Understanding a Comparator functor for STL

Question

So I have always used comparator functors in STL but never truly understood what returning a true or false meant. I had to run it and adjust the functor all the time. For instance suppose I have the following code

struct functor
{
    // does returning true place a before b ?
    bool operator()(int a,int b)
    {
        if (a < b)
            return true;
        return false;
    }
};

int main() 
{
    std::priority_queue<int, std::vector<int>,functor> q;
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
}

Could anyone please clarify this

bool operator()(int a,int b)
    {
        if (a < b)
            return true;
        return false;
    }

Does returning a true place a before b? I am trying to come up with something like "if a is less than b than return true and true means a will be placed before b" but apparently this is not correct

Functor simply should return `true` if its first argument (`a`) comes before its second argument (`b`) with respect to the required ordering. — Daniel Langr, Jan 27 '18 at 21:12

Edgar Rokjān · Answer 1 · 2018-01-27T21:28:09.007

You could always check the documentation.

From the priority_queue:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Compare - A Compare type providing a strict weak ordering.

Then, check Compare:

The concept Compare is a set of requirements expected by some of the standard library facilities from the user-provided function object types.

The return value of the function call operation applied to an object of type Compare, when contextually converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this Compare type, and false otherwise.

It means, that functor::operator() should accept two parameters (a and b) and return true if a "appears before" b while "appears before" rules are defined by the implementation of functor::operator() (this implementation must be compliant with the requirements imposed by Compare concept).

Important: for `priority_queue`, the order is the **reverse** of the order defined by the comparator. That is, calling `pop()` returns the **largest** element when the comparator is `<`. That's the nature of a priority queue; "normal" sorted containers follow the order defined by the comparator. — Pete Becker, Jan 27 '18 at 21:34

score 1 · Accepted Answer · answered Jan 27 '18 at 21:46

Yes, if your function is

bool operator(T a, T b);

If it returns true, it means that a is placed before b in the sorted ordering. However, the priority queue is ordered so that if a is placed before b, b will be higher than a in the queue. So if

bool operator (T a, T b) { return a < b; }

is used, the "largest" element will be at the top of the queue.

score -1 · Answer 3 · answered Jan 27 '18 at 21:12

-1

It's convention to sort on <. Your code

bool operator()(int a,int b)
{
    if (a < b)
        return true;
    return false;
}

is the same as

bool operator()(int a, int b)
{
    return a < b ;
}

Also, have a look at Operator< and strict weak ordering

answered Jan 27 '18 at 21:12

Johan Lundberg

26,184
12
71
97

Robert F. Dickerson · Answer 4 · 2018-01-27T21:28:28.290

Why not just do this since it's simpler:

bool operator()(int a, int b)
{
    return a < b
}

The function you need to give as your sort function for the priority queue should by a binary function that returns true if b is bigger than a, or the first argument is bigger than b.

The sort function internally uses probably a simple swap of the two values if that condition is not true.

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

http://www.cplusplus.com/reference/algorithm/sort/

Understanding a Comparator functor for STL

4 Answers4

Linked