how to compare two std::set?

Question

I do such comparison of two std::set

#include <cstdlib>
#include <cstdio>
using namespace std;

#include <vector>
#include <set>


int main(int argc, char** argv)
{
    int myints1[]= {10,20,30,40,50};
    int myints2[]= {50,40,30,20,10};
    std::set<int> s1 (myints1,myints1+5);
    std::set<int> s2(myints2,myints2+5);
    if(s1==s2){
        printf("sets: true");
    }else printf("sets: false");
    std::set<int>::iterator it2=s2.begin();
    for(std::set<int>::iterator it1=s1.begin();it1!=s1.end();it1++){
                printf("\ns1: %d  s2: %d",*it1,*it2);
        it2++;
    }
}

output:

sets: true
s1: 10  s2: 10
s1: 20  s2: 20
s1: 30  s2: 30
s1: 40  s2: 40
s1: 50  s2: 50

Question:

Is this the right way to do it? Or is any other (special) way of comparing two sets?

Solution 1

Yes, operator== is correctly defined for all standard containers (except the unordered containers - based on 23.2.5.2 of the standard), and will generally do a lexicographic comparison. See for example here. The relevant quote:

Checks if the contents of lhs and rhs are equal, that is, whether lhs.size() == rhs.size() and each element in lhs has equivalent element in rhs at the same position.

Since std::set is an ordered container, any set with the same size and same elements (given the comparators are the same) will necessarily have them in the same position, hence will compare equal.

Solution 2

There are several set operations in C++ standard library header <algorithm>.

std::set_difference gives those elements that are in set 1 but not set 2.

std::set_intersection gives those elements that are in both sets.

std::set_symmetric_difference gives those elements that appear in one of the sets but not both.

std::set_union gives those elements that are in either set 1 or set 2.

The algorithms above can also be applied to STL containers other than std::set, but the containers have to be sorted first (std::set is sorted by default).

Solution 3

Another way would be this:

template<typename Set>

bool set_compare(Set const &lhs, Set const &rhs){
    return lhs.size() == rhs.size() 
        && equal(lhs.begin(), lhs.end(), rhs.begin());
}

Inspired from the elegant answer here.

Solution 4

C++11 standard on == for std::set

Others have mentioned that operator== does compare std::set contents and works, but here is a quote from the C++11 N3337 standard draft which I believe implies that.

The quote is exactly the same as that for std::vector which I have interpreted in full detail at: C++: Comparing two vectors

As a short summary to avoid duplication with that other answer:

• 23.2.1 "General container requirements" states that all containers use equal() for operator==
• 25.2.11 "Equal" defines equal and explicitly shows that it iterates over both containers comparing the elements of each

View more solutions

Comments

[Mark Ransom]

If std::set implements operator== I'd expect it to be correct.

[jogojapan]

It does implement it, and it does do the right thing. But is that the question? Or are you asking whether the for-loop is correct?

[jogojapan]

If you are looking for a way to determine the elements s1 and s2 do not have in common, you may want to look at std::set_symmetric_difference from the <algorithm> header.

[Bill]

I am not sure if std::set implements == (cplusplus.com/reference/set/set). If you have some object (which does not have == overloaded) instead of int, I am not sure if you will get the same result

[Admin]

I use operator == in s1==s2, I am asking if this is correct if yes, please answer I will accept it, alternatively how should it be done?

[Bill]

Alternatively, iterate over the sets (similar to what you have), and compare each element. I think it is safer that way.

[Drew Dormann]

@jogojapan Of all the commenters that answered correctly, you would get the most out of a reputation bump. :) Consider posting that as an answer.

[jogojapan]

@DrewDormann Nice way of looking at it... anyway, too late...

[Admin]

but two sets with identical elements but in different positions mathematically are equal. Are they equal also in std::set== ? I think yes, but iterating and comapre would lead us to misleading results

[jogojapan]

@gumtree std::set does not keep the elements in the order you inserted them. It sorts them. So, iterating will work just like == works (and std::equal works, too, in the same way).

[Yuushi]

@gumtree That's the point - set is ordered (the second template argument to it is a comparison operator), hence two sets having the same comparator and the same elements cannot have them in different positions.

[rubenvb]

Unordered containers also have operator== (see here or better, here)