std::map 覆盖错误的键
std::map overwriting wrong keys
所以我正在编写一个使用 BFS 算法解决迷宫的代码。由于我必须显示路径,因此我使用地图来存储父节点。不幸的是,父节点本应保持不变,却被覆盖了。这是代码
//Data structure to store the coordinates for easy access
class Point
{
public:
int x;
int y;
// For using map
bool operator<(const Point& p) const {
return this->x < p.x && this->y < p.y;
}
bool operator==(const Point& p)const {
return this->x == p.x && this->y == p.y;
}
};
// A function to be used in algo
// Return: Bool whether the value is in range
bool isValid(int row, int col)
{
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// Off sets for the neighbours
int rowOffsets[] = { -1, 0, 0, 1 };
int colOffsets[] = { 0, -1, 1, 0 };
// The main BFS Algorithm
vector<Point> BFS(int mat[ROW][COL], Point source, Point destination)
{
bool visited[ROW][COL]; // An array to check whether the node is visited
memset(visited, false, sizeof(visited)); // Set all the values to false
// Mark the source as visited
visited[source.x][source.y] = true;
// Change the ! and * to movable spaces
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (mat[i][j] == 99 || mat[i][j] == -01)
mat[i][j] = 0;
// Create the queue
queue<Point> q;
// The parent map. Second denotes the parent for the first.
map<Point, Point> parent;
q.push(source); // Enqueue source cell
// Let's Start!
bool success = false;
while (!q.empty())
{
Point current = q.front();
// Reached the destination?
if (current.x == destination.x && current.y == destination.y) {
success = true;
break; // Continue to the next stuff
}
// Deque it
q.pop();
// Continue BFS with other nodes
for (int i = 0; i < 4; i++)
{
int row = current.x + rowOffsets[i];
int col = current.y + colOffsets[i];
// if adjacent cell is valid, has path and not visited yet, enqueue it.
if (isValid(row, col) && !mat[row][col] && !visited[row][col])
{
// mark cell as visited and enqueue it
visited[row][col] = true;
Point Adjcell = { row, col };
parent[Adjcell] = current; // Certify the parent
q.push(Adjcell);
}
}
}
// Trace back
if (!success)
return {};
Point node = parent[destination]; // The first path
vector<Point> path;
while (node.x != source.x || node.y != source.y) {
path.push_back(node);
node = parent[node];
}
return path;
}
当我 运行 使用此 BFS 算法构建迷宫时,地图显示出一些非常奇怪的行为。这是一个例子:
这是原始地图。从代码和调试器中可以清楚地看出,adjCell (2,1) 的父项为 (1,1) 应该还有一个条目,对吗?但是没有:
什么都没发生。这被完全忽略了。好吧,让我们说系统曾经欺骗我 :(。至少现在应该有 (1,3) 的新条目,其中 (1,2) 作为父项。但是没有:
值被覆盖了!这怎么可能?不应该有新的价值吗?为什么 (1,2) & (1,3) 相同?
最后有一个奇怪的观察结果:如果我在 Point
class
中更改此代码
bool operator<(const Point& p) const {
return this->x < p.x && this->y < p.y;
}
到
bool operator<(const Point& p) const {
return this->x < p.x;
}
末尾父级的大小从 7 变为 13。我最好的猜测是 map class 中的插入有问题。由于运算符 < 是 'key' ,我可能会遗漏一些东西。但我没有任何确定的线索。非常感谢任何帮助。
operator<
函数实现不正确。它不符合键的严格弱排序标准。
使用
bool operator<(const Point& p) const {
return std::tie(this->x, this->y) < std::tie(p.x, p.y);
}
如果您想手动编写正确的实现代码,请使用:
bool operator<(const Point& p) const {
if ( this->x != p.x )
{
return (this->x < p.x);
}
return (this->y < p.y);
}
所以我正在编写一个使用 BFS 算法解决迷宫的代码。由于我必须显示路径,因此我使用地图来存储父节点。不幸的是,父节点本应保持不变,却被覆盖了。这是代码
//Data structure to store the coordinates for easy access
class Point
{
public:
int x;
int y;
// For using map
bool operator<(const Point& p) const {
return this->x < p.x && this->y < p.y;
}
bool operator==(const Point& p)const {
return this->x == p.x && this->y == p.y;
}
};
// A function to be used in algo
// Return: Bool whether the value is in range
bool isValid(int row, int col)
{
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// Off sets for the neighbours
int rowOffsets[] = { -1, 0, 0, 1 };
int colOffsets[] = { 0, -1, 1, 0 };
// The main BFS Algorithm
vector<Point> BFS(int mat[ROW][COL], Point source, Point destination)
{
bool visited[ROW][COL]; // An array to check whether the node is visited
memset(visited, false, sizeof(visited)); // Set all the values to false
// Mark the source as visited
visited[source.x][source.y] = true;
// Change the ! and * to movable spaces
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (mat[i][j] == 99 || mat[i][j] == -01)
mat[i][j] = 0;
// Create the queue
queue<Point> q;
// The parent map. Second denotes the parent for the first.
map<Point, Point> parent;
q.push(source); // Enqueue source cell
// Let's Start!
bool success = false;
while (!q.empty())
{
Point current = q.front();
// Reached the destination?
if (current.x == destination.x && current.y == destination.y) {
success = true;
break; // Continue to the next stuff
}
// Deque it
q.pop();
// Continue BFS with other nodes
for (int i = 0; i < 4; i++)
{
int row = current.x + rowOffsets[i];
int col = current.y + colOffsets[i];
// if adjacent cell is valid, has path and not visited yet, enqueue it.
if (isValid(row, col) && !mat[row][col] && !visited[row][col])
{
// mark cell as visited and enqueue it
visited[row][col] = true;
Point Adjcell = { row, col };
parent[Adjcell] = current; // Certify the parent
q.push(Adjcell);
}
}
}
// Trace back
if (!success)
return {};
Point node = parent[destination]; // The first path
vector<Point> path;
while (node.x != source.x || node.y != source.y) {
path.push_back(node);
node = parent[node];
}
return path;
}
当我 运行 使用此 BFS 算法构建迷宫时,地图显示出一些非常奇怪的行为。这是一个例子:
最后有一个奇怪的观察结果:如果我在 Point
class
bool operator<(const Point& p) const {
return this->x < p.x && this->y < p.y;
}
到
bool operator<(const Point& p) const {
return this->x < p.x;
}
末尾父级的大小从 7 变为 13。我最好的猜测是 map class 中的插入有问题。由于运算符 < 是 'key' ,我可能会遗漏一些东西。但我没有任何确定的线索。非常感谢任何帮助。
operator<
函数实现不正确。它不符合键的严格弱排序标准。
使用
bool operator<(const Point& p) const {
return std::tie(this->x, this->y) < std::tie(p.x, p.y);
}
如果您想手动编写正确的实现代码,请使用:
bool operator<(const Point& p) const {
if ( this->x != p.x )
{
return (this->x < p.x);
}
return (this->y < p.y);
}