c++ Container that preserve insertion order

Question

I have a std::map which store a key with a vector of std::any.
The purpose is to store all values and print them (with the different types) for each key. No other operations are performed on the container, only "insertion" and "clean".

I want to clarify that the container is filled (and emptied) very frequently, so i need an efficient container.

It all works with my code. The problem, however, is that when i print the values they are sorted according to the key, but i have to print (or store) them by insertion order.

My code:

#include <iostream>
#include <map>
#include <vector>
#include <any>

std::map<int, std::vector<std::any>> testMap;

void insertMap(int value, std::vector<std::any> tempVector);
void printMap();


int main()
{   
    std::vector<std::any> tempVector;
    
    tempVector.clear();
    tempVector.push_back(1000);
    tempVector.push_back((std::string)"hello");
    tempVector.push_back(0.10f);
    insertMap(10, tempVector);
    
    
    tempVector.clear();
    tempVector.push_back(1500);
    tempVector.push_back((std::string)"hello2");
    tempVector.push_back(0.20f);
    insertMap(5, tempVector);
    
    tempVector.clear();
    tempVector.push_back(2000);
    tempVector.push_back((std::string)"hello3");
    tempVector.push_back(0.5f);
    insertMap(7, tempVector);

    // etc..
    
    printMap();
}

void insertMap(int value, std::vector<std::any> tempVector)
{
    testMap[value].insert(testMap[value].end(), tempVector.begin(), tempVector.end());
}


void printMap()
{
    for (const auto& [key, value] : testMap)
    {
       std::cout << "key=" << key << "\n";

        for(auto vec_iter : value)
        {
            if (vec_iter.type() == typeid(int))
                std::cout << "\t" << "int=" << std::any_cast<int>(vec_iter) << "\n";

            else if (vec_iter.type() == typeid(float))
                std::cout << "\t" << "float=" << std::any_cast<float>(vec_iter) << "\n";

            else if (vec_iter.type() == typeid(std::string))
                std::cout << "\t" << "string=" << std::any_cast<std::string>(vec_iter) << "\n";
        }
    }
}

Output:

key=5
key=7
key=10

Expected output:

key=10
key=5
key=7

I tried to using unordered_map but it doesn't print them by insertion order.
So which container could i use? What could be the best performance in my case?
I thought that i could use a std::vector< std::map<int, std::vector<std::any>> > (vector that store std::map). But is it fast? Is there a better solution?

Answer 1

There is no standard library container that both provides fast access by key (which is presumably why you're using std::map to begin with) and "preserves insertion order". If you really need access by key, then iteration order is something you give up control over.

If you need to recover the order of insertion, then you are going to have to preserve it. The simplest way to do that is to just store a vector of map iterators alongside your map. When you insert an item into the map, push the new iterator for it to the back of the vector too.

Answer 2

If you are in a position to use Boost, Boost.MultiIndex can be resorted to:

Live Coliru Demo

#include <iostream>
#include <vector>
#include <any>
#include <utility>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/key.hpp>

struct test_map_value_type
{
  test_map_value_type(int first, const std::vector<std::any>& second):
    first{first},second{second}{}
  
  int first;
  mutable std::vector<std::any> second;
};

boost::multi_index_container<
  test_map_value_type,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_unique<
      boost::multi_index::key<&test_map_value_type::first>
    >,
    boost::multi_index::sequenced<>
  >
> testMap;

void insertMap(int value, std::vector<std::any> tempVector);
void printMap();

int main()
{   
    std::vector<std::any> tempVector;
    
    tempVector.clear();
    tempVector.push_back(1000);
    tempVector.push_back((std::string)"hello");
    tempVector.push_back(0.10f);
    insertMap(10, tempVector);
    
    
    tempVector.clear();
    tempVector.push_back(1500);
    tempVector.push_back((std::string)"hello2");
    tempVector.push_back(0.20f);
    insertMap(5, tempVector);
    
    tempVector.clear();
    tempVector.push_back(2000);
    tempVector.push_back((std::string)"hello3");
    tempVector.push_back(0.5f);
    insertMap(7, tempVector);

    // etc..
    
    printMap();
}

void insertMap(int value, std::vector<std::any> tempVector)
{
    auto it=testMap.emplace(value,std::vector<std::any>{}).first;
    it->second.insert(it->second.end(), tempVector.begin(), tempVector.end());
}


void printMap()
{
    for (const auto& [key, value] : testMap.get<1>())
    {
       std::cout << "key=" << key << "\n";

        for(auto vec_iter : value)
        {
            if (vec_iter.type() == typeid(int))
                std::cout << "\t" << "int=" << std::any_cast<int>(vec_iter) << "\n";

            else if (vec_iter.type() == typeid(float))
                std::cout << "\t" << "float=" << std::any_cast<float>(vec_iter) << "\n";

            else if (vec_iter.type() == typeid(std::string))
                std::cout << "\t" << "string=" << std::any_cast<std::string>(vec_iter) << "\n";
        }
    }
}

Output

key=10
    int=1000
    string=hello
    float=0.1
key=5
    int=1500
    string=hello2
    float=0.2
key=7
    int=2000
    string=hello3
    float=0.5