Using custom std::set comparator

Question

I am trying to change the default order of the items in a set of integers to be lexicographic instead of numeric, and I can't get the following to compile with g++:

file.cpp:

bool lex_compare(const int64_t &a, const int64_t &b) 
{
    stringstream s1,s2;
    s1 << a;
    s2 << b;
    return s1.str() < s2.str();
}

void foo()
{
    set<int64_t, lex_compare> s;
    s.insert(1);
    ...
}

I get the following error:

error: type/value mismatch at argument 2 in template parameter list for ‘template<class _Key, class _Compare, class _Alloc> class std::set’
error:   expected a type, got ‘lex_compare’

what am I doing wrong?

Answer 1

1. Modern C++20 solution

auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s;

We use lambda function as comparator. As usual, comparator should return boolean value, indicating whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.

Online demo

2. Modern C++11 solution

auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s(cmp);

Before C++20 we need to pass lambda as argument to set constructor

Online demo

3. Similar to first solution, but with function instead of lambda

Make comparator as usual boolean function

bool cmp(int a, int b) {
    return ...;
}

Then use it, either this way:

std::set<int, decltype(cmp)*> s(cmp);

Online demo

or this way:

std::set<int, decltype(&cmp)> s(&cmp);

Online demo

4. Old solution using struct with () operator

struct cmp {
    bool operator() (int a, int b) const {
        return ...
    }
};

// ...
// later
std::set<int, cmp> s;

Online demo

5. Alternative solution: create struct from boolean function

Take boolean function

bool cmp(int a, int b) {
    return ...;
}

And make struct from it using std::integral_constant

#include <type_traits>
using Cmp = std::integral_constant<decltype(&cmp), &cmp>;

Finally, use the struct as comparator

std::set<X, Cmp> set;

Online demo

Answer 2

You are using a function where as you should use a functor (a class that overloads the () operator so it can be called like a function).

struct lex_compare {
    bool operator() (const int64_t& lhs, const int64_t& rhs) const {
        stringstream s1, s2;
        s1 << lhs;
        s2 << rhs;
        return s1.str() < s2.str();
    }
};

You then use the class name as the type parameter

set<int64_t, lex_compare> s;

If you want to avoid the functor boilerplate code you can also use a function pointer (assuming lex_compare is a function).

set<int64_t, bool(*)(const int64_t& lhs, const int64_t& rhs)> s(&lex_compare);

Answer 3

Yacoby's answer inspires me to write an adaptor for encapsulating the functor boilerplate.

template< class T, bool (*comp)( T const &, T const & ) >
class set_funcomp {
    struct ftor {
        bool operator()( T const &l, T const &r )
            { return comp( l, r ); }
    };
public:
    typedef std::set< T, ftor > t;
};

// usage

bool my_comparison( foo const &l, foo const &r );
set_funcomp< foo, my_comparison >::t boo; // just the way you want it!

Wow, I think that was worth the trouble!

Answer 4

You can use a function comparator without wrapping it like so:

bool comparator(const MyType &lhs, const MyType &rhs)
{
    return [...];
}

std::set<MyType, bool(*)(const MyType&, const MyType&)> mySet(&comparator);

which is irritating to type out every time you need a set of that type, and can cause issues if you don't create all sets with the same comparator.

Answer 5

std::less<> when using custom classes with operator<

If you are dealing with a set of your custom class that has operator< defined, then you can just use std::less<>.

As mentioned at http://en.cppreference.com/w/cpp/container/set/find C++14 has added two new find APIs:

template< class K > iterator find( const K& x );
template< class K > const_iterator find( const K& x ) const;

which allow you to do:

main.cpp

#include <cassert>
#include <set>

class Point {
    public:
        // Note that there is _no_ conversion constructor,
        // everything is done at the template level without
        // intermediate object creation.
        //Point(int x) : x(x) {}
        Point(int x, int y) : x(x), y(y) {}
        int x;
        int y;
};
bool operator<(const Point& c, int x) { return c.x < x; }
bool operator<(int x, const Point& c) { return x < c.x; }
bool operator<(const Point& c, const Point& d) {
    return c.x < d;
}

int main() {
    std::set<Point, std::less<>> s;
    s.insert(Point(1, -1));
    s.insert(Point(2, -2));
    s.insert(Point(0,  0));
    s.insert(Point(3, -3));
    assert(s.find(0)->y ==  0);
    assert(s.find(1)->y == -1);
    assert(s.find(2)->y == -2);
    assert(s.find(3)->y == -3);
    // Ignore 1234, find 1.
    assert(s.find(Point(1, 1234))->y == -1);
}

Compile and run:

g++ -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out

More info about std::less<> can be found at: What are transparent comparators?

Tested on Ubuntu 16.10, g++ 6.2.0.

Answer 6

Hope this will save some of your time. The simple theory you want to know about comparator,

In C++, comparator should return false if its arguments are equal

Answer 7

struct Cmp{
    bool operator()(pair<int,int> i1,pair<int,int> i2){
        return (i1.first < i2.first) || ((i1.first == i2.first) && i1.second >i2.second  );
    }
};
set<pair<int,int> ,Cmp> st;

Sample Program for demo::

// Online C++ compiler to run C++ program online
#include <iostream>
#include<set>
using namespace std;
int arr[50];

struct Cmp{
    bool operator()(pair<int,int> i1,pair<int,int> i2){
        return (i1.first < i2.first) || ((i1.first == i2.first) && i1.second >i2.second  );
    }
};
set<pair<int,int> ,Cmp> st;

int main() {
    // Write C++ code here
    arr[0] = 0,arr[1] = 2,arr[2] = 4,arr[3] = 3;
    st.insert({0,1});
    st.insert({1,2});
    st.insert({2,2});
    st.insert({2,4});
    set<pair<int,int>,Cmp> ::iterator itr;
    for(itr = st.begin();itr!=st.end();itr++ ){
        cout<<" First: " << itr->first <<" second: " <<itr->second<<endl;
    }
    std::cout << "Hello world!";

    return 0;
}

Output of Program::

First: 0 second: 1
 First: 1 second: 2
 First: 2 second: 4
 First: 2 second: 2
Hello world!