How to compute the size of an intersection of two STL sets in C++

It's not difficult to write a loop that moves through the two sets looking for matching elements, or you could do this, which is much simpler than a custom iterator:

struct Counter
{
  struct value_type { template<typename T> value_type(const T&) { } };
  void push_back(const value_type&) { ++count; }
  size_t count = 0;
};

template<typename T1, typename T2>
size_t intersection_size(const T1& s1, const T2& s2)
{
  Counter c;
  set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(c));
  return c.count;
}

You could do this:

auto common = count_if(begin(s1), end(s1), [&](const auto& x){ return s2.find(x) != end(s2); });

It's not optimally efficient but should be fast enough for most purposes.


You can simplify the usage of your approach a fair bit:

struct counting_iterator
{
    size_t count;
    counting_iterator& operator++() { ++count; return *this; }

    struct black_hole { void operator=(T) {} };
    black_hole operator*() { return black_hole(); }

    // other iterator stuff may be needed
};

size_t count = set_intersection(
  s1.begin(), s1.end(), s2.begin(), s2.end(), counting_iterator()).count;

Tags:

Algorithm

C++

Stl