C++0x 正在介绍unordered_set
哪些在boost
和许多其他地方可用。我的理解是具有查找复杂性unordered_set
的哈希表。O(1)
另一方面,set
它只不过是一棵具有log(n)
查找复杂性的树。为什么到底有人会使用set
而不是unordered_set
?即有没有必要set
了?
13 回答
无序集必须通过以下几种方式为其 O(1) 平均访问时间付出代价:
set
比存储相同数量的元素使用更少的内存。unordered_set
- 对于少量元素,在 a 中查找
set
可能比在 an中查找更快unordered_set
。 - 尽管在 的平均情况下许多操作更快
unordered_set
,但通常保证它们具有更好的最坏情况复杂性(set
例如insert
)。 - 如果您想按顺序访问元素,那么
set
对元素进行排序很有用。 - 您可以按字典顺序将不同
set
的 s 与<
、<=
和>
进行比较>=
。unordered_set
s 不需要支持这些操作。
什么时候,对于想要迭代集合中的项目的人来说,顺序很重要。
每当您喜欢树而不是哈希表时。
例如,哈希表在最坏的情况下是“O(n)”。O(1) 是平均情况。树在最坏的情况下是“O( log n)”。
在以下情况下使用 set:
- 我们需要有序的数据(不同的元素)。
- 我们必须打印/访问数据(按排序顺序)。
- 我们需要元素的前任/继任者。
在以下情况下使用 unordered_set:
- 我们需要保留一组不同的元素,并且不需要排序。
- 我们需要单元素访问,即没有遍历。
例子:
放:
输入:1、8、2、5、3、9
输出:1、2、3、5、8、9
无序集:
输入:1、8、2、5、3、9
输出:9 3 1 8 2 5(可能是这个顺序,受哈希函数影响)
主要区别:
注意:(在某些情况下set
更方便)例如使用vector
as key
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>
可以作为 key inset
是因为vector
override operator<
。
但是如果你使用unordered_set<vector<int>>
你必须创建一个散列函数vector<int>
,因为向量没有散列函数,所以你必须定义一个像:
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++ 有序集 vs 无序集基准
我对这个占主导地位的 Linux C++ 实现进行了基准测试以查看差异:
完整的基准测试详细信息和分析已在:C++ 中设置的 STL 的底层数据结构是什么?我不会在这里重复它们。
“BST”的意思std::set
是“用std::unordered_set
. “堆”是std::priority_queue
我分析的:堆与二叉搜索树(BST)
作为一个快速总结:
该图清楚地表明,在这些条件下,当项目超过 100k 时,hashmap 插入总是快得多,并且差异随着项目数量的增加而增长
这种速度提升的代价是您无法有效地按顺序遍历。
曲线清楚地表明,ordered
std::set
是基于 BST 并且std::unordered_set
是基于 hashmap 的。在参考答案中,我进一步确认了通过 GDB 一步调试代码。
map
vs的类似问题unordered_map
:在微不足道的键的情况下,使用 map 而不是 unordered_map 有什么优势吗?
因为 std::set 是标准 C++ 的一部分,而 unordered_set 不是。C++0x 不是标准,Boost 也不是。对于我们中的许多人来说,可移植性是必不可少的,这意味着要坚持标准。
考虑扫描线算法。这些算法在哈希表上会完全失败,但在平衡树上工作得很好。为了给你一个扫描线算法的具体例子,请考虑财富算法。http://en.wikipedia.org/wiki/Fortune%27s_algorithm
虽然这个答案可能晚了 10 年,但值得指出的是,它std::unordered_set
也存在安全问题。
如果散列函数是可预测的(除非它应用随机盐等反措施,否则通常是这种情况),攻击者可以手工制作产生散列冲突并导致所有插入和查找花费 O(n) 时间的数据.
这可以用于非常有效和优雅的拒绝服务攻击。
许多(大多数?)内部使用哈希映射的语言实现都遇到了这种情况:
除了其他人已经提到的之外,还有一件事。虽然将元素插入 unordered_set 的预期摊销复杂度为 O(1),但有时会花费 O(n),因为需要重组哈希表(需要更改存储桶的数量)——即使使用一个“好”的哈希函数。就像在向量中插入一个元素时不时地需要 O(n),因为底层数组需要重新分配。
插入一个集合总是最多需要 O(log n)。这在某些应用程序中可能更可取。
请原谅我,关于 sorted 属性还有一件事值得注意:
如果您想要容器中的一系列数据,例如:您将时间存储在set中,并且您想要从 2013-01-01 到 2014-01-01 的时间。
对于unordered_set是不可能的。
当然,这个例子对于map和unordered_map之间的用例会更有说服力。
顺便说一句,如果您希望将其转换为不同的格式,那么将事物置于关系中会很方便。
也有可能,虽然访问速度更快,但构建索引的时间或创建和/或访问它时使用的内存更长。
如果您想对事物进行排序,那么您将使用 set 而不是 unordered_set。当排序存储无关紧要时,unordered_set 被过度使用。
这是我没有看到列出的一个实际原因......如果在错误代码中使用不正确,无序集可能会导致代码在不同机器上表现不同。这是因为值的存储顺序在机器之间不一致。
如果(错误地)编写依赖于存储顺序的代码,结果将是程序在不同机器之间的行为不一致。实际上,如果无序集是返回值列表的函数/方法的实现的一部分,则可能会发生这种情况。该函数的客户端可能没有意识到正在使用无序集,并且可能没有意识到返回列表的顺序不能保证是一致的/可移植的。
因此,对于程序员来说,无序集比有序集更难理解。他们引入了这种额外的机制来混淆代码行为,这可能导致耗时/令人困惑的错误,因为它们可能无法在机器之间重现。