# C++ unordered_set is so much slower than vector

• Completely same code.
If I use `unordered_set`, although I have the advantage of removing used edges to reduce iteration time in next loop, the performance isn't satisfactory at all.

66 / 66 test cases passed
Status: Accepted
Runtime: 169 ms
Beats 35.44%

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n < 2) return vector<int>(n);
vector<unordered_set<uint>> neighbor(n);
vector<uint> degree(n, 0);
vector<uint> leaf(n);
vector<uint>::iterator p = leaf.begin(), q = p, e = leaf.end();
for (auto& i : edges) {
neighbor[i.first].insert(i.second);
neighbor[i.second].insert(i.first);
degree[i.first]++;
degree[i.second]++;
}
for (uint i = 0; i < n; i++) {
if (degree[i] < 2) *(p++) = i;
}
while (p != e) {
for (auto qq = p ; q != qq; q++) {
for (uint nbr : neighbor[*q]) {
neighbor[nbr].erase(*q);
if (degree[nbr]-- == 2) *(p++) = nbr;
}
}
}
return vector<int>(q, e);
}
};
``````

Then if I use `vector`, which means I can't easily remove used edges, so there should be quite a few redundant loops, yet I get a huge unexpected performance boost.

66 / 66 test cases passed
Status: Accepted
Runtime: 66 ms
Beats 99.18%

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n < 2) return vector<int>(n);
vector<vector<uint>> neighbor(n);
vector<uint> degree(n, 0);
vector<uint> leaf(n);
vector<uint>::iterator p = leaf.begin(), q = p, e = leaf.end();
for (auto& i : edges) {
neighbor[i.first].push_back(i.second);
neighbor[i.second].push_back(i.first);
degree[i.first]++;
degree[i.second]++;
}
for (uint i = 0; i < n; i++) {
if (degree[i] < 2) *(p++) = i;
}
while (p != e) {
for (auto qq = p ; q != qq; q++) {
for (uint nbr : neighbor[*q]) {
if (degree[nbr]-- == 2) *(p++) = nbr;
}
}
}
return vector<int>(q, e);
}
};
``````

I suspect it is due to the fact when the number of nodes grows, the collisions happen so frequent that `unordered_set` degenerates from O(1) to O(n).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.