迭代unordered_set的效率如何？

遍歷unordered_set是否需要查看哈希表的每個桶？如果是這樣，那不是非常低效嗎？如果我想頻繁迭代一個集合，但仍然需要在O（1）中移除，那麼unordered_set仍然是最好的數據結構？迭代unordered_set的效率如何？

來源

2016-02-28 Duncan

迭代容器的每個元素對於所有標準C++容器都是「O（n）」。你是否在測試成員資格，哪一個更快？ –

'*如果是這樣，那不是非常低效嗎？*爲什麼這會「非常低效？」散列表存儲在連續內存中，因此檢查存儲區並不是特別繁瑣，性能明智。它顯然不像檢查vector那樣快，但它不像緩存沒有通過set來運行。 –

據我所知，桶的數量應該大於預期的元素數量，所以我認爲需要更多的時間遍歷所有的桶，然後訪問每個桶的內容。 – Duncan

碰巧，std::unordered:set鏈路的常見的實現所有元件一起多作爲std::forward_list確實，所以橫穿容器基本上等同於遍歷列表（細節here）。無論如何，如果有疑問，請查看您的計劃，看看結果是否符合您的需求。

來源

2016-02-29 06:54:09

散列表將數據存儲在向量中，並且通過將密鑰轉換爲散列號（通常爲long），將所有內容都索引，該散列號將成爲所需元素的向量中的索引，同時還有使用向量內的向量做這個。如果通過std::unordered_set迭代它只收O(n)，因爲它就像通過std::vector

來源

2016-02-28 18:52:35

當然不是那麼簡單？除非散列函數減少到非常小的域，否則必須包含稀疏數組，否則基礎向量將會很大。 –

迭代將通過哈希表迭代是不是通過vector迭代慢？是。 A vector將連續存儲其元素;哈希表需要一些方法來確定一個存儲桶是否包含數據。一些哈希表爲每個存儲桶提供映射到同一個存儲桶的鏈接值列表;其他人使用其他方法。無論哪種方式，迭代器需要查看每個存儲桶並確定其是否爲空。這並不像指針算術那麼快。

但是，我不會將花費在空桶上的額外時間歸類爲「非常低效」。僅僅因爲它不如排序的vector那麼快並不意味着效率低下。您仍然擁有緩存一致性，因爲存儲桶可能不佔用太多的內存，而測試空的只是單個緩存的內存獲取。

最後，每個數據結構都有折衷。如果你想O（1）查找和刪除，一個哈希表是唯一的方法來獲取它。這意味着迭代需要比vector更長的時間。但不會只有一個set。

來源

2016-02-28 19:14:31

爲什麼會比'std :: set'更快地迭代散列表？ – Herbert

迭代unordered_set的效率如何？

回答

相關問題