I have two unordered_set and want the intersection of those. I can't find a library function to do that.
Essentially, what I want is this:
unordered_set<int> a = {1, 2, 3};
unordered_set<int> b = {2, 4, 1};
unordered_set<int> c = a.intersect(b); // Should be {1, 2}
I can do something like
unordered_set<int> c;
for (int element : a) {
if (b.count(element) > 0) {
c.insert(element);
}
}
However, I think there should be a more convenient way to do that. If there isn't one, can someone explain why? I know there is std::set_intersection
, but that seems to operate on vectors only.
In fact, a loop-based solutions is the best thing you can use with std::unordered_set
.
There is an algorithm called std::set_intersection
which allows to find an intersection of two sorted ranges:
Constructs a sorted range beginning at d_first consisting of elements that are found in both sorted ranges [first1, last1) and [first2, last2).
As you deal with std::unordered_set
, you cannot apply this algorithm because there is no guaranteed order for the elements in std::unordered_set
.
My advice is to stick with loops as it explicitly says what you want to achieve and has a linear complexity (O(N), where N is a number of elements in the unordered set you traverse with a for loop) which is the best compexity you might achieve.