Search code examples
c++setcomparator

Implementing Compare for std::set

I have a struct that is just two ints that I want to store in std::set, while also taking advantage of its sorting properties. For example

struct Item
{
    int order;
    int value;
};

So I wrote a comparator

struct ItemCmp
{
    bool operator()( const Item& lhs, const Item& rhs ) const
    {
        return lhs.order < rhs.order || lhs.value < rhs.value;
    }
};

The intent is that Item should be sorted in the collection by ORDER first, and then by VALUE. If I put these Item in a vector and use std::sort, seems to be working as expected.

I also implemented unit tests for the cases in https://en.cppreference.com/w/cpp/named_req/Compare

However now this test case is failing:

std::set<Item, ItemCmp> stuff;
stuff.insert( {1, 1} );
stuff.insert( {1, 1} );
CHECK( stuff.size() == 1 );

The size of the set is 2, violating the contract of set. Where am I going wrong?

Solution

  • based on @retired-ninja 's comment, the answer is to ensure the comparator does proper lexicographical comparison. One shortcut to this is to leverage std::tuple's operators (see https://en.cppreference.com/w/cpp/utility/tuple/operator_cmp ) using this example:

    return std::tie(lhs.order, lhs.value) < std::tie(rhs.order, rhs.value);