c++setset-union

find size of union of two sets?


Is there any way to find size of union of two sets. I know can do this

vector < int > s3( s1.size() , s2.size() ); 
auto it=set_union( s1.begin() , s1.end() , s2.begin() ,s2.end(), s3.begin());
int size = it - s3.begin();

print size

example

s1 = {2 4 5 6}   size 4

s2 = {1 4 5 9 10}  size 5

s3 = {1 2 4 5 6 9 10}  size 7

complexity of set_union is 2*(s1 size + s2 size)-1

Is there any other method to get size of union of two sets faster method, I just need the size do not want the values of new union set formed. If you know a faster method please suggest.


Solution

  • You can just put a counting iterator in last argument to set_union. E.g.

    int count = 0;
    it=set_union( s1.begin() , s1.end() , s2.begin() ,s2.end(), boost::make_function_output_iterator([&count](int){ ++count; })); 
    

    Or a non-boost equivalent of that output iterator

    struct counter {
        using difference_type = void;
        using value_type = void;
        using pointer = void;
        using reference = void;
        using iterator_category = std::output_iterator_tag;
        int count = 0;
        void operator&(int) { ++count }
        counter& operator++ { return *this; }
    };