I have a struct
with two fields :
struct road {
int from, len ;
};
For some reason, I need to be able to order my road
s :
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
?
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
.
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{});
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With