std :: map插入或std :: map查找？

Question

假設您想要保存現有條目的地圖。 20％的時間，您插入的條目是新數據。使用返回的迭代器執行std :: map :: find然後std :: map :: insert是否有優勢？或者，嘗試插入然後根據迭代器是否指示記錄已插入或未插入而動作更快？

Answer 1

答案是你沒做。相反，你想Scott Meyers做點什麼通過項目的Effective STL 24提示：

typedef map<int, int> MapType; // Your map type may vary, just change the typedef 

MapType mymap; 
// Add elements to map here 
int k = 4; // assume we're searching for keys equal to 4 
int v = 0; // assume we want the value 0 associated with the key of 4 

MapType::iterator lb = mymap.lower_bound(k); 

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first))) 
{ 
    // key already exists 
    // update lb->second if you care to 
} 
else 
{ 
    // the key does not exist in the map 
    // add it to the map 
    mymap.insert(lb, MapType::value_type(k, v)); // Use lb as a hint to insert, 
                // so it can avoid another lookup 
} 

Answer 2

2之間的速度幾乎沒有任何區別，find將返回一個迭代器，insert會執行相同的操作，並且無論如何將搜索映射以確定條目是否已經存在。

所以......它歸結爲個人喜好。我總是嘗試插入，然後根據需要進行更新，但有些人不喜歡處理返回的對。

Answer 3

map [key] - 讓stl把它整理出來。這是最有效地傳達你的意圖。

是的，夠公平的。

如果您執行查找，然後執行插入操作，則在執行2 x O（log N）時會發生錯誤，因爲查找只會讓您知道是否需要插入插入的位置（lower_bound可能幫助你）。只是一個直接插入，然後檢查結果是我會走的方式。

Answer 4

任何有關效率的答案將取決於您的STL的確切實施。唯一可以確定的方法是通過兩種方式進行基準測試。我猜猜這種差異不太可能是重要的，所以根據你喜歡的風格來決定。

Answer 5

我想如果你做了一個查找然後插入，額外的成本將是當你沒有找到鑰匙和執行後插入。這就像是按照字母順序瀏覽書籍，而不是找到書本，然後再次查看書籍以查看插入它的位置。它歸結爲你將如何處理鑰匙，如果他們不斷變化。現在有一些靈活性，如果你沒有找到它，你可以登錄，例外，做任何你想要的...

Answer 6

如果你關心效率，你可能想檢查出hash_map<>。

典型地圖<>被實現爲二叉樹。根據您的需要，hash_map可能更有效。

Answer 7

的這個問題的答案也取決於它是多麼昂貴的創建你在地圖存儲值類型：

typedef std::map <int, int> MapOfInts; 
typedef std::pair <MapOfInts::iterator, bool> IResult; 

void foo (MapOfInts & m, int k, int v) { 
    IResult ir = m.insert (std::make_pair (k, v)); 
    if (ir.second) { 
    // insertion took place (ie. new entry) 
    } 
    else if (replaceEntry (ir.first->first)) { 
    ir.second->second = v; 
    } 
} 

對於值類型如int，上面會更有效率比查找後跟插入（在沒有編譯器優化的情況下）。如上所述，這是因爲通過地圖的搜索只發生一次。

然而，插入電話要求你已經有了新的「價值」建設：

class LargeDataType { /* ... */ }; 
typedef std::map <int, LargeDataType> MapOfLargeDataType; 
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult; 

void foo (MapOfLargeDataType & m, int k) { 

    // This call is more expensive than a find through the map: 
    LargeDataType const & v = VeryExpensiveCall (/* ... */); 

    IResult ir = m.insert (std::make_pair (k, v)); 
    if (ir.second) { 
    // insertion took place (ie. new entry) 
    } 
    else if (replaceEntry (ir.first->first)) { 
    ir.second->second = v; 
    } 
} 

爲了調用「插入」我們正在付出的昂貴的調用來構建我們的價值型 - 和從你在問題中所說的話你不會在20％的時間內使用這個新值。在上述情況下，如果更改映射值類型不是一個選項，那麼首先執行「查找」以檢查是否需要構造該元素會更有效。

或者，可以更改地圖的值類型，以使用您最喜歡的智能指針類型將句柄存儲到數據中。插入調用使用空指針（構造非常便宜），並且只有在必要時纔是構造的新數據類型。

Answer 8

我失去最多的回答。

查找回報map.end（），如果它沒有找到任何這意味着如果你有夠慢的

map.insert 

任何元素不增加新的東西，然後

iter = map.find(); 
if (iter == map.end()) { 
    map.insert(..) or map[key] = value 
} else { 
    // do nothing. You said you did not want to effect existing stuff. 
} 

兩次已經在地圖中，因爲它將不得不搜索兩次。一旦看到它是否在那裏，再次找到放置新事物的地方。

Answer 9

我似乎沒有足夠的觀點留下評論，但被選中的答案似乎很長時間對我有利 - 當你認爲insert會返回迭代器時，爲什麼要搜索lower_bound，何時可以使用迭代器返回。奇怪。