为什么unordered_map和unordered_set较慢？

Question

我正在解决一个简单的问题，即在数组中查找唯一元素。我使用std::unordered_map来计算唯一元素，但在一个测试用例中给出了Time Limit Exceeded。然后，我使用了std::unordered_set，结果相同。

PS：我使用了std::unordered_map和std::unordered_set，因为我读到这两个分别比std::map和std::set快得多。

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, a;
    cin >> n;
    unordered_set<int> s;

    for(int i = 0; i < n; i++) {
        cin >> a;
        s.insert(a);
    }
    cout << s.size();
}

测试7超过了时间限制。

我的问题是：

如果std::unordered_map和std::unordered_set更快，为什么要赋予TLE？

Answer 1

std::unordered_map在大多​​数情况下会得到o（n）的结果，而并非总是如此。谈到TLE问题，约束可能会超过10 ^ 18，在这种情况下，o（n）复杂性将无法工作。尝试o（log（n））方法。

Answer 2

要解决此问题，您可以使用由整数索引的位集，例如std::vector<bool>。将每个读取的整数的位设置为1，然后计算设置的位数。

Answer 3

无序容器被优化用于检索值，而不是用于插入它们。

您可以看一下此比较https://medium.com/@nonuruzun/stl-container-performance-3ec5a8fbc3be。在那里，您可以看到无序容器的插入最坏情况为O（N），而有序容器的插入情况为O（log（N））

但是您可以通过首先分配内存来解决此问题，因此冲突更少。