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是不可能的。

当然，这个例子对于map和unordered_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 回答