Why/Are 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(1) 的结果。谈到 TLE 问题，约束可能超过 10^18，在这种情况下，o(n) 复杂度将不起作用。尝试 o(log(n)) 方法。

Answer 2

无序容器针对检索值进行了优化，而不是针对插入值进行了优化。

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

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

Answer 3

std::unordered_set<int> 是一个基于节点的容器，其中每个元素都存储在单独分配的列表节点中。列表节点包含一个int元素和两个列表节点指针，在64位平台上，由于对齐，每个列表节点占用24个字节。每个分配的内存块（GNU libc 为 8 字节）也有分配器开销，因此每个 4 字节 int 元素至少有 28 字节的开销。

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

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

一个工作示例：

#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';
}

Why/Are unordered_map 和 unordered_set 比较慢？

Why/Are unordered_map and unordered_set slower?

c++

unordered-map

stdmap

unordered-set

stdset

我的问题是：