CODEWITHSUNDEEP
c++structsetcompare
Michael Kemmerzell
Michael Kemmerzell

Reputation: 5256

Why do I have to implement operator< when using operator() for sorting a std::set

During a code review a colleage from mine was sorting a std::set using a struct. I am still quite new in C++ and had to implement it myself to fully understand it. Sadly I had some struggle because the MSVC forced me to implement operator< too after I implemented operator() of the struct.

Can someone explain me why it is necessary to implement both operator if I use a struct for sorting a std::set? I guessed that operator< is not needed because std::set calls some basic compare function?

class Hallo {
int one;
int two;
public:
Hallo(int one, int two);

bool operator < (const Hallo& rhs) const
{
    return one < rhs.GetOne();
}

struct cmpStruct{
bool operator()(Hallo const &lhs, Hallo const &rhs) const
{
        return lhs.GetOne() < rhs.GetOne();
}

int main(int ac, char* av[]){
const Hallo a{ 1, 1 };
const Hallo b{ 2, 2 };
const Hallo c{ 3, 3 };
const Hallo d{ 5, 5 };

std::set<Hallo, Hallo::cmpStruct> sortedList{};
std::set<Hallo> unsortedList{};

sortedList.insert(b);
sortedList.insert(c);
sortedList.insert(a);
sortedList.insert(d);

unsortedList.insert(b);
unsortedList.insert(c);
unsortedList.insert(a);
unsortedList.insert(d);

Upvotes: 3

Views: 877

Answers (3)

Slava
Slava

Reputation: 44238

Can someone explain me why it is necessary to implement both operator if I use a struct for sorting a std::set?

Because you created 2 instances of std::set with class Hallo as a key and in the first you explicitly used cmpStruct as a functor, but in the second you implicitly use std::less as stated in documentation

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

and std::less uses "some basic compare function" which is operator< documentation:

Function object for performing comparisons. Unless specialized, invokes operator< on type T.

emphasis is mine. So unless you specialize std::less for class Hallo or would not replace std::less in std::set instantiation with something else it would require operator< either as method or standalone function.

Upvotes: 3

James K. Lowden
James K. Lowden

Reputation: 7837

The members of any mathematical set are unique; no two can have the same key. But what does the same mean for a user-defined type like struct? We know what it means for two strings to be equal, or two integers. But the meaning of "same" for your struct is up to you, and up to you to define.

The members of std::set are both unique and sorted, by definition. So, beyond enforcing uniqueness, std::set represents the members in order. What order? Again, for user-defined types, it's up to the user to define what it means for one object to be "less than" another.

That's where operator< comes in. You define what it means for one of your objects to be less than the other. std::set calls your user-defined operator on your user-defined type, and puts the members in the order thus defined. It also uses that function to enforce uniqueness: If a new item cannot be inserted before an existing one nor after it, it's equal to it, and the insertion is rejected.

Upvotes: 0

Thomas Matthews
Thomas Matthews

Reputation: 57678

By default, std::set uses operator < to compare two Hallo instances. This is why you would need to define an operator< function for comparing them. There is no default operation for comparing structs.

Edit 1: Specifying an ordering or comparison function
One of the std::set constructors allows you to specify a function for comparing Hallo instances. If you don't want to add an overloaded operator< method to your struct, you'll need to pass a function that compares two Hallo instances, to the std::set constructor. Again, there are no default comparison operators for struct or class instances; you'll have to create something.

Edit 2: Purpose of comparison function
The comparison function argument of std::set allows you specify a comparison function for your Hallo structure. It allows you to create one set that orders by member one and you could create another set that orders by the two member.

Also, you can define the ordering function for ascending or descending orders. The choices are plentify.

Upvotes: 2

Related Questions