執行索引列表的C++數據結構

我正在尋找最有效的數據結構來維護索引列表。您可以輕鬆地查看它interms一個STL地圖：執行索引列表的C++數據結構

std::map<int,std::vector<int> > eff_ds;

我，因爲我目前使用此設置使用此作爲一個例子。我想要執行的操作是：

基於鍵插入值：與eff_ds [鍵] .push_back（..）相似;
按照每個鍵打印數據結構的內容。

我也試圖用無序的映射和轉發列表，

std::unordered_map<int,std::forward_list<int> > eff_ds;

這是我能在時間上做，如果我使用C++，還是有其他的選擇是最好的？

更新： - 只要我做的所有鍵相同的前/後

我能做的插入任何一種方式。爲了讓我的問題更清楚，請考慮以下內容：

在我的算法的每次迭代中，我將有一個外部塊給我一個（鍵，值） - 它們都是單個整數 - 作爲輸出對。當然，我將不得不將這個值插入相應的鍵。而且，在不同的迭代中，可能會以不同的值返回相同的密鑰。最後，我的輸出數據（寫入文件）看起來應該是這樣的：

k1: v1 v2 v3 v4 
k2: v5 v6 v7 
k3: v8 
. 
. 
. 
kn: vm

這些迭代的數量相當大~1m。

來源

2014-10-10 Swami

這些都聽起來像很好的解決方案。爲什麼他們不夠？你有特別的要求，使他們無效？你的數據集足夠大以至於不重要？你最關心哪個特定的操作（查找？刪除？插入？） – 2014-10-10 03:17:52

我只關心從後面/前面插入，這並不重要。我的數據集相當大，因爲可能的密鑰數量可能超過100萬，但每個節點的數量卻超過了數百個。你可以把它看作一個大圖，但是連接稀疏。我感興趣的只是添加邊緣並根據每個邊緣打印圖形的內容。希望這個清楚。我只想知道是否有更聰明的方法來用C++來做到這一點。 – Swami 2014-10-10 03:22:27

使用unordered_map將非常快地呈現單元素訪問，但是順序訪問也非常緩慢。如果你需要用鍵和地圖中的所有鍵打印出所有相關的值，我會去std :: map。否則，如果你只訪問密鑰單獨去unordered_map。既然你已經在考慮密鑰，我不會談論鄰接列表/向量。 – 2014-10-10 03:27:03

有兩個層面的問題：

有什麼用，你希望能夠查找使用數字鍵在容器中的物品，有大量的最佳容器密鑰和密鑰是稀疏的

數字鍵可能會使自己的載體爲此，但如果密鑰稀疏填充，會浪費大量的內存。

假設您不想按順序遍歷關鍵字（您沒有聲明爲需求），那麼unordered_map可能是最好的選擇。
是什麼號碼的列表的最佳容器，從而允許插入在任一端和檢索號的列表，以便（外側地圖的值類型）

這個問題的答案的能力將取決於你想在前面插入元素的頻率。如果這種情況經常發生，那麼您可能需要考慮forward_list。如果你主要在最後插入，那麼一個向量的開銷就會降低。根據您的更新問題

，因爲你可以限制自己添加值列表的末尾，既然你不關心在列表中重複的條目，我會建議使用std::unordered_map<int,vector<int> >

來源

2014-10-10 03:41:15 harmic

請參閱更新。 – Swami 2014-10-10 04:38:23

@Swami已更新以考慮您的更新，但建議不會有太大變化！ – harmic 2014-10-10 05:41:34

執行索引列表的C++數據結構

回答

相關問題