un C++ mappa di hash che preserva l'ordine di inserimento

Question

Ho il seguente codice:

#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; 
} 

Tuttavia, sto cercando qualcosa che preserva l'ordine in modo che dopo posso iterare gli elementi nello stesso ordine in cui sono stati inseriti. Sul mio computer il codice di cui sopra non conservare l'ordine e stampa il seguente:

0 1 
11 0 
21 2 

ho pensato che forse avrei potuto usare un boost::multi_index_container

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

Qualcuno mi può mostrare come implementare il mio codice originale utilizzando questo contenitore (o qualsiasi altro contenitore appropriato) in modo che l'iteratore segua l'ordine di inserimento?

Answer 1

#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; 
} 

Answer 2

È possibile provare a creare una mappa ordinata utilizzando la combinazione di mappa e vettore.

• Il vettore può contenere la coppia di chiavi e il valore .
• Vector iterator può essere utilizzato come iteratore per attraversare la mappa ordinata.
• mappa può essere utilizzato accedere agli elementi più veloce.