上無序集合

的set_difference算法執行set_difference需要在範圍以下上無序集合

各單元必須已經根據該相同標準

這對於哈希表的情況下進行排序。

我想實現在std::remove_copy方面設定的差AB在去除標準將在集合B

的A的元素的存在，有沒有一個標準，有效的，最快的，最安全的如何做到這一點？

2014-03-28 Nikos Athanasiou

使用臨時std :: set對象並將哈希表數據插入到std :: set對象中可能會更快（我相信它更安全）。然後調用set_difference（）並將結果輸出回散列表。我是確保事情先行工作的支持者，然後在必要時進行優化。 – PaulMcKenzie

那麼，如果你真的想做一個臨時副本，使用std :: vector和std :: sort，而不是std :: set。它會（更多！）更快，更高效地存儲內存。 – ltjax

如果您有兩個哈希表，最有效的方法應該是迭代其中一個哈希表，查找另一個哈希表中的每個元素。然後將你沒有找到的那些插入到第三個容器中。草圖可能是這樣的：

std::vector<int> result; 
std::copy_if(lhs.begin(), lhs.end(), std::back_inserter(result), 
    [&rhs] (int needle) { return rhs.find(needle) == rhs.end(); });

來源

2014-03-28 11:04:17

我更喜歡rhs.count（針）== 0; 然而，我對你的答案的主要批評是你剛剛給你的算法的代碼，但沒有說明你爲什麼認爲它是最快的可用方法。 – CashCow

如果你有2個無序集合A和長度Na和Nb的B和你想要做一組差，即得到的不是所有的元素B，則因爲B中的查找是恆定的時間，所以簡單地迭代A並檢查它是否在B中的複雜度是O（Na）。

如果A是一組無序和B是一組（或有序矢量等），然後每個查找將日誌（NB），以便全部複雜性將是O（NA *日誌（NB））

排序首先使它（Na * log（Na））排序，然後Na + Nb進行合併。如果Na顯着小於Nb，則Na * log（Nb）顯然小於Na + Nb，並且如果Na越來越大於Nb，那麼首先進行分選並不會更快。

因此，我認爲你排序第一（通過首先排序，我的意思是將它移動到一個排序的集合）沒有得到什麼。

來源

2017-08-02 08:10:02 CashCow

回答

相關問題