a C++ hash map that preserves the order of insertion

Question

I have the following code:

#include <iostream>
#include "boost/unordered_map.hpp"

using namespace std;
using namespace boost;

int main()
{

    typedef unordered_map<int, int> Map;
    typedef Map::const_iterator It;

    Map m;
    m[11] = 0;
    m[0]  = 1;
    m[21] = 2;

    for (It it (m.begin()); it!=m.end(); ++it)
        cout << it->first << " " << it->second << endl;

    return 0;
}

However, I am looking for something that preserves the order so that later I can iterate over the elements in the same order in which they were inserted. On my computer the above code does not preserve the order, and prints the following:

 0 1
11 0
21 2

I thought maybe I could use a boost::multi_index_container

typedef multi_index_container<
    int,
    indexed_by<
        hashed_unique<identity<int> >,
        sequenced<>
    >
> Map;

Can somebody show me how to implement my original code using this container (or any other appropriate container) so that the iterator follows the order of insertion?

Solution

You can try creating an ordered map using the combination of map and the vector.

• Vector can hold the pair of key and value.
• Vector iterator can be used as iterator to traverse ordered map.
• map can be used access the elements faster.

Comments

[Jonathan O'Neil]

Is maintaining a separate list to track the insertion order out of the question?

[D R]

I am not very experienced in C++. Can you give me a sample implementation of your suggestion?