C++用於雙向隨機存取

有效的數據結構我有元件和兩組A和B和B現在這些都與彼此（0..1：N基數），所以每一個具有在乙至多一個夥伴並且每個b可以有幾個（至少一個）與A中項目的關聯。 A是一組整數對，B是整數。C++用於雙向隨機存取

是否有存儲這樣的「雙向」地圖有效的方法？一個簡單的方法是使用兩個地圖：

map<pair<unsigned int, unsigned int>, unsigned int> AtoB 
map<unsigned int, vector<pair<unsigned int, unsigned int> > > BtoA

但也許有對付這種更有效的好方法。

感謝您的幫助

來源

2012-11-16 user1801173

加速包含兩個庫來處理這個：Boost.Bimap和Boost.MultiIndex。前者針對雙射（「雙向」）映射的問題，後者更爲一般，實現類似於具有任意索引的內存數據庫。

鑑於您的unsigned int鍵不唯一映射到你對，我覺得多指標更是爲了。這是自從我最後一次使用這個庫很長一段時間，但看着教程，你需要像

struct YourData { 
    unsigned key; 
    std::pair<unsigned, unsigned> value; 
}; 

typedef multi_index_container< 
    YourData, 
    indexed_by< 
     ordered_non_unique<member<YourData, unsigned, &YourData::key> >, 
     ordered_unique<member<YourData, std::pair<unsigned, unsigned>, 
           &YourData::value> > 
    > 
> YourContainer;

如果你不想使用Boost，那麼你至少可以簡化您的當前設置通過替代

map<unsigned int, vector<pair<unsigned int, unsigned int> > >

由std::multimap<unsigned, std::pair<unsigned, unsigned>>。

來源

2012-11-16 09:49:04

如何boost::bimap？ http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html我認爲這是給你的。

來源

2012-11-16 09:48:05 ForEveR

地圖和Multimap之富人O（log n）的的效率，所以，我覺得就是一個用於存儲數據的最佳方式。我建議使用

map<pair<unsigned int, unsigned int>, unsigned int> AtoB 
multimap<pair<unsigned int, unsigned int>, unsigned int> BtoA

來源

2012-11-16 10:14:07 Vargan

C++用於雙向隨機存取

回答

相關問題