C++ Code Clarification Needed..

Question

Hi guys

I'm trying to understand what the code below says:

struct compare_pq;

struct compare_pq {
    bool operator() (Events *& a, Events *& b);
};

std::priority_queue<Events *, std::vector<Events *>, compare_pq> eventList;

i looked at what priority_queue is and how its declared but can't quit understand what compare_pq is doing in the priority_queue eventList. Also what does operator() do since i've never seen *& before and empty operator overloading operator()!

any help would be appreciated. Thank you

Answer 1

operator() is the function-call operator. It allows you to use an object of the class type as if it were a function, e.g.,

compare_pq my_comparator;
bool result = my_comparator(a, b);

Objects of class types that overload operator() are frequently called function objects or functors.

The third template parameter of std::priority_queue is for the comparison function. By default, the priority queue sorts its elements using std::less, which applies operator< to two elements. You can use any function (or function object) that takes two elements and returns a boolean indicating whether the first is smaller than the second. "Smaller" in this case is a relative term: the top() of the priority queue is the "largest" element currently in the queue.

In this case, you need to use a custom comparison function because the priority queue is storing pointers, so by default it would sort the elements by pointer value. The custom comparator (probably) dereferences the pointers and performs some comparison on the pointed-to objects.

Events*& is just a reference to a pointer to an Events object. It really doesn't need to be passed by reference. Since it's just a pointer, it can be passed by value (e.g., Events*). If you do choose for some reason to use a reference it should be a const reference.

Answer 2

*& is a reference to a pointer. It works like any other kind of reference. In less sophisticated C++ code you might see a double pointer (**) used.

compare_pq is a functor used to compare Event pointers. In this case, priority_queue would likely be instantiating a compare_pq whenever a comparison is needed.

Event * a = new Event();
Event * b = a;
compare_pq foo;
bool result = foo(a, b);

operator() is not empty. You're looking at a declaration. It must be defined somewhere else if it is to be instantiated.

Answer 3

I'll try to answer the question why a functor is used. It's just a guess of course, as I'm not the author of the code, but I saw discussions about it at least a few times and the consensus seems to be, that functors enable or at least make it easier to inline the comparison code.

Functors are structs (or classes) and in general are more flexible than regular functions because they can have some members, that store some state, which can be used by operator(). In this case this advantage isn't used, so the functor was most probably used to enable (or help) in inlining or just because the author was used to this common pattern.

Why would it help in inlining? Let's look at a simple example. Lets take std::sort

template <class RandomAccessIterator, class Compare>
  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

Imagine You want to sort std::vector<int> and You want to provide Your custom comparators.

struct MyStructComp1
{
    bool operator()(int lhs, int rhs) const { /*...*/}
};

struct MyStructComp2
{
    bool operator()(int lhs, int rhs) const { /*...*/}
};

bool myFunctComp1 (int lhs, int rhs) const { /*...*/}
bool myFunctComp2 (int lhs, int rhs) const { /*...*/}

Now You can use the sort temeplate in the following ways

sort(myvector.begin(), myvector.end(), MyStructComp1()); // 1
sort(myvector.begin(), myvector.end(), MyStructComp2()); // 2
sort(myvector.begin(), myvector.end(), myFunctComp1);  // 3
sort(myvector.begin(), myvector.end(), myFunctComp2);  // 4

Here are the function the compiler creates form the template

sort<vector<int>::iterator, MyStrucComp1> // 1
sort<vector<int>::iterator, MyStrucComp2> // 2
sort<vector<int>::iterator, bool (*) (int lhs, int rhs)> // 3, // 4

Since the Compare parameter in the sort template is a type, and functors are types, the compiler creates a different function for every functor supplied as a template argument. sort<vector<int>::iterator, MyStrucComp1> and
sort<vector<int>::iterator, MyStrucComp2> are two different functions. So when sort<vector<int>::iterator, MyStrucComp1> is created, it is known exactly what the comparing code is and the comparator can be simply inlined.

Functions myFunctComp1 and myFunctComp2 however are of exactly the same type:
bool (*) (int lhs, int rhs) and the compiler creates one function sort<vector<int>::iterator, bool (*) (int lhs, int rhs)> for all comparing functions of type bool (*) (int lhs, int rhs). I saw opinions, that inlining is possible anyway in this situation, but I have no idea how.

It is possible to create templates with a pointer to function as a template parameter as it's a compile time constant, but it's ugly and constants can't be deduced from the function arguments. For example if sort was defined as:

template <class RandomAccessIterator,
bool (*comparer) (typename RandomAccessIterator::value_type, typename RandomAccessIterator::value_type)>
    void sort ( RandomAccessIterator first, RandomAccessIterator last) {/*   */}

You would have to call it like this

sort<std::vector<int>::iterator, myFunctComp1>(myvector.begin(), myvector.end());

You would get a different sort for every comparing function, but functors are much more convenient.