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?

Is maintaining a separate list to track the insertion order out of the question? — Rich Schuler, Dec 14 '09 at 08:07
It's unfortunate this question was closed, because `std::map` requires O(n lg n) construction time, so it is not a substitute for `std::unordered_map` at O(n). — Walter Nissen, Jul 02 '21 at 22:17

score 11 · Accepted Answer · 2009-12-14T08:47:03.877

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

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>

using namespace std;
using namespace boost;
using namespace boost::multi_index;


struct key_seq{};
struct key{};

struct Data_t
{
    int key_;
    int data_;
    Data_t (int key_v, int data_v) : key_(key_v), data_(data_v) {}
};

int main()
{
    typedef multi_index_container<
        Data_t,
        indexed_by<
            hashed_unique<tag<key>,  BOOST_MULTI_INDEX_MEMBER(Data_t,int,key_)>,
            sequenced<tag<key_seq> >
        >
    > Map;

    typedef Map::const_iterator It;

    typedef index<Map,key>::type Map_hashed_by_key_index_t;
    typedef index<Map,key>::type::const_iterator  Map_hashed_by_key_iterator_t;

    typedef index<Map,key_seq>::type Map_sequenced_by_key_index_t;
    typedef index<Map,key_seq>::type::const_iterator  Map_sequenced_by_key_iterator_t;

    Map m;
    m.insert(Data_t(11,0));
    m.insert(Data_t(0,1));
    m.insert(Data_t(21,1));

    {
        cout << "Hashed values\n";
        Map_hashed_by_key_iterator_t i = get<key>(m).begin();
        Map_hashed_by_key_iterator_t end = get<key>(m).end();
        for (;i != end; ++i) {
            cout << (*i).key_ << " " << (*i).data_ << endl;
        }
    }

    {
        cout << "Sequenced values\n";
        Map_sequenced_by_key_iterator_t i = get<key_seq>(m).begin();
        Map_sequenced_by_key_iterator_t end = get<key_seq>(m).end();
        for (;i != end; ++i) {
            cout << (*i).key_ << " " << (*i).data_ << endl;
        }
    }

    return 0;
}

Thanks. I get a compilation error with the above code on boost 1.41. — D R, Dec 14 '09 at 08:30
I have tested this example with Boost.1.41 and Visual Studio 2005 and everything is OK. What compliler and OS do you use? — , Dec 14 '09 at 08:38
I'm using i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5646) (dot 1) on Snow Leopard. I am downloading gcc-4.4 right now, hopefully it will compile with the latest version of gcc. — D R, Dec 14 '09 at 08:41
Sorry, I just mistyped `insert_()` instead of `insert()`. This was an error what caused problems on gcc. I fixed the code. — , Dec 14 '09 at 08:49
Actually it was an issue with the gcc version. After upgrading from 4.2 to 4.4 your code compiles. — D R, Dec 14 '09 at 10:38
Thanks for your answer, but I got the same order after running this code. Any idea why? — Lucifer, May 04 '20 at 02:50

score 3 · Answer 2 · answered Dec 14 '09 at 08:23

3

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.

answered Dec 14 '09 at 08:23

aJ.

34,624
22
86
128

I am not very experienced in C++. Can you give me a sample implementation of your suggestion? – D R Dec 14 '09 at 08:32

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

2 Answers2

Linked