C++數據結構保持插入順序並能夠通過鍵查找

有沒有任何數據結構（C++ 03或Boost）可以保持插入順序並能夠通過鍵查找。我目前做的是這樣的：C++數據結構保持插入順序並能夠通過鍵查找

struct Foo { 
    vector<string> v; // keep the key order by insert time 
    map<string, string> m; // <key, value> 
}; 

Foo foo; 
foo.v.push_back("key1"); 
foo.m["key1"] = "value1"; 
foo.v.push_back("key2"); 
foo.m["key2"] = "value2";

有了這個，我可以保持我想在矢量對象的順序，並且仍然能夠快速地與地圖對象查找。缺點是我必須保持矢量對象和地圖對象的氣味。

來源

2013-11-21 Stan

您可以使用[std :: find]（http://www.cplusplus.com/reference/algorithm/find/）的矢量。但是，按鍵查找並不會有效。 – memo1288

僅僅使用像這樣的結構具有地圖和矢量有什麼問題？你可以創建一個類來抽象'insert'，'find'和'delete'，這樣'insert'就可以將k，v放在地圖上，並且將它推到vector上，'delete'從map和vector中移除，'find '在地圖上查找。我猜最大的問題是：你會使用這個結構，爲什麼插入順序很重要？ – Vinay

[A std :: map跟蹤插入順序的可能的重複]（http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of -insertion） – Vinay

可能的選項是Boost Multi-index containers library。當我有類似的要求時，我已經使用過他們。習慣模板設置需要一點時間，但之後它會很好地工作。

來源

2013-11-21 07:41:29

你只能擁有組織，由一個物業爲主，所以如果你想查找通過插入的時間，你想通過字符串查找，那麼你需要兩個數據結構

，如果你需要通過字符串以迭代 - 再地圖是好的 - 但如果你會迭代的時間，只有字符串查找比std::unordered_map將更快

如果你沒有做很多插入/刪除，然後std :: vector很好 - 否則考慮一個std ::列表

也考慮有一個結構包含一個迭代器到第二個，所以喲ü可以很容易地從兩個刪除，最有可能把向量迭代器unordered_map

list<string, string> insertOrder 
unordered_map<string, list<string, string>::iterator> fastLookup

您可以在template<K,V>類包裝這使您可以重複使用其他類，並保持在一個地方的協調

來源

2013-11-21 07:00:06

我認爲這是錯誤的。您可以實施保留散列的訂單。 CRuby將哈希順序保存在1.9中（不過不幸的是不是按規範說明的，如果我沒有記錯的話，不用在64位實現中）。所以@斯坦的問題仍然是開放的：是否有人在C++中發佈了一個保存順序的散列？ –

@JoachimWuttke - 我相信這基本上是一樣的東西，但使用std的類。訂單保留哈希有一個散列，它將鏈接列表中的指針指向爲節點 –

C++數據結構保持插入順序並能夠通過鍵查找

回答

相關問題