为什么有人会使用set而不是unordered_set？

Question

C++ 0x正在引入unordered_set,可以在boost许多其他地方使用.我理解的是unordered_set具有O(1)查找复杂性的哈希表.另一方面,set只是具有log(n)查找复杂性的树.为什么人们会使用set而不是unordered_set？即是否需要set了？

Answer 1

无序集必须以几种方式支付其O(1)平均访问时间:

• set使用较少的内存而不是unordered_set存储相同数量的元素.
• 对于少量元素,a中的查找set可能比查找中的查找更快unordered_set.
• 尽管很多操作都在更快的平均情况为unordered_set,他们经常保证有更好的最坏情况复杂的set(例如insert).
• 这set 排序的元素,如果你想顺序访问它们是有用的.
• 您可以按字典顺序比较不同sets的<,<=,>和>=.unordered_sets不需要支持这些操作.

Answer 2

当对于想要迭代集合项目的人来说,顺序很重要.

Answer 3

每当您更喜欢树到哈希表时.

例如,在最坏的情况下,哈希表是"O(n)".O(1)是平均情况.树木最糟糕的是"O(log n)".

Answer 4

使用时设置:

1. 我们需要有序数据(不同的元素).
2. 我们必须打印/访问数据(按排序顺序).
3. 我们需要元素的前身/后继者.

在以下情况下使用unordered_set:

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

例子:

组:

输入:1,8,2,5,3,9

输出:1,2,3,5,8,9

Unordered_set:

输入:1,8,2,5,3,9

输出:9 3 1 8 2 5(也许这个顺序,受哈希函数的影响)

主要区别:

注意:(在某些情况下set更方便)例如使用vectoras键

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/ /sf/answers/2089918141/

Answer 5

抱歉，关于排序属性还有一件事值得注意：

如果您想要容器中的一系列数据，例如：您在set中存储了时间，并且您想要从 2013-01-01 到 2014-01-01 的时间。

对于unordered_set来说这是不可能的。

当然，对于map和unordered_map之间的使用案例，这个示例会更有说服力。

Answer 6

g++ 6.4 stdlibc++ 有序 vs 无序集合基准

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

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

“BST”的意思std::set是“用std::unordered_set. “堆”是std::priority_queue我分析的：堆与二叉搜索树（BST）

作为一个快速总结：

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

  这种速度提升的代价是您无法有效地按顺序遍历。

• 曲线清楚地表明orderedstd::set是基于BST的并且std::unordered_set是基于hashmap的。在参考答案中，我通过GDB一步调试代码进一步确认。

mapvs 的类似问题unordered_map：在关键的情况下，使用 map 比 unordered_map 有什么优势吗？

Answer 7

因为std :: set是标准C++的一部分而unordered_set不是.C++ 0x不是标准,也不是Boost.对于我们许多人来说,便携性是必不可少的,这意味着坚持标准.

Answer 8

考虑扫描线算法.这些算法将完全失败并使用哈希表,但与平衡树一起工作得非常漂亮.为了给你一个扫描线算法的具体例子,考虑一下fortune的算法.http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Answer 9

除了其他人已经提到的之外，还有一件事。虽然将元素插入到 unordered_set 的预期摊销复杂度是 O(1)，但它时不时地需要 O(n)，因为哈希表需要重组（桶的数量需要改变） - 即使有一个“好”的哈希函数。就像在向量中插入一个元素时不时需要 O(n) 一样，因为底层数组需要重新分配。

插入一个集合总是最多需要 O(log n)。这在某些应用中可能更可取。

Answer 10

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

如果散列函数是可预测的（这通常是这种情况，除非它应用随机盐等对策），攻击者可以手工制作产生散列冲突的数据，并导致所有插入和查找花费 O(n) 时间.

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

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

• Javascript
• PHP
• 爪哇