为什么会有人使用集合而不是无序集合?

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

• set 使用 比 unordered_set 存储相同数量的元素。
• 暂时 少量元素 设置 可能是 而不是在 .
• 尽管在未来的几年中,许多操作速度更快 一般情况 无序集 更好的最坏情况复杂性 对于 设置 (例如 insert
• 那个 设置
• 你可以 词典比较 不同的 设置 < , <= > 和 >= 无序集 支持这些操作不需要使用。

当某人想要迭代集合中的项目时,顺序很重要。

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

在以下情况下使用set:

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

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

设置:

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

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

无序集:

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

主要区别是:

注:(在某些情况下) 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> 可以作为键输入 设置 因为 operator<

unordered_set<vector<int>> 您必须为其创建一个哈希函数 向量<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++有序与无序集基准测试

我对这个主流的Linux C++实现进行了基准测试,以看出不同之处:

完整的基准详情和分析见: What is the underlying data structure of a STL set in C++?

“BST”是指“使用 std::set “散列映射”是指“使用 std::unordered_set std::priority_queue 我在以下网站上分析: Heap vs Binary Search Tree (BST)

简要总结如下:

• 该图清楚地显示,在这些条件下,当项目数超过100k时,hashmap插入总是快得多,并且随着项目数的增加,差异也会增大

  这一速度提升的代价是你无法按顺序高效地穿越。

• std::set 是基于hashmap的。在参考答案中,我进一步确认了通过GDB步骤调试代码。

map vs unordered_map : Is there any advantage of using map over unordered_map in case of trivial keys?

因为STD::SET是标准C++的一部分,而无序的集合不是。C++0x

考虑扫描算法。这些算法在使用哈希表时会完全失败,但在使用平衡树时效果很好。给你一个具体的例子,一个扫尾算法考虑财富的算法。 http://en.wikipedia.org/wiki/Fortune%27s_algorithm

除了其他人已经提到的以外,还有一件事。虽然将元素插入无序_集的预期摊销复杂度为O(1),但有时它会 以O(n)为例,因为哈希表需要重新构造(bucket的数量需要改变)——即使使用“良好”的哈希函数也是如此。就像在向量中插入一个元素一样,有时需要O(n),因为底层数组需要重新分配。

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

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

许多(大多数?)内部使用哈希映射的语言实现都遇到了以下问题:

• Javascript
• PHP
• Java

对不起,关于排序属性,还有一件事值得注意:

如果你愿意 一系列数据 在容器中,例如:您将时间存储在

对于 这是不可能的。

当然,这个例子对于两个用户之间的用例更具说服力 地图 无序地图 .

如果您想对事物进行排序,那么可以使用set而不是unordered_set。当存储的顺序无关紧要时,无序_集合用于集合之上。

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

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