Why/Are unordered_map and unordered_set slower?

Question

I was solving a simple problem of finding unique elements in an array. I used a std::unordered_map to count unique elements but it gave Time Limit Exceeded in one test case. Then I used a std::unordered_set with the same result.

PS: I used std::unordered_map and std::unordered_set because I read that these two are much much faster than std::map and std::set respectively.

#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();
}

Test 7 exceeded the time limit.

My Question is:

If std::unordered_map and std::unordered_set are faster why did they give TLE?

Answer 1

std::unordered_set<int> is a node-based container, where each element is stored in separately allocated list node. The list node contains an int element and two list node pointers, which, on a 64-bit platform, makes each list node occupy 24 bytes due to alignment. There is also allocator overhead for each allocated chunk of memory (8 bytes for GNU libc), so that there is at least 28 bytes of overhead for each 4-byte int element.

s.insert(a); makes a memory allocation for each new element and that is what makes the code slow.

---

To solve this problem efficiently you can use a bitset indexed by the integers, e.g. std::vector<bool>. Set the bit to 1 for each read integer and then count the number of set bits. If the elements are signed, covert them to unsigned to make the bit index a non-negative number.

A working example:

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

---

A version that passes that grader:

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