c++ - 集合 vs 无序集合！哪个更好用？

Question

我必须在 n 个元素的列表中找到唯一元素的数量。我已经使用了 set 并且它被接受了，但是当我在其中一种情况下使用 unordered_set 时超出了时间限制。这怎么可能？

使用集合的代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
set<int> s;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
s.insert(x);
}
cout << s.size() << "\n";
return 0;
}

使用 Unordered_set 的代码

#include <bits/stdc++.h>
 using namespace std;
 int main()
 {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 unordered_set<int> s;
 int n;
 cin >> n;
 for (int i = 0; i < n; i++)
 {
 int x;
 cin >> x;
 s.insert(x);
 }
 cout << s.size() << "\n";
 return 0;
 }

Answer 1

set在内部使用红黑树，因此它像 a 一样在内部进行操作BST，并且在任何情况下它都会进行 balanced tree 搜索 logarithmic time ，但是插入到 a 中unordered_set 取决于所使用的数据和实际确定的“内部哈希函数”哈希集中的冲突数量，因此可能由于特定输入导致的冲突数量较多，它可能无法处理大量冲突，因为冲突处理也需要时间，因为它可能使用任何2 标准方法

Answer 2

unordered_set insert() 操作的最坏情况时间复杂度为 O(n)，而在 ordered_set 的情况下，时间复杂度为 O(log(n))，因为它在每次操作后保持自平衡 BST。我建议您通过 CPP-reference 阅读以下文档，您可以找到与 c++ 相关的所有信息。

参考：对于 unordered_set:insert()

(1) https://en.cppreference.com/w/cpp/container/unordered_set/insert

对于ordered_set:insert()

(2) https://en.cppreference.com/w/cpp/container/set/insert

希望这有帮助..快乐编码..

Answer 3

测试用例包含的值散列非常严重，有很多冲突。
插入的最坏情况复杂度unordered_set与集合的大小成线性关系。在最坏的情况下，
插入 a是对数的。set