180

C++0x 正在介绍unordered_set哪些在boost和许多其他地方可用。我的理解是具有查找复杂性unordered_set的哈希表。O(1)另一方面,set它只不过是一棵具有log(n)查找复杂性的树。为什么到底有人会使用set而不是unordered_set?即有没有必要set了?

4

13 回答 13

384

无序集必须通过以下几种方式为其 O(1) 平均访问时间付出代价:

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

于 2009-08-28T23:33:24.767 回答
251

什么时候,对于想要迭代集合中的项目的人来说,顺序很重要。

于 2009-08-28T22:45:12.680 回答
34

每当您喜欢树而不是哈希表时。

例如,哈希表在最坏的情况下是“O(n)”。O(1) 是平均情况。树在最坏的情况下是“O( log n)”。

于 2009-08-28T22:44:18.143 回答
25

在以下情况下使用 set:

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

在以下情况下使用 unordered_set:

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

例子:

放:

输入: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更方便)例如使用vectoras 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是因为vectoroverride 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

于 2018-09-06T12:17:06.197 回答
10

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

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

在此处输入图像描述

完整的基准测试详细信息和分析已在:C++ 中设置的 STL 的底层数据结构是什么?我不会在这里重复它们。

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

作为一个快速总结:

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

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

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

mapvs的类似问题unordered_map在微不足道的键的情况下,使用 map 而不是 unordered_map 有什么优势吗?

于 2019-04-04T08:21:19.787 回答
7

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

于 2009-08-28T22:47:15.920 回答
7

考虑扫描线算法。这些算法在哈希表上会完全失败,但在平衡树上工作得很好。为了给你一个扫描线算法的具体例子,请考虑财富算法。http://en.wikipedia.org/wiki/Fortune%27s_algorithm

于 2009-09-02T08:00:34.433 回答
6

虽然这个答案可能晚了 10 年,但值得指出的是,它std::unordered_set也存在安全问题。

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

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

许多(大多数?)内部使用哈希映射的语言实现都遇到了这种情况:

于 2019-11-21T14:44:07.747 回答
5

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

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

于 2011-03-14T15:29:24.290 回答
5

请原谅我,关于 sorted 属性还有一件事值得注意:

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

对于unordered_set是不可能的。

当然,这个例子对于mapunordered_map之间的用例会更有说服力。

于 2015-02-03T19:23:28.863 回答
2

顺便说一句,如果您希望将其转换为不同的格式,那么将事物置于关系中会很方便。

也有可能,虽然访问速度更快,但构建索引的时间或创建和/或访问它时使用的内存更长。

于 2009-08-28T22:44:08.923 回答
2

如果您想对事物进行排序,那么您将使用 set 而不是 unordered_set。当排序存储无关紧要时,unordered_set 被过度使用。

于 2009-08-28T22:46:45.250 回答
1

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

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

因此,对于程序员来说,无序集比有序集更难理解。他们引入了这种额外的机制来混淆代码行为,这可能导致耗时/令人困惑的错误,因为它们可能无法在机器之间重现。

于 2021-08-04T22:35:47.540 回答