一个保留插入顺序的C ++哈希映射 [英] a C++ hash map that preserves the order of insertion

问题描述

我有以下代码：

  #include< iostream> 
 #includeboost / unordered_map.hpp
 
 using namespace std; 
 using namespace boost; 
 
 int main（）
 {
 
 typedef unordered_map< int，int>地图; 
 typedef Map :: const_iterator It; 
 
地图m; 
 m [11] = 0; 
 m [0] = 1; 
 m [21] = 2; 
 
 for（It it（m.begin（））; it！= m.end（）; ++ it）
 cout<第一<< <第二<< endl; 
 
 return 0; 
} 
  

但是，我在寻找保留顺序的东西，以与插入它们相同的顺序对元素进行迭代。在我的计算机上，上述代码不保留订单，并打印以下内容：

  0 1 
 11 0 
 21 2 
  

我想也许我可以使用 boost :: multi_index_container

  typedef multi_index_container< 
 int，
 indexed_by< 
 hashed_unique< identity< int> >，
 Sequenced<> 
> 
>地图;有人可以告诉我如何使用这个容器（或任何其他适当的容器）来实现我的原始代码。迭代器遵循插入的顺序？
解决方案
 
  #include< iostream& 
 #includeboost / 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> > 
> 
>地图; 
 
 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; 
 
地图m; 
 m.insert（Dat_t（11,0））; 
 m.insert（Data_t（0,1））; 
 m.insert（Data_t（21,1））; 
 
 {
 cout<< 散列值\\\
; 
 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\\\
; 
 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; 
} 
  
 
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?
解决方案
#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;
}


                        
这篇关于一个保留插入顺序的C ++哈希映射的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！