如何解決似乎不太可能出現內存不足問題的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)，在迷宮的文本文件中讀取，存儲（行，列）對起點和目標廣場以及對應於迷宮中「可通過」的（行，列）對的集合。

有幾個其它功能：

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

下面是它們的實現：$g++ maze.cc -g -std=c++0x 然而，$./a.out smallMaze.txt產生

：

// <...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編譯細

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

我不知道Ë一些理智與Valgrind的和GDB檢查： Valgrind的指出：Conditional jump or move depends on uninitialised value(s)在開始

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

和附近的行的行做一組查找，

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

當我檢查GDB中的這些可通過的鄰居指針，它確實看起來像底層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，你最好存儲它的值而不是存儲一個指針。

Answer 2

你加入到孩子們向量的局部變量的地址，一個很大的禁忌

SearchNode child; 
child.cell = childCell; 
child.parent = &sn; 
child.pMaze = mazePointer; 
sn.children.push_back(&child); 

使用某種分配的，或讓你的孩子成爲一個vector<SearchNode>

例如：

SearchNode *child = new SearchNode(); 
child->cell = childCell; 
child->parent = &sn; 
child->pMaze = mazePointer; 
sn.children.push_back(child); 

然後，你將需要在後面打掃一下，或者讓你的載體vector<unique_ptr<SearchNode>>並推動unique_ptr<SearchNode>(child)和去allocat離子將爲你完成