在地圖和列表之間尋找標準容器

尋找一個容器，用於存儲自定義關鍵字（如地圖）下的元素，允許在複雜度較高的關鍵點下搜索O（n）（如地圖），但也記住插入對（鍵和值）的順序，允許push_front和pop_back功能，如列表中所示在地圖和列表之間尋找標準容器

編輯：只需使用兩個容器即可解決。按順序存儲對的映射和用於存儲索引的列表。如果有人提供更優雅的解決方案，將會讓這個問題開放。

雖然語法有點粗糙，但您可以使用[multiindex]（http://www.boost.org/doc/libs/1_62_0/libs/multi_index/doc/index.html） – EdChum

沒有標準容器都被排序並記住未排序的訂單。您可以使用映射進行存儲和快速搜索，同時將密鑰存儲在雙端隊列中（支持push_front和pop_back），從而構建多索引的簡單版本。假設快速搜索是最重要的。 –

c + + 11有std :: unsorted_map，正是這樣做。 –

標準庫中沒有這樣的數據結構。

實現這種結構的「微不足道」方法是在內部使用兩個獨立的結構。用於查找的映射，以及用於按照插入順序進行迭代的列表（或向量，或雙向變換）。其中一個數據結構應該存儲對象，另一個可以存儲指向對象的指針。

Boost庫集合中存在這種多索引容器的泛化。

2017-08-16 09:43:47 user2079303

我認爲列表會比矢量更好，因爲列表迭代器永遠不會失效，因此您可以將迭代器保留在地圖中。 – alain

@alain或者您可以將對象存儲在向量中的映射和迭代器中，在這種情況下這不是問題。儘管如此，你最終還是錯過了一個向量的最大好處，那就是內存的連續性。 – user2079303

是的，這是一種可能性。 – alain

回答