C++ - How to use a vector of reference_wrapper
Solution 1
I can gather that it comes from the line: openList.erase(std::find(openList.begin(), openList.end(), current)); but I'm not sure how to fix this.
std::find
iterates over std::reference_wrapper<Tile>
and not Tile&
itself. Hence
Tile& current = openList[0];
openList.erase(std::find(openList.begin(), openList.end(), current));
is incorrect. Change this to
openList.erase(std::find_if(openList.begin(), openList.end(), [&](const std::reference_wrapper<Tile> &i)
{
return i.get() == current;
}));
std::reference_wrapper::get
returns the underlying reference.
A simple, working example to demonstrate this
#include <algorithm>
#include <list>
#include <vector>
#include <iostream>
#include <functional>
struct S
{
int val;
S(int i) : val(i) {}
};
int main()
{
std::list<S> l = {-4, -3, -2, -1, 0, 1, 2, 3, 4};
std::vector<std::reference_wrapper<S>> v(l.begin(), l.end());
auto& x = l.front();
v.erase(std::find_if(v.cbegin(), v.cend(), [&](const std::reference_wrapper<S> &i)
{
return i.get().val == x.val;
}));
std::cout << v[0].get().val;
}
Solution 2
Your problem is here:
std::sort(openList.begin(), openList.end(), sortF());
Your sortF
is an invalid comparison object. The operator()
must look like this:
bool operator()(const Tile& lhs, const Tile& rhs) const
// ^^^ ref ^^^ ^^^ ref ^^^
{
return lhs.f < rhs.f;
}
Instead of:
bool operator()(const Tile* p_a, const Tile* p_b) const
// ^^^ ptr ^^^ ^^^ ptr ^^^
You have a vector of reference_wrapper<Tile>
, not a vector of Tile*
.
Evan Ward
Updated on July 01, 2022Comments
-
Evan Ward almost 2 years
I'm trying to refactor part of a pathfinding algorithm I had that used pointers to not use pointers. Unfortunately I'm not that knowledgable about references. I get the error:
Invalid operands to binary expression ('std::__1::reference_wrapper<Tile>' and 'const std::__1::reference_wrapper<Tile>')
I also have no idea what that means. My code is below, and I can gather that it comes from the line:
openList.erase(std::find(openList.begin(), openList.end(), current));
but I'm not sure how to fix this.bool TileMap::tilesBetween(Tile& p_start, Tile& p_end) { std::vector<std::reference_wrapper<Tile>> openList; std::vector<std::reference_wrapper<Tile>> closedList; openList.push_back(p_start); do { std::sort(openList.begin(), openList.end(), sortF()); Tile& current = openList[0]; closedList.push_back(current); openList.erase(std::find(openList.begin(), openList.end(), current)); if(std::find(closedList.begin(), closedList.end(), p_end) != closedList.end()) { return true; } std::vector<std::reference_wrapper<Tile>> adjacentTiles; if (current.m_coordinates.x > 0) { adjacentTiles.push_back(m_tiles[current.m_coordinates.y * m_width + (current.m_coordinates.x - 1)]); } if (current.m_coordinates.x < m_width) { adjacentTiles.push_back(m_tiles[current.m_coordinates.y * m_width + (current.m_coordinates.x + 1)]); } if (current.m_coordinates.y > 0) { adjacentTiles.push_back(m_tiles[(current.m_coordinates.y - 1) * m_width + current.m_coordinates.x]); } if (current.m_coordinates.y < m_height) { adjacentTiles.push_back(m_tiles[(current.m_coordinates.y + 1) * m_width + current.m_coordinates.x]); } for(auto t : adjacentTiles) { if(std::find(closedList.begin(), closedList.end(), t) != closedList.end()) { continue; } if(std::find(openList.begin(), openList.end(), t) == closedList.end()) { openList.push_back(t); } } } while(!openList.empty()); return false; }
EDIT: posted
sortF
struct sortF { bool operator()(const Tile* p_a, const Tile* p_b) const { return p_a->f < p_b->f; } };
UPDATE: As per the suggestion, I've changed the function to use pointers instead of references. It SEEMS to be working, but I have more to implement before it's finished.
bool TileMap::tilesBetween(Tile* p_start, Tile* p_end) { std::vector<Tile*> openList; std::vector<Tile*> closedList; std::cout << p_start << ", "; openList.push_back(p_start); do { std::sort(openList.begin(), openList.end(), sortF()); Tile* current = openList[0]; closedList.push_back(current); openList.erase(std::find(openList.begin(), openList.end(), current)); if(std::find(closedList.begin(), closedList.end(), p_end) != closedList.end()) { return true; } std::vector<Tile*> adjacentTiles; if (current->m_coordinates.x > 0) { adjacentTiles.push_back(&m_tiles[current->m_coordinates.y * m_width + (current->m_coordinates.x - 1)]); } if (current->m_coordinates.x < m_width) { std::cout << &m_tiles[current->m_coordinates.y * m_width + (current->m_coordinates.x + 1)] << std::endl; adjacentTiles.push_back(&m_tiles[current->m_coordinates.y * m_width + (current->m_coordinates.x + 1)]); } if (current->m_coordinates.y > 0) { adjacentTiles.push_back(&m_tiles[(current->m_coordinates.y - 1) * m_width + current->m_coordinates.x]); } if (current->m_coordinates.y < m_height) { adjacentTiles.push_back(&m_tiles[(current->m_coordinates.y + 1) * m_width + current->m_coordinates.x]); } for(auto t : adjacentTiles) { if(std::find(closedList.begin(), closedList.end(), t) != closedList.end()) { continue; } if(std::find(openList.begin(), openList.end(), t) == openList.end()) { openList.push_back(t); } } } while(!openList.empty()); return false; }
-
Evan Ward about 9 yearsSorry, I was updating the whole function when I posted this so it didn't match. I did have it the way you suggested when it used references though.
-
Praetorian about 9 yearsThat works, but manually unwrapping the
reference_wrapper
is not required because it has an implicit conversion operator toT&
. So you can avoid the lambda and usefind
as long asS
is equality comparable - coliru.stacked-crooked.com/a/4dcd9b9164a93645 -
legends2k about 9 yearsI tried without the manual unwrapping - lambda - in vain, but I'd implemented
operator==
as a member function, when I changed it to a external friend function it worked! Thanks to you I'd learned about the symmetric assumption made instd
's generic algorithms. -
legends2k over 2 yearsSymmetric Assumption - Replacement for broken link.