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

Question

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

A simple 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 () sets the size of the intersection. However, the intersection must be preserved, even if we do not do anything with it.

To avoid this, I tried to implement a dummy iterator output class, which only counts, but it does not 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); } }; 

with 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 the counter has the size of the intersection.

This is much more code. My questions:

1) Is there a standard (library) way or a standard trick to get the size of the intersection without saving the entire intersection? 2) Whether or not it exists, is the approach with a custom dummy iterator good?

Answer 1

It's not difficult to write a loop that moves through two sets looking for suitable elements, or you can do it, 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 can do it:

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

It is not optimally effective, but should be fast enough for most purposes.

Answer 3

You can simplify using your approach with a fair bit:

 struct counting_iterator { size_t count; counting_iterator& operator++() { ++count; return *this; } // other iterator stuff }; size_t count = set_intersection( s1.begin(), s1.end(), s2.begin(), s2.end(), counting_iterator()).count; 

Answer 4

It is impossible to write a function that does this. This shows how set_intersection is set_intersection [although the actual implementation may, of course, be slightly different)

So, we could just take this code and change it a bit:

 template <class InputIterator1, class InputIterator2> size_t set_intersection_size (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) { size_t result = 0; while (first1!=last1 && first2!=last2) { if (*first1<*first2) ++first1; else if (*first2<*first1) ++first2; else { result++; ++first1; ++first2; } } return result; } 

Although in my experience, when you want to know how many of them are at the intersection, you usually want to know sooner or later which elements too.