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

Question

I am given two sets (std::set from <set>) of which I'd like to know the size of the intersection. I could use std::set_intersection from <algorithm>, but I have to provide it an output iterator to copy the intersection into some other container.

A straightforward way would be

  set<int> s1{1,2,3,4,5};
  set<int> s2{4,5,6,7,8,9,0,1};

  vector<int> v;

  set_intersection(
      s1.begin(), s1.end(), s2.begin(), s2.end(),
      inserter(v, v.begin()));

after which v.size() gives the size of the intersection. However, the intersection will have to be stored as well, even though we don't do anything with it.

To avoid that, I tried to implement a dummy output iterator class, which only counts, but it doesn't assign:

template<typename T>
class CountingOutputIterator {
 private:
  int* counter_;
  T dummy_;
 public:
  explicit CountingOutputIterator(int* counter) :counter_(counter) {}
  T& operator*() {return dummy_;}
  CountingOutputIterator& operator++() { // ++t
    (*counter_)++;
    return *this;
  }
  CountingOutputIterator operator++(int) { // t++
    CountingOutputIterator ret(*this);
    (*counter_)++;
    return ret;
  }
  bool operator==(const CountingOutputIterator& c) {
    return counter_ == c.counter_; // same pointer
  }
  bool operator!=(const CountingOutputIterator& c) {
    return !operator==(c);
  }
};

using which we could do

  set<int> s1{1,2,3,4,5};
  set<int> s2{4,5,6,7,8,9,0,1};

  int counter = 0;
  CountingOutputIterator<int> counter_it(&counter);
  set_intersection(
      s1.begin(), s1.end(), s2.begin(), s2.end(), counter_it);

after which counter holds the size of the intersection.

This is much more code however. My questions are:

1) Is there a standard (library) way or a standard trick to obtain the size of the intersection without storing the whole intersection? 2) Independent of whether or not there is, is the approach with the custom dummy iterator a good one?

Answer 1

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

Answer 2

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.