Usage of comparator in C++

Question

Following is the c++ code to Merge k Sorted Lists. But i was confused reading the first 4 lines of code. I know what it does just confused how it does it. Could anybody explain these lines to me?

Why use struct? What are the "()" for after "operator"? Why use ">" rather than "<" since all the lists including the result list are in ascending order?

struct compare {
    bool operator() (ListNode* &left, ListNode* &right) {
        return left->val > right->val;
    }
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, compare> heap;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i]) heap.push(lists[i]);
        }
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (!heap.empty()) {
            ListNode *min = heap.top();
            heap.pop();
            cur->next = min;
            cur = min;
            if (min->next) {
                heap.push(min->next);
            }
        }
        return dummy->next;
    }
};

possible duplicate of [Operator overloading](http://stackoverflow.com/questions/4421706/operator-overloading) — aruisdante, Oct 21 '14 at 16:29
Gah, I didn't actually mean to close, I was just using that as a to search for a link as it explains part 1 of your question (about ``operator()``). The ``compare`` struct's sol purpose is to define the that operator overload, essentially making it a function-object. With respect to part 2, it changes the order of sortation. — aruisdante, Oct 21 '14 at 16:31
1) It isn't a good idea to name your variables `min`. 2) A galnce at your code shows you have a memory leak on `ListNode *dummy = new ListNode(0);`. I don't see where you save that pointer value anywhere for future `delete`-ion. — PaulMcKenzie, Oct 21 '14 at 16:58

5gon12eder · Answer 1 · 2014-10-21T16:55:31.937

Your struct compare is what is known as a functor or a function object.

struct compare
{
  bool
  operator() (const ListNode& left, const ListNode& right) const
  {
    return left.val > right.val;
  }
};

void
example_usage(const ListNode& left, const ListNode& right, const compare cmp)
{
  if (cmp(left, right))
    std::cout << "left is greater" << std::endl;
  else
    std::cout << "right is greater" << std::endl;
}

(I have changed the signature since using references to pointers and making these non-const disturbed me too much.)

It is a convenient alternative to using function pointers in many situations. Most important, when used in templates (as in your example) the compiler is usually able to inline calls to operator (). Using function pointers this is not so easy.

It is not clear whether this is relevant in your example but generally, a functor has the advantage that it can be declared anywhere (also inside function bodies) while functions may only be declared at global scope or as class members. This allows better encapsulation using functors. Since C++11, we have lambdas as yet another alternative:

auto cmp = [](const ListNode& left, const ListNode& right)->bool{
    return left.val > right.val;
};

It can be used just like the functor. (Under the hood, the compiler will most likely create a functor if you give it a lambda expression.)

@NeilKirk Fair enough, but why does this mean, we should not either pass just those pointers (as you mention in your answer) or have the caller dereference them and pass by reference (which is what I prefer). In either case, they should be `const` qualified. — 5gon12eder, Oct 21 '14 at 16:51

score 1 · Answer 2 · answered Oct 21 '14 at 16:42

1

Why use struct?

There is no need to use a struct here, although it doesn't hurt.

What are the "()" for after "operator"?

Look for operator overloading tutorial.

Why use ">" rather than "<" since all the lists including the result list are in ascending order?

It's convention to use < for comparisions such as these, so I don't know why, except to be awkward.

Furthermore the parameters should be (const ListNode* left, const ListNode* right) and if inside a struct, the member function should be made const as well. There is no need to take them by reference here. I would also consider whether you need a data structure of pointers and dynamic allocation here.

answered Oct 21 '14 at 16:42

Neil Kirk

21,327
9
53
91

OP wants to compare types `ListNode*`, so I think `const` is not appropriate here. Either use `ListNode*` or a `const` reference to it (`ListNode* const&`). – anatolyg Oct 21 '14 at 16:56
@anatolyg And he can compare them as `const ListNode*` so I don't see the problem here. Comparison function doesn't alter the objects pointed to. – Neil Kirk Oct 21 '14 at 17:08

score 0 · Accepted Answer · answered Oct 21 '14 at 16:51

Why use struct?

It can be a struct or a class. They are essentially the same thing other than 1. members of structs are default public and members of classes are default private, and 2. general opinions on how people should use structs for POD (plain old data) and classes for everything else.

What are the "()" for after "operator"?

This one's fun. ... operator()(...) defines an overload for the function call operator. Whenever you call a function, you will definitely use this operator, encapsulating the arguments within the brackets and having the return value be the result of the expression.

On a side note, a class or struct with an overloaded function call operator is normally referred to as a functor.

Why use ">" rather than "<" since all the lists including the result list are in ascending order?

This is also another interesting question. The idea is that the STL (Standard Template Library) is meant to be used by almost everyone that uses C++, and is meant to provide convenience in performing certain operations. As such, all the tools in the STL are built to work for any types, including user-defined types.

However, user-defined types do not have operators such as < and > overloaded by default, so users will have to overload them.

The result of a > b is essentially the same as b < a. Now imagine if some of these tools use <, while others use >. Everyone would have to overload both operators even though they are just complements of each other and can be used to substitute each other.

Therefore, a standard was set such that the STL will only use the > operator and only require you to overload that one operator.

On a side note, instead of writing your own comparison functor, you can use the std::less templated functor for simple operations like a less-than comparison, and the std::function for more complex operations.

Thank you for reading.

Thx. And why ... operator()(...) does not indicate any operators(> < ==)? — user3692521, Oct 21 '14 at 16:59
@user3692521 `a == b` => `a.operator==(b)`, `a > b` => `a.operator>(b)`, therefore `a(b)` => `a.operator()(b)`. Note that this only applies to **user-defined types** and do not describe the behavior of operators on **built-in types**. — Nard, Oct 21 '14 at 17:04

Usage of comparator in C++

3 Answers3