Алгоритм — Как использовать вектор reference_wrapper

Question

Алгоритм — Как использовать вектор reference_wrapper

Я пытаюсь провести рефакторинг части моего алгоритма поиска пути, который использовал указатели, чтобы не использовать указатели. К сожалению, я не настолько осведомлен о ссылках. Я получаю ошибку: Invalid operands to binary expression ('std::__1::reference_wrapper<Tile>' and 'const std::__1::reference_wrapper<Tile>')

Я также понятия не имею, что это значит. Мой код ниже, и я могу понять, что он исходит из строки: openList.erase(std::find(openList.begin(), openList.end(), current)); но я не уверен, как это исправить.

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;
}

РЕДАКТИРОВАТЬ: опубликовано sortF

struct sortF
{
bool operator()(const Tile* p_a, const Tile* p_b) const
{
return p_a->f < p_b->f;
}
};

ОБНОВЛЕНИЕ: Согласно предложению, я изменил функцию, чтобы использовать указатели вместо ссылок. Это работает, но мне нужно еще кое-что реализовать, пока она не закончилась.

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;
}

3

algorithm binary-operators c++pointers reference

Решение

Другие решения

Ваша проблема здесь:

std::sort(openList.begin(), openList.end(), sortF());

Ваш sortF недопустимый объект сравнения operator() должен выглядеть так:

bool operator()(const Tile& lhs, const Tile& rhs) const
//              ^^^ ref ^^^      ^^^ ref ^^^
{
return lhs.f < rhs.f;
}

Вместо:

bool operator()(const Tile* p_a, const Tile* p_b) const
//              ^^^ ptr ^^^      ^^^ ptr ^^^

У вас есть вектор reference_wrapper<Tile>, а не вектор Tile*,

0

Источник

Accepted Answer

Я могу понять, что это происходит из строки: openList.erase (std :: find (openList.begin (), openList.end (), current)); но я не уверен, как это исправить.

std::find перебирает std::reference_wrapper<Tile> и не Tile& сам. следовательно

    Tile& current = openList[0];
openList.erase(std::find(openList.begin(), openList.end(), current));

это неверно. Изменить это на

    openList.erase(std::find_if(openList.begin(), openList.end(), [&](const std::reference_wrapper<Tile> &i)
{
return i.get() == current;
}));

std::reference_wrapper::get возвращает основную ссылку.

Просто, рабочий пример чтобы продемонстрировать это

#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;
}

3