2

我从字符串的 const 列表中编写了一个文本文件，我需要避免重复（列表包含重复）。这些数据结构中的哪一个更好（在性能方面）用于跟踪已写入的字符串，

map<string,bool>
set<string>

现在我将如何做到这一点，

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

或者有没有其他方法可以做到这一点？

4

4 回答 4

3

地图不包含具有重复键的条目，因此使用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-26T07:48:01.600 回答
1

您可能会获得性能改进，set<string>因为map<string,bool>需要存储一个至少大小为 1 的额外 bool 值。根据分配器和 std::string 的实现方式，这可能会导致更大的内存消耗（考虑对齐）和缓存未命中。在此处查找并插入.

于 2013-06-26T07:56:47.780 回答
1

如果您可以选择使用 c++11，我建议您使用unordered_set它，因为它的性能应该比set. 如果这不是一个选项，请使用set. 没有理由map<string, bool>为此任务使用 a。

于 2013-06-26T07:59:48.357 回答
0

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

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.log的操作复杂度（在 map/set * n 项中插入）。map/set 解决方案为您提供2.n内存的2.n.log操作；使用算法通过n+n.log操作和1.n内存完成工作。

于 2013-06-26T10:52:35.547 回答