CODEWITHSUNDEEP
c++stlset
Pavel
Pavel

Reputation: 5876

Count elements in union of two sets using stl

I have two sets and I want to know how many elements there are at least in one set. It is a function set_union in <algorithm> which writes the union in another set, but I want only the number. Can I find it using stl without saving elements?

Upvotes: 2

Views: 850

Answers (3)

Ragnar
Ragnar

Reputation: 433

Although the solution by SCFrench is fine, it does require a container, while we only need a back_insert_iterator. Here is an example of an implementation.

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

template <typename T>
class count_back_inserter {
    size_t &count;
public:
    typedef void value_type;
    typedef void difference_type;
    typedef void pointer;
    typedef void reference;
    typedef std::output_iterator_tag iterator_category;
    count_back_inserter(size_t &count) : count(count) {};
    void operator=(const T &){ ++count; }
    count_back_inserter &operator *(){ return *this; }
    count_back_inserter &operator++(){ return *this; }
};

You can use it by passing a size_t variable to the constructor that will be incremented for every element that is 'added' to the 'underlying container'.

int main(){
    std::vector<int> v1 = {1, 2, 3, 4, 5}; 
    std::vector<int> v2 = {      3, 4, 5, 6, 7}; 
    size_t count = 0;
    set_union(v1.begin(), v1.end(),
              v2.begin(), v2.end(),
              count_back_inserter<int>(count));
    std::cout << "The number of elements in the union is " << count << std::endl;
}

Upvotes: 1

SCFrench
SCFrench

Reputation: 8374

I agree with Marshall Clow; I don't believe there is an off-the-shelf algorithm to do this. Here's an idea I've been toying with. It is a simple class that provides a push_back method that just increments a counter. You use it with a std::back_inserter as an output iterator.

#include <initializer_list>
#include <iterator>
#include <iostream>
#include <algorithm>

template <typename T>
class CountingPushBack
{
  public:
  using value_type = T;

  void push_back(T const &) {++count;}

  std::size_t get_count() const {return count;}

  private:
  std::size_t count = 0;
};

int main()
{
  std::initializer_list<int> il1 = { 0, 1, 2, 3, 4 };
  std::initializer_list<int> il2 = { 0, 2, 4, 6, 8 };

  CountingPushBack<int> cp;

  std::set_union(il1.begin(), il1.end(), 
                 il2.begin(), il2.end(), 
                 std::back_inserter(cp));

  std::cout << cp.get_count() << std::endl;
}

Upvotes: 5

Marshall Clow
Marshall Clow

Reputation: 16670

I don't know of such an algorithm. That being said, you can use the guts of set_union to write your own to do that; like this:

#include <iostream>
#include <set>

// Counts the number of elements that would be in the union
template <class Compare, class InputIterator1, class InputIterator2>
size_t set_union_size(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      Compare comp)
{
    size_t __result = 0;
    for (; first1 != last1;)
    {
        if (first2 == last2)
            return __result + std::distance(first1, last1);
        if (comp(*first2, *first1))
        {
            ++__result;
            ++first2;
        }
        else
        {
            ++__result;
            if (!comp(*first1, *first2))
                ++first2;
            ++first1;
        }
    }
    return __result + std::distance(first2, last2);
}

int main () {
    std::set<int> s1 = { 0, 1, 2, 3, 4 };
    std::set<int> s2 = { 0, 2, 4, 6, 8 };
    std::cout
        << set_union_size(s1.begin(), s1.end(), s2.begin(), s2.end(), std::less<int>())
        << std::endl;
    }

And this prints 7, which is what you would expect.

Upvotes: 1

Related Questions