Как решить проблему bad_alloc, которая вряд ли является проблемой нехватки памяти?

Я пишу немного кода для поиска лабиринта с BFS в C ++ (мой основной язык — 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) квадратов начала и цели, а также набор, соответствующий парам (row, col), которые «проходимы» в лабиринте.

Также есть несколько других функций:

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:
Вальгринд отмечает, что Conditional jump or move depends on uninitialised value(s) в строке, которая начинается

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

и рядом строка, которая делает поиск набора,

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

Когда я проверяю эти указатели passableNeighbor в GDB, это делает похоже, что базовый объект SearchNode не имеет правильно инициализированной дочерней ячейки со всевозможными странными значениями. Я подозреваю, что это связано с моим непониманием того, как C ++ распределяет объекты.

Таким образом, совершенно очевидно, что основная проблема заключается в том, что объект passableNeighbor каким-то образом содержит поврежденные данные. Является ли это артефактом того, как я написал метод getPassableChildren ()? Есть еще мысли?

Я посмотрел на std :: bad_alloc, и кажется, что это исключение обычно связано с нехваткой памяти, но я получаю эту ошибку на своем самом первом узле, расширенном во время BFS, так что кажется крайне маловероятным, что я ударяя любой предел памяти.