c++ - 如何解决似乎不太可能是内存不足问题的 bad_alloc？

Question

我正在用 C++ 编写一些使用 BFS 搜索迷宫的代码(我的主要语言是 Python，但我想稍微锻炼一下我的 C++ 大脑...)，我偶然发现了这个奇怪的错误。

这里是相关的数据结构:

struct Maze {
  std::pair<int, int> start;
  std::pair<int, int> goal;
  std::pair<int,int> dims;
  std::set<std::pair<int, int> > passable;
};

struct SearchNode {
  std::pair<int, int> cell;
  Maze* pMaze;
  SearchNode* parent;
  std::vector<SearchNode*> children;
};

假设我已经有了一个方法 void parseFile(Maze* maze, char* filename) 读取迷宫文本文件，存储开始和开始的 (row, col) 对目标方 block 以及对应于迷宫中“可通过”的(行，列)对的集合。

还有一些其他的功能:

bool isPassable(Maze* maze, std::pair<int,int> testCell);
std::vector<SearchNode*> getPassableChildren(SearchNode sn);
void mazeSearch(Maze* maze);

以下是它们的实现:

// <...snip...>
inline bool isPassable(Maze* maze, std::pair<int,int> cell) {
  return maze->passable.find(cell) != maze->passable.end();
}


std::vector<SearchNode*> getPassableChildren(SearchNode sn) {
  // Store a cached copy of the children, so if we require multiple queries
  // we do not have to re-compute children.
  if(sn.children.empty()) {
    Maze* mazePointer = sn.pMaze;
    int r = sn.cell.first;
    int c = sn.cell.second;
    for(int i = 0; i <= 2; ++i) {
      for(int j = 0; j <= 2; ++j) {
        if (!(i == 1 && j == 1)) {
          std::pair<int,int> childCell(r+i-1, c+j-1);

          if(isPassable(mazePointer, childCell)) {
            // Build child SN
            SearchNode child;
            child.cell = childCell;
            child.parent = &sn;
            child.pMaze = mazePointer;
            sn.children.push_back(&child);
          }
        }
      }
    }
  }
  return sn.children;
}

void mazeSearch(Maze* maze) {
  std::set<std::pair<int,int> > visited;
  std::deque<SearchNode> workQueue;

  // Create root node.
  SearchNode root;
  root.cell = maze->start;
  root.parent = NULL;
  root.pMaze = maze;

  workQueue.push_back(root);
  visited.insert(root.cell);

  while(!workQueue.empty()) {
    SearchNode sn = workQueue.front();
    workQueue.pop_front();

    for(SearchNode* passableNeighbor : getPassableChildren(sn))  {
      // THIS IF-STATEMENT IS BROKEN
      if(passableNeighbor->cell.first == maze->goal.first &&
         passableNeighbor->cell.second == maze->goal.second) {
        printf("Found a path.\n");
        return;
      }
      // Check to make sure it is not in our visited set.
      // THIS STATEMENT IS ALSO BROKEN
      if (visited.find(passableNeighbor->cell) == visited.end()) {
        workQueue.push_back(*passableNeighbor);
        visited.insert(passableNeighbor->cell);
      }
    }
  }
  printf("No path found.\n");
}
// <...snip...>

代码在 GCC 4.6.3 下编译良好:$g++ maze.cc -g -std=c++0x然而，$./a.out smallMaze.txt 产生

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

我已经用 Valgrind 和 GDB 做了一些合理性检查:Valgrind 指出 Conditional jump or move depends on the uninitialised value(s) in the line begins

if(passableNeighbor->cell.first == maze->goal.first

和附近的行进行集合查找，

if(visited.find(passableNeighbor->cell) == visited.end())

当我检查 GDB 中的这些 passableNeighbor 指针时，它确实看起来底层 SearchNode 对象没有正确初始化它的子单元格，各种奇怪的值突然出现。我怀疑这与我对 C++ 如何分配对象缺乏了解有关。

所以很明显，潜在的问题是 passableNeighbor 对象以某种方式在其中包含损坏的数据。这是我编写 getPassableChildren() 方法的产物吗？还有其他想法吗？

我查看了 std::bad_alloc ，似乎这个异常通常与内存不足有关，但我在 BFS 期间扩展的第一个节点上遇到了这个错误，所以这似乎极不可能我正在达到任何内存限制。

Answer 1

这部分有问题

      if(isPassable(mazePointer, childCell)) {
        // Build child SN
        SearchNode child;
        child.cell = childCell;
        child.parent = &sn;
        child.pMaze = mazePointer;
        sn.children.push_back(&child);
      }

因为它用指向局部变量的指针填充 children。当您离开 if 语句时，所有指针均无效。

如果您在这里创建一个新的 child，最好存储它的值而不是存储一个指针。