How does std::greater<> wоrk in a set?

user_14662096 0
Viewed 243

I know how std::greater works. But when I read the API of std::greater since C++14 it has a default type of void. So, if we don't pass any template argument to greater it defaults to void as below. But the result is as expected in descending order.

#include <iostream>
#include <set>

template< class T = void >
struct greater;

int main()
{
    std::set<int, std::greater<>> s {4, 5, 6, 7}; // This transforms to std::set<int, std::greater<void>>
}

Can someone explain how this specialization works?

c++14 c++
2 Answers

It works by having the call operator be a function template instead of a function. Compare the old version to the new specialisation:

// greater<T>
bool operator()( const T& lhs, const T& rhs ) const;

// greater<void> i.e. greater<>
template< class T, class U>
auto operator()( T&& lhs, U&& rhs ) const;

What makes this great is the ability to compare objects of differing types.

This is crucial for example in case where given a string view, you need to look up whether an equivalent std::string is stored in a set. Being able to compare string view to a std::string allows us to not create a string from that string view. Which is good because std::string can potentially be expensive to create.

With the old comparator, it could only compare std::string to another std::string in which case we would have to create a std::string in order to look it up from a set of std::string.

user_20793030

The basic idea is to defer instantiation for a particular type to the call of a templated operator() instead of instantiationg greater for a particular type.

Consider you want to pass an overload set to a function so you can do something like this:

template <typename F>
void foo(F f){
    f(std::string{});  
    f(42);             
}

You cannot pass an overload set to foo. You also cannot pass a class template to foo (without instantiating it). But you can write a class with an templated operator():

struct bar {
    template <typename T>
    void operator()(T t) {}
};


int main() {
  foo(bar{});  
}

In your case passing greater<> instead of greater<int> is mainly a matter of convenience, but the idea is the same. greater<> has a templated operator().

PS: ...and I missed one crucial advantage of greater<>::operator() (explained in detail in this answer). greater<> allows you to compare elements of different type even when there is no implicit conversion between them or you don't want to trigger the conversion (of course you still need a viable >).

user_41177280
Related