CODEWITHSUNDEEP
c++stlcountset-difference
gudge
gudge

Reputation: 1073

Count the number of elements different in one set than the other

The set_difference algorithm gives you output of elements which are in the first range and not in second. Is there a algorithm which will just give me the count and not the difference.

I understand I can implement my own version of the algorithm described in the link or I can count the number of elements after I get the result. Is there a existing API which will do it for me efficiently.

Thanks

Upvotes: 1

Views: 533

Answers (3)

Barry
Barry

Reputation: 302757

You could simply write your own OutputIterator-like thing that you could pass into std::set_difference. An OutputIterator needs to be dereferencable, assignable, and incrementable. Note also that std::set_difference returns an OutputIterator, so we can take advantage of that by making it convertible to int.

Hence something like:

struct CountingIterator
    : std::iterator<std::output_iterator_tag, int>
{
    template <typename T>
    CountingIterator& operator=(T&& ) {
        ++count;
        return *this;
    }

    CountingIterator& operator*() { return *this; }
    CountingIterator& operator++() { return *this; }

    operator int() { return count; }

    int count = 0;
};

Which, when modifying the example in std::set_difference yields:

int main() {
    std::vector<int> v1 {1, 2, 5, 5, 5, 9};
    std::vector<int> v2 {2, 5, 7};

    int count = 
        std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), 
                        CountingIterator());

    std::cout << count << std::endl; // prints 4
}

Upvotes: 1

Jarod42
Jarod42

Reputation: 217135

You may create an "CountingIterator" as OutputIterator, something like:

struct CountingIterator
{
    CountingIterator& operator*() { return *this; }  

    CountingIterator& operator ++() { return *this; }
    CountingIterator& operator ++(int) { return *this; }

    template <typename T>
    CountingIterator& operator =(const T&) { ++counter; return *this; }

    int counter = 0;
};

Upvotes: 0

Jack
Jack

Reputation: 133567

It's an operation such trivial that doesn't require a specific method. If you can't afford to allocate a temporary set to compute the difference and then get their size, just compute it with std::accumulate or std::for_each:

unordered_set<int> set1 = {1,2,3,4,5};
unordered_set<int> set2 = {2,4,6};    
size_t count = set1.size() - std::accumulate(set1.begin(), set1.end(), 0, [&set2](size_t previous, int value) { return set2.count(value) + previous; });

But if you don't have any specific requirement or huge sets doing set_difference + size() is just fine.

Upvotes: 0

Related Questions