STL結構：「插入如果不存在」操作？

我正在處理一些程序，現在正在處理一些指數時間算法。正因爲如此，我的程序的一個主循環正在運行很多次，我試圖儘可能地優化它。STL結構：「插入如果不存在」操作？

分析顯示大部分時間用於std::unordered_map的查找和散列計算。

我想知道：

是否有緩存std::unordered_map一個關鍵的哈希值，然後將它作爲參數傳遞給插入以後的方法嗎？
有沒有一種方法，我可以做下面的一個操作：給定一個鍵和值{x,y}，檢查關鍵x在地圖上，如果不是，將其插入並返回{x,y}，否則返回{x,z}對於任何z已經在地圖中。

我正在做這樣的事情，但效率不高，因爲我必須計算密鑰的哈希值並檢查它是否在地圖中。但是如果它不在地圖中，我會做一個完全獨立的插入操作。理論上，檢查它是否存在於地圖中，如果插入它應該找到它將在地圖中的位置。

我願意嘗試其他數據結構，如std::map或Boost的其他數據結構，如果它們會減少此操作的時間。

來源

2015-10-06 jmite

改爲使用線程。或者你可以使用OpenMP並行化你的循環 –

什麼是關鍵類型？ – SergeyA

你甚至可能想要一個'std :: vector'，因爲它非常緩存和預取友好。請參閱：http：//baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html – NathanOliver

您可以使用返回值std::unordered_map::insert()來實現關鍵存在檢查+使用單個散列計算的插入。

template<typename K, typename V> 
std::pair<K, V> myinsert(std::unordered_map<K, V> &map, const std::pair<K, V> &kv) 
{ 
    return *(map.insert(kv).first); 
}

來源

2015-10-06 15:53:13 timrau

備註：還有std :: map :: emplace –

它應該足以讓'V'自己返回，因爲密鑰已經知道 - 它被傳遞到函數中。 –

@DieterLücking我建議改變返回值，而不是參數。 'return（map.insert（kv）.first） - > second'。 –

不能緩存鍵的哈希值，但如果你有一個迭代器，它最近一次（無論是從當你最初插入，或者你最後一次成功發現了上述物品），你可以使用insert(const_iterator hint, value_type&& value);成員也可以幫助將迭代器返回到新插入的元素或阻止插入的先前存在的元素。

來源

2015-10-06 15:56:35

你是什麼意思，「這是最後一次」？如上所述，從上次插入的迭代器開始，或者從我找到（x）開始的迭代器，它沒有找到它？ – jmite

STL結構：「插入如果不存在」操作？

回答

相關問題