为什么unordered_map和unordered_set慢些？

Question

我在解决一个简单的问题，就是在数组中找到唯一的元素。我使用std::unordered_map来计数唯一的元素，但在一个测试用例中，它给出了超过的时间限制。然后，我使用了一个具有相同结果的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_set<int>是一个基于节点的容器，每个元素都存储在单独分配的列表节点中.列表节点包含一个int元素和两个列表节点指针，在64位平台上，由于对齐，每个列表节点占用24个字节。每个分配的内存块( GNU为8个字节)也有分配程序开销，因此每个4字节int元素至少有28个字节的开销。

s.insert(a);为每个新元素分配内存，这就是导致代码变慢的原因。

为了有效地解决这个问题，您可以使用整数索引的位集，例如std::vector<bool>。将每个读取整数的位设置为1，然后计数Set位数。如果元素是有符号的，则将它们隐藏为无符号，以使位索引成为非负数。

一个有用的例子：

#include <vector>
#include <iostream>
#include <numeric>
#include <limits>

int main() {
    int n;
    std::cin >> n;
    std::vector<bool> bitset(1000000001); // a range is 1≤a≤10^9.

    for(int i = 0, a; i < n; ++i) {
        std::cin >> a;
        bitset[static_cast<unsigned>(a)] = true;
    }
    std::cout << std::accumulate(bitset.begin(), bitset.end(), 0u) << '\n';
}

通过那个评分器的版本：

#include <bitset>
#include <iostream>
#include <numeric>
#include <limits>

int main() {
    int n;
    std::cin >> n;
    std::bitset<1000000001> bitset; // a range is 1≤a≤10^9.
    unsigned unique = 0;
    for(int i = 0, a; i < n; ++i) {
        std::cin >> a;
        if(!bitset.test(a)) {
            ++unique;
            bitset.set(a);
        }
    }
    std::cout << unique << '\n';
}

Answer 2

std::unordered_map在大多数情况下给出了o(1)的结果，但并不总是这样。谈到TLE问题，可能存在约束大于10^18的可能性，在这种情况下，o(n)复杂性将无法工作。尝试o(log(n))方法。

Answer 3

无序容器是为检索值而不是为插入值而优化的。

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

但是，您可以通过首先分配内存来解决这个问题，这样就可以减少冲突。