C++ : struct vs function for ordering elements

Question

I have a struct with two fields :

struct road {
    int from, len ;
};

For some reason, I need to be able to order my roads :

• by ascending from in an array

• by ascending len in a priority queue

I have thus included :

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

I have come across websites suggesting to overload the operator<, but because of the two possible orderings that just feels wrong and it would only solve one of the two.

By messing around with textbooks, I got this to work :

bool cmpFrom (const road & a, const road & b) {
    return (a.from < b.from) ;
}

struct cmpLen {
    bool operator () (const road & a, const road & b){
        return (a.len < b.len) ;
    }
};

To be used with :

std::sort(trips, trips + nbRoads, &cmpFrom) ;
std::priority_queue<road, std::vector<road>, cmpLen> pickRoad ;

Where trips is of course a road [].

It compiles perfectly (haven't tried running it, but it should be fine), but it seems weird to define two very similar comparators in two quite different manners, so isn't there a way to define both comparison methods the same way ?

Changing the definition of cmpFrom to

struct cmpFrom {
    bool operator () (const road & a, const road & b){
        return (a.from < b.from) ;
    }
};

Gives

chantier.cpp: In function ‘int main()’:
chantier.cpp:38:48: error: expected primary-expression before ‘)’ token
     std::sort(trips, trips + nbRoads, &cmpFrom) ;

Which I assume means "You gave me a type when I was expecting a reference".

While writing

bool cmpLen (const road & a, const road & b) {
    return (a.len <= b.len) ;
}

Gives

chantier.cpp: In function ‘int main()’:
chantier.cpp:52:56: error: type/value mismatch at argument 3 in template parameter list for ‘template<class _Tp, class _Sequence, class _Compare> class std::priority_queue’
     std::priority_queue<road, std::vector<road>, cmpLen> pickRoad ;
                                                        ^
chantier.cpp:52:56: note:   expected a type, got ‘cmpLen’
chantier.cpp:56:30: error: request for member ‘top’ in ‘pickRoad’, which is of non-class type ‘int’
...

Is there a way to make one of these comparison methods work for both containers ? Or is there perhaps a third way of doing this that could work with both ?

What if I had needed to use the same ordering with both containers ? Would that have required defining twice the same comparison method, but with one inside a struct ?

Answer 1

You almost have it. In std::sort you need an object that you can call operator() on. Using

bool cmpFrom (const road & a, const road & b) {
    return (a.from < b.from) ;
}
std::sort(trips, trips + nbRoads, &cmpFrom);

works because a function pointer can be used like a function. When you change cmpFrom to

struct cmpFrom {
    bool operator () (const road & a, const road & b){
        return (a.from < b.from) ;
    }
};

you can't use std::sort(trips, trips + nbRoads, &cmpFrom); anymore because you can't apply & to a type name. Instead what you need to do is get an object of cmpFrom and you do that like

std::sort(trips, trips + nbRoads, cmpFrom{});

now both the priority_queue and sort could use cmpFrom.

Answer 2

It's easier to define both as structures, because you can always create an object from a type and it will behave as expected, but getting a type from a function and having it act as a caller for the function is much more difficult.

You were in fact almost there with struct cmpFrom. However, you've correctly noted that std::sort expects a comparator object (such as a function), not a type. Of course, doing &cmpFrom where cmpFrom is a type is not valid C++. Instead, you need to create an object of that type; thanks to the operator() defined, the object will be callable and do what you want. So just call std::sort like this:

std::sort(trips, trips + nbRoads, cmpFrom{});