C++ library method for intersection of two unordered_set

Question

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.

Answer 1

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.

Answer 2

As the accepted answer explains, there is nothing that directly does what you want, and std::set_intersection isn't intended for intersection std::unordered_sets, even though it sounds like it. The ideal solution depends on the C++ standard you're using.

Given two sets std::unordered_set<T> a, b; ...

In-place

... the best method to turn a into the intersection a & b is as follows:

// C++20 (needs <unordered_set>)
std::erase_if(a, [&b](int e) {
    return !b.contains(e);
});

// C++11 (needs <unordered_set>)
for (auto it = a.begin(); it != a.end();) {
    if (!b.count(*a)) { it = a.erase(it); }
    else              { ++it; }
}

Non-modifying

Alternatively, to compute a new set c which contains the intersection of a and b:

// C++23 (needs <unordered_set>, <ranges>)
std::unordered_set<int> c(std::from_range, a | std::views::filter([&b](int e) {
    return b.contains(e);
});

// C++20 (needs <unordered_set>, <ranges>)
auto view = a | std::views::filter([&b](int e) {
    return b.contains(e);
};
std::unordered_set<int> c(view.begin(), view.end());

// C++11 (needs <unordered_set>)
std::unordered_set<int> c;
// TODO: consider reserving a size (optimistically |a| + |b|)
for (int e : a) {
    if (b.count(e)) { a.insert(e); }
}

Answer 3

There is a function from std called set_intersection. However, it would have a very high complexity using it with std::set as input parameter.. A better solution is, create two vectors from those sets and use set_intersection with vectors as input parameters.