I'm trying to create a std::priority_queue that takes as parameters a pair. The pair has parameters int and Coord. Coord is a struct simply containing two ints (x and y) for coordinates for an array.
What I'm trying to do with my entire program is implementing the Dijkstra algorithm on an array grid (instead of using a graph), which is already giving me a headache because I'm not really sure I'm doing it the correct way. At least I'm trying and learning. But anyway the problem I'm having now is that when I compile, I get the error
"C2678 binary'<' no operator found which takes a left-hand operand of type 'const Coord' (or there is no acceptable conversion)"
This is how some of my code looks like:
struct Coord
{
int x, y;
};
this is the basic Coord struct. Then there's the function where I create the queue:
void dijkstraFirstPhase(Coord start, Coord end, int(&aGrid)[HEIGHT][WIDTH], unordered_map<pair<int, int>, bool, pair_hash>& theMap)
{
//priority_queue< pair<int, pair<int, int>> > pq;
priority_queue<pair<int, Coord>> pq; //this is the line where the error comes from
//initializing the starting point
int distanceFromStart = 0;
aGrid[start.x][start.y] = distanceFromStart;
pq.push({ distanceFromStart, start });
while (!pq.empty())
{
Coord u = pq.top().second;
theMap[make_pair(u.x, u.y)] = true;
pq.pop();
writeDistances(u.x, u.y, aGrid, theMap, pq);
displayGrid(aGrid);
if (theMap[make_pair(end.x, end.y)] = true)
{
cout << "The end has been found" << endl;
cout << "Distance written into its cell: " << aGrid[end.x][end.y] << endl;
break;
}
}
}
I'd like to know how to get rid of this error, I'm not very familiar with queues or pairs, but I thought I understood them enough for what I needed to do. What is it trying to compare with that operator? I don't need an int to be smaller than the Coord in the pair arguments.
Any suggestions are welcome, but not complex one as I'm still a beginner with C++ and might not understand them
It may seem entirely logical to you, but the compiler has no idea what order your conceptual definition of "priority" means regarding your thing called a Coord. Your objects being stored in your queue look like this:
std::pair<int, Coord>
and understanding how std::priority_queue compares elements is warranted.
The adapter std::priority_queue defaults to using std::less for the item comparator to determine order. As you have now-discovered, that comparator does little more than manufacture a simple a < b construct to compare objects for order, and if the object class (or its bases) provide this, great; if not, you need to do so. as it turns out, std::pair does provide an operator <, which basically establishes strict weak ordering across first and second. For two pair objects it essentially does this:
return lhs.first < rhs.first || (!(rhs.first < lhs.first) && lhs.second < rhs.second);
Why is that important? Note that second usage in the last expression. It's important because the second in the above is of your type Coord, Therefore, operator < is being applied to Coord and since there is no such operator, compiler = not-happy.
As a side-note, you've noticed this works out of the box for std::pair<int, std::pair<int,int>> because as mentioned earlier, std::pair has an operator <overload, and in that case two different instantiations ofoperator <` are manifested.
To solve this, you have to provide such an operator for your type. There are essentially only two ways to do this: a member function or a free-function either of which define a operator < overload for Coord. Usually implemented as a member function, but also possible as a free-function, this essentially provides the operator std::less is looking for. This is the most common mechanism for providing order (and imho the easiest to understand):
// member function
struct Coord
{
int x, y;
bool operator <(const Coord& rhs)
{
return x < rhs.x || (!(rhs.x < x) && y < rhs.y)
}
};
or
// free function
bool operator <(const Coord& lhs, const Coord& rhs)
{
return lhs.x < rhs.x || (!(rhs.x < lhs.x) && lhs.y < rhs.y)
}
General Comparator Guidelines
Beyond making std::less<> happy for a given type by overloading operator <, many containers, adapters, and algorithms allow you to provide your own custom comparator type. For example:
std::mapstd::setstd::sortstd::priority_queueTo that, there are several possible ways to do this. Examples include:
operator < for instances of your Type type (easy, example shown prior). This allows the continued default std::less to do it's job of firing operator < that is provided by you.std::less that you specify for the container, adapater, or algorithm when declaring or invoking them.std::less<Coord> (moderately easy, but rarely done and less intuitive for beginners). This replaces std::less with your specialization wherever it would normally be used.Examples of the last two appear below. We'll assume we're just using your Coord rather than your std::pair<int, Coord>, explained earlier
Provide custom comparator
You don't have to use std::less for ordering. You can also provide your own functor that does the same job. The third template parameter to std::priority_queue is what you use to provide this:
struct CoordLess
{
bool operator()(Coord const& lhs, Coord const& rhs) const
{
return lhs.x < rhs.x || (!(rhs.x < lhs.x) && lhs.y < rhs.y)
}
};
std::priority_queue<Coord, std::vector<Coord>, CoordLess> myqueue;
This is handy when you need to implement different orderings on the same object class for different containers. For example, you could have one container that orders small-to-large, another large-to-small. Different comparators allow you to do that. For example, you could create a std::set of Coord objects with your comparator by doing
std::set<Coord, CoordLess> myset;
or sort a vector vec of Coord objects by doing this:
std::sort(vec.begin(), vec.end(), CoordLess());
Note in both cases we specify at declaration or invocation the custom comparator.
Provide a std::less specialization
This is not as easy to understand, rarely done, but just as easy to implement. Since std::less is the default comparator, so long as the type is a custom type (not a native language type or library type) you can provide a std::less specialization for Coord. This means everything that normally uses std::less<Coord> for ordering will get this implicitly if the definition below is provided beforehand.
namespace std
{
template<>
struct less<Coord>
{
bool operator ()(Coord const& lhs, Coord const& rhs) const
{
return lhs.x < rhs.x || (!(rhs.x < lhs.x) && lhs.y < rhs.y)
}
};
}
With that provided (usually immediately after your custom type in the same header), you can simply use default template parameters, whereas before we had to specify them. For example now we can declare a std::set like this:
std::set<Coord> myset;
or perform a sort like this:
std::sort(vec.begin(), vec.end());
Both of those default to using std::less<Coord> and since we've specialized that ourselves, it uses ours. This is a handy, enveloping way of changing default behavior in many places, but with great power comes great responsibility, so be careful, and never do this with native or library-provided types.
Hopefully that give you some ideas on different ways you can solve your error.