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

Question

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

Answer 1

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

Answer 2

如果你想要对事物进行排序，那么你将使用set而不是unordered_set。当存储的顺序无关紧要时，unordered_set用于set。

Answer 3

g++ 6.4 stdlibc ++ ordered vs unordered set benchmark

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

完整的基准细节和分析已在：What is the underlying data structure of a STL set in C++?给出，我在此不再重复。

快速总结一下：

• 该图清楚地表明，在这些条件下，当存在超过10万个项目时，hashmap插入总是快得多，并且随着项目数量的增加，差异会增加 这种速度提升的代价是您无法有效地遍历。
• 曲线清楚地表明有序std::set是基于BST的，而std::unordered_set是基于hashmap的。在参考答案中，我进一步确认通过GDB步骤调试代码。

结果如下所示。 “BST”表示“使用std::set进行测试，”哈希图“表示”使用std::unordered_set进行测试。 “堆”是std::priority_queue，我在Heap vs Binary Search Tree (BST)分析

类似的问题map vs unordered_map：Is there any advantage of using map over unordered_map in case of trivial keys?

Answer 4

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

• set使用比unordered_set更少的内存来存储相同数量的元素。
• 对于少量元素，set中的查找可能比unordered_set中的查找更快。
• 尽管unordered_set的平均情况下许多操作更快，但它们通常保证set具有更好的最坏情况复杂性（例如insert）。
• 如果您想按顺序访问它们，set对元素进行排序很有用。
• 您可以按字典比较不同的sets与<，<=，>和>=。 unordered_sets不需要支持这些操作。

Answer 5

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

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

Answer 6

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

Answer 7

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

Answer 8

使用时设置：

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更方便）例如使用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

Answer 9

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

插入集合总是最多需要O（log n）。在某些应用中这可能更为可取。

Answer 10

请原谅我，还有一件事需要注意有关排序的属性：

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

对于unordered_set，这是不可能的。

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

Answer 11

另外，如果你想将它转换成不同的格式，我会说在关系中有事情很方便。

也有可能的是，当访问速度更快时，构建索引的时间或创建和/或访问索引时使用的内存更大。