2009-12-14 57 views
7

我有以下代碼的順序:一個C++哈希表,保留插入

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

不過,我尋找的東西,保留順序,這樣以後我可以通過在同一順序的元素迭代插入它們。在我的電腦上面的代碼不保留順序,並打印如下:

0 1 
11 0 
21 2 

我想也許我可以用一個boost::multi_index_container

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

有人能告訴我如何使用來實現我的原代碼這個容器(或任何其他適當的容器),以便迭代器遵循插入順序?

+1

正在維護一個單獨的列表來跟蹤插入順序嗎? – Qberticus

回答

11
#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; 
} 
+0

謝謝。上面的代碼在boost 1.41上出現編譯錯誤。 – dzhelil

+0

我用Boost.1.41和Visual Studio 2005測試了這個例子,一切都正常。你使用什麼compliler和操作系統? –

+0

我在Snow Leopard上使用i686-apple-darwin10-gcc-4.2.1(GCC)4.2.1(Apple Inc. build 5646)(dot 1)。我現在正在下載gcc-4.4,希望它能用最新版本的gcc編譯。 – dzhelil

2

您可以嘗試使用地圖和矢量的組合創建有序地圖。

  • 向量可以容納一對鑰匙和 值。
  • 向量迭代器可以作爲 迭代器來遍歷有序映射。
  • 地圖可以用來更快地訪問元素 。
+0

我在C++中不是很有經驗。你能給我一個你的建議的樣本實施嗎? – dzhelil