views:

736

answers:

2

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?

+9  A: 
#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;
}
skwllsp
Thanks. I get a compilation error with the above code on boost 1.41.
celil
I have tested this example with Boost.1.41 and Visual Studio 2005 and everything is OK. What compliler and OS do you use?
skwllsp
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.
celil
Sorry, I just mistyped `insert_()` instead of `insert()`. This was an error what caused problems on gcc. I fixed the code.
skwllsp
It has nothing to do with the gcc version or Boost version
skwllsp
Actually it was an issue with the gcc version. After upgrading from 4.2 to 4.4 your code compiles.
celil
A: 

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.
aJ
I am not very experienced in C++. Can you give me a sample implementation of your suggestion?
celil