为什么会有人使用集合而不是无序_集合？

C++0x引入了unordered_set，它可以在_、ABC_1和许多其他地方使用。我所理解的是，unordered_set是具有O(1)查找复杂度的哈希表。另一方面，set只不过是具有log(n)查找复杂度的树。究竟为什么有人会使用set而不是_ABC_0？即，是否还需要set？

92504 次浏览
小开

现在，我想说的是，如果你想把它转换成一种不同的格式，那么在一段关系中拥有东西是很方便的。

还可能的是，虽然访问速度更快，但建立索引的时间或创建和/或访问索引时使用的内存更多。

小开

无论何时你更喜欢树而不是哈希表。

例如，哈希表在最坏的情况下是“ O（n）”。O（1）是平均情况。树在最坏的情况下是“ O（木头原木N）”。

小开
最佳答案

对于想要对集合中的项目进行迭代的人来说，顺序很重要。

小开

如果你想把东西排序，那么你应该使用集合而不是无序_集合。当存储顺序无关紧要时，无序_SET用于SET.

小开

因为STD：set是标准C++的一部分，而无序_set不是。C++0x 不是标准，Boost也不是。对于我们中的许多人来说，可移植性是必不可少的，这意味着坚持标准。

小开

无序集必须以几种方式为其O（1）平均访问时间付出代价：

  • set使用更少的内存而不是unordered_set来存储相同数量的元素。
  • 对于少量元素，set中的查找可能比unordered_set中的查找再快点。
  • 即使对于unordered_set，许多操作在一般情况中更快，但是通常保证它们对于set具有更好的最坏情况复杂性（例如insert）。
  • 如果要按顺序访问set对元素进行排序，则它们非常有用。
  • 您可以使用<、<=、>和>=来按字典顺序比较个不同的set。unordered_set不是支持这些操作所必需的。

小开

请考虑使用Sweepline算法。这些算法在使用哈希表时会彻底失败，但在使用平衡树时却能完美地工作。为了给出一个扫描线算法的具体例子，考虑一下福琼算法，http://en.wikipedia.org/wiki/Fortune%27s_algorithm。

小开

还有一件事，除了其他人已经提到的。虽然将元素插入无序_集合的预期分摊复杂度为O（1），但由于哈希表需要重新构造（桶的数量需要改变），即使使用“良好”的哈希函数，它也会不时地将为O（n）。就像在向量中插入一个元素一样，每隔一段时间就会花费O（n），因为底层数组需要重新分配。

在集合中插入总是最多花费O（log n）。这在某些应用中可能是优选的。

小开

对不起，关于已分类的财产，还有一件事值得注意：

如果要获取container中的一系列数据，例如：设置中存储了时间，则需要2013-01-01到2014-01-01之间的时间。

对于无序_集，这是不可能的。

当然，此示例对于地图和无序_映射之间的使用情况更有说服力。

小开

在以下情况下使用SET：

  1. 我们需要有序数据（不同的元素）。
  2. 我们必须打印/访问数据（按排序顺序）。
  3. 我们需要元素的前驱/后继。

在以下情况下使用无序_集：

  1. 我们需要保留一组不同的元素，并且不需要排序。
  2. 我们需要单元素访问，即没有遍历。

示例：

设置:

输入：1，8，2，5，3，9

产量：1，2，3，5，8，9

无序_集：

输入：1，8，2，5，3，9

输出：931825（可能是这个顺序，受哈希函数的影响）

主要区别：

enter image description here

注：（在某些情况下，set更方便）例如，使用vector作为键

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});


for(const auto& vec:s)
cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3

vector<int>可以作为set中的关键字的原因是vector覆盖operator<。

但是，如果您使用unordered_set<vector<int>>，则必须为vector<int>创建一个哈希函数，因为Vector没有哈希函数，所以您必须定义一个类似如下的函数：

struct VectorHash {
size_t operator()(const std::vector<int>& v) const {
std::hash<int> hasher;
size_t seed = 0;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
return seed;
}
};


vector<vector<int>> two(){
//unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
unordered_set<vector<int>, VectorHash> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});


for(const auto& vec:s)
cout<<vec<<endl;
// 1 2
// 1 3
}

您可以看到，在某些情况下，unordered_set更为复杂。

主要引自： https：//www.geeksforgeeks.org/set-vs-unordered_set-c-stl/. https://stackoverflow.com/a/29855973/6329006

小开

g++6.4 Stdlibc++有序集与无序集比较

我对这个占主导地位的Linux C++实现进行了基准测试，以了解其差异：

enter image description here

完整的基准详细信息和分析已在以下位置给出：在C++中，STL集合的底层数据结构是什么？，我不会在这里重复它们。

“ BST ”表示“用std::set测试”，而“哈希映射”表示“用std::unordered_set测试”。“ Heap ”表示std::priority_queue，我在堆与二叉搜索树（BST）中对其进行了分析。

简单总结一下：

  • 该图清楚地表明，在这些条件下，当项目超过100K时，HashMap插入总是快得多，并且差异随着项目数量的增加而增加。

    这种速度提升的代价是你不能有效地按顺序遍历。

  • 曲线清楚地表明，有序std::set是基于BST的，而std::unordered_set是基于HashMap的。在参考答案中，我进一步确认了由GDB一步一步调试的代码。

map与unordered_map的类似问题：在普通密钥的情况下，使用Map是否比无序_Map更有优势？

小开

虽然这个答案可能晚了10年，但值得指出的是，std::unordered_set也有安全方面的缺点。

如果哈希函数是可预测的（这是典型的情况，除非它应用诸如随机化SALT之类的对抗措施），则攻击者可以手工创建产生哈希冲突的数据，并导致所有插入和查找花费O（n）时间。

这可以用于非常高效和优雅的拒绝服务攻击。

许多（大多数？）内部使用哈希映射的语言实现都会遇到这种情况：

小开

这里有一个实际原因，我还没有看到列出..如果在错误代码中使用不当，无序集可能会导致代码在不同的机器上表现不同。这是因为存储值的顺序在计算机之间不一致。

如果（错误地）编写了依赖于存储顺序的代码，结果将是程序在不同机器之间的行为不一致。实际上，如果无序集是返回值列表的函数/方法的实现的一部分，则可能发生这种情况。该函数的客户端可能没有意识到正在使用无序集，并且可能没有意识到返回列表的顺序不能保证是一致的/可移植的。

因此，对程序员来说，无序集比有序集更不宽容。他们引入了这种额外的机制来混淆代码行为，这可能会导致耗时/令人困惑的错误，因为它们可能无法在机器之间复制。


提交答案