地圖<key,bool> vs設置<key>以保持密鑰集合的唯一性

我從常量字符串列表中編寫一個文本文件，我需要避免重複（列表包含重複項）。這些數據結構中的哪一個更好性能）用於跟蹤已寫入字符串，地圖<key,bool> vs設置<key>以保持密鑰集合的唯一性

map<string,bool> 
set<string>

現在我要如何做，這是，

foreach(string in list) 
    if(not found in map/set) 
     write to file 
     insert to map/set 
    endif 
end

否則有沒有這樣做的另一種方式？

來源

2013-06-26 Dinushan

地圖不包含帶重複鍵的條目，因此使用map<string,bool>沒有意義。這與性能無關。 std::set<std::string>或std::unordered_set<std::string>會完成這項工作。這裏有一個例子：

std::vector<std::string> word_list = ....; 
std::set<std::string> word_set; 

for (const auto& s : work_list) // loop over words in word_list 
{ 
    if(word_set.insert(s).second) // attempt to insert: fails if s already in set 
    { 
    // insertion succeeded: write to file 
    } 
}

來源

2013-06-26 07:48:01 juanchopanza

實際上，使用'map '有一點，儘管它可能不適用於此。當你刪除/重新添加項目時，'map '可能會比'set '執行得更好，因爲重新添加只是改變'bool'的狀態，而不是重新分配和重新平衡。 –

@MatthieuM。好點，但是像例子中那樣調用插入，避免了這種重新添加。所以機器已經在'set'接口中，只需要知道它。 – juanchopanza

您就有可能獲得與set<string>因爲map<string,bool>需求的性能改進來存儲額外的布爾值，其中至少有大小1.根據如何分配和std ::字符串實現這可能導致在更大的內存消耗（想到分配）和緩存未命中。在這裏尋找finding和inserting。

來源

2013-06-26 07:56:47

如果您可以選擇使用C++ 11，我建議您使用unordered_set，因爲它應該比set漸近地好。如果這不是一個選項，則使用set。沒有理由爲此任務使用map<string, bool>。

來源

2013-06-26 07:59:48

你並不真的需要另一個容器，使用算法：

std::vector<std::string> list = ... 
std::sort(list.begin(), list.end()); 
std::unique(list.begin(), list.end()); 

// alternatively, copy to your file without changing source vector 
std::unique_copy(list.begin(), list.end(), std::ostream_iterator(out_stream));

不管你做什麼，你得到的操作（在地圖上插入/套* n項）的n.log複雜性。一個地圖/設置解決方案讓你2.n.log操作2.n內存;使用算法可以完成n + n.log操作和1.n內存的工作。

來源

2013-06-26 10:52:35 lip

地圖<key,bool> vs設置<key>以保持密鑰集合的唯一性

回答

相關問題