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?

Lysol

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

Holcomb

In example 1, does cmp need to be passed into the constructor? Will the set construct one itself as the lambda type is given as a template type? – Ave

@Ave before C++20 comparator has to be passed into the constructor. In C++20 constructor without arguments can be used. Thank you for question; answer was updated – Holcomb

@Holcomb Thank you very much for the response and update to your already great answer. – Ave

That 5. is insane. One finds new nooks and crannies of the language every day. – Laius

Promoted to the accepted answer (just 10+ years after the original question was asked!). – Lysol

Just an addition to the answer, If we want to pass some set with custom comparator then it is better to use the solution based on comparator as function instead of lambdas. – Majors

Is there something similar to the c++20 or c+11 solution for unordered_sets ? – Monogram

@Monogram Haha. Why would there be? It's unordered. But what you're probably looking for are the hash function and the key equality function. See here: en.cppreference.com/w/cpp/container/unordered_set – Bergschrund

How can I do the solution number tree for a vector of sets? what will happen to s(&cmp) ? – Jitney

@MahtaShafieesabet you need to pass comparator as constructor parameter when adding elements to vector. But better to use C++20 solution – Holcomb

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);

Aristotelian

actually my problem appeared to be an extra closing > in the declaration of the set. I am closing the question as bogus. (using a straight function instead of a functor is perfectly okay for STL) – Lysol

the code in the question is simpler than what you proposed (for a simple function comparator) and works just fine. – Lysol

@Omry: I'd be interested in knowing what compiler you're using: codepad.org/IprafuVf – Adrastus

@Omry Which compiler are you using? – Xmas

@Omry The C++ standard says that the second template parameter must be the name of a type - a function name is not the name of a type. – Xmas

@anon: That's not what the (C++03) Standard says. It says: [23.1.2/2] : " [...] This comparison object may be a pointer to function or an object of a type with an appropriate function call operator." – Comfrey

I'm getting an error: ...lib/c++/v1/__tree:1596:17: No matching function for call to object of type 'value_compare' (aka 'lex_compare'). Any ideas? – Phip

If s is a class member and lex_compare is a function how should s been declared? – Leanaleanard

can we use decltype(lex_compare) to denote the function type ? – Berberine

@LewisChan correct term would be std::set<int64_t, decltype(&lex_compare)> s(&lex_compare) – Polybasite

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!

Clodhopping

A matter of opinion, I guess. – Xmas

Wow indeed! But it also points to how ghastly C++ syntax is. I hope future versions and standards will simplify C++ syntax. – Inerney

@Inerney The ::t part can be eliminated in C++14. I think it looks about as good as the Java generics equivalent, while guaranteeing zero runtime overhead. – Clodhopping

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.

Averill

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.

Hauptmann

@A_P hi, why do you mean? – Hauptmann

Answer 6

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!

Euphroe

Answer 7

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

Manizales