調試bad_alloc的錯誤C++

Question

當我運行我的代碼似乎一切都工作正常，但（每個時間通常〜100，但不同數量的）若干時間步長後，我得到的錯誤：

「終止叫拋出一個'std :: bad_alloc'的實例後「

不太確定如何去調試它，因爲它不會在每次代碼運行時發生在同一點。我會發布我的代碼，但是這段代碼很長，並且確實有些亂七八糟（這是我第一次用C++編寫程序的真正嘗試），但是我會嘗試解釋結構和我期望的最可能的地方錯誤的來源是。

基本結構是我有一組「鳥」（一個我定義的類），選擇如何在每個時間步更新自己的一些非常複雜的計算。這樣做通常會調用函數getVisualState來更新每個鳥存儲爲其「視覺狀態」的鏈接列表。我相信這是我在模擬期間動態分配任何內存的唯一時間，所以我認爲這是錯誤的根源。函數Bird :: resetVisualState（）應該在分配的內存被使用後清除分配的內存（但它看起來不像內存不足，至少在任務管理器中監視它）。

如果任何人都能看到任何他們認爲可能是問題的根源，那將是太棒了，或者如果不是任何關於我應該如何實際調試的建議！

#include <iostream> 
#include <cmath> 
#include <gsl/gsl_rng.h> 
#include <gsl/gsl_randist.h> 
#include <ctime> 
#include <vector> 
#include <algorithm> 
#include <fstream> 

#include "birdClasses.h" 

using namespace std; 

/* 
nBirds, nSteps, nF, v, dt, birdRad defined in "birdClasses.h" 
*/ 

//define other parameters. 
const int nSensors = 20; 
const int nMoves = 3; //no. possible moves at each step. 
double dTheta = 15*M_PI/180.0; //angle that birds can change their orientation by in a timestep. 
double moves[nMoves] = {-dTheta, 0, dTheta}; //possible moves. 
double noise = 0.0; 
double initBoxX = 20, initBoxY = 20; //size of initial box particles are placed in. 
double sensorFrac[nSensors]; 
double sensorRef[nSensors]; 
double sensorRange = 2*M_PI/((double)nSensors); 
int counter = 0; 

int nps = numStates(nMoves,nF); 
int *possibleStates = new int[nps]; 


//variables to record positions and orientations. 
double xPositions[nSteps][nBirds], yPositions[nSteps][nBirds], orientations[nSteps][nBirds]; 

//array to keep track of which collisions are possible. 
int couldCollide[nF][nBirds][nBirds]; 

//function prototypes 
bool checkCollision(int i, int nFut, Bird *birds, double xi, double yi); 
unsigned long int getVisualState(Bird *birdList, int nFut, int i, double cX, double cY, double cAng); 
void updateTree(double exploreX, double exploreY, double exploreO, Bird *bird, int bn, int nFut); 

int main() 
{ 
    sensorRef[0] = sensorRange; 
    for(int u=1; u<nSensors; u++) sensorRef[u] = sensorRef[u-1] + sensorRange; 

    //set up GSL random number generator. 
    const gsl_rng_type * Tr; 
    gsl_rng * RNG; 
    gsl_rng_env_setup(); 
    Tr = gsl_rng_default; 
    RNG = gsl_rng_alloc (Tr); 
    gsl_rng_set(RNG,time(NULL)); 

    //set up output 
    ofstream output("output.txt"); 

    //initialize birds in a box randomly, all with the same orientation. 
    Bird birdList[nBirds]; 

    for(int i=0; i<nBirds; i++) { 
     birdList[i].set_position(gsl_ran_flat(RNG,0,initBoxX),gsl_ran_flat(RNG,0,initBoxY)); 
    } 


    //ACTUAL CODE 

    int uniqueVisStates[nMoves]; 
    double cX, cY, fX, fY, exploreX, exploreY, exploreO; 


    //main time step loop 
    for(int ts=0; ts<nSteps; ts++) { 

     //save current positions 
     for(int i=0; i<nBirds; i++) { 
      xPositions[ts][i] = birdList[i].get_xPos(); 
      yPositions[ts][i] = birdList[i].get_yPos(); 
      orientations[ts][i] = birdList[i].get_orientation(); 
      birdList[i].updateFuture(); 
     } 

     //update list of possible collisions. 
     for(int nFut=0; nFut<nF; nFut++) { 
      for(int i=0; i<nBirds; i++) { 
       cX = birdList[i].get_xPos(); cY = birdList[i].get_yPos(); 
       counter = 0; 
       for(int j=0; j<nBirds; j++) { 
        if(i==j) { 
         continue; 
        } else { 
         fX = birdList[j].get_futureX(nFut); fY = birdList[j].get_futureY(nFut); 
         if((cX-fX)*(cX-fX)+(cY-fY)*(cY-fY) < ((nFut+1)*v*dt+2*birdRad)*((nFut+1)*v*dt+2*birdRad)) { 
           couldCollide[nFut][i][counter]=j; 
           counter++; 
         } 
        } 
       } 
       if(counter < nBirds) couldCollide[nFut][i][counter]=-1; 
      } 
     } 

     //loop over birds to choose how they update their orientation. 
     for(int bn=0; bn<nBirds; bn++) { 
      //loop over possible moves bird can make NOW. 

      for(int l=0; l<nMoves; l++) { 
       uniqueVisStates[l]=0; 
      } 

      for(int mn=0; mn<nMoves; mn++) { 
       for(int l=0; l<nps; l++) { 
        possibleStates[l]=0; 
       } 
       counter = 0; 
       exploreO = birdList[bn].get_orientation() + moves[mn]; 
       exploreX = birdList[bn].get_xPos() + cos(exploreO)*v*dt; 
       exploreY = birdList[bn].get_yPos() + sin(exploreO)*v*dt; 
       updateTree(exploreX,exploreY,exploreO,&birdList[0],bn,0); 
       vector<int> visStates (possibleStates,possibleStates+counter); 
       vector<int>::iterator it; 
       sort (visStates.begin(),visStates.end()); 
       it = unique(visStates.begin(),visStates.end()); 
       uniqueVisStates[mn] = distance(visStates.begin(),it); 

      } 
      int maxInd = 0, maxVal = uniqueVisStates[0]; 
      for(int h=1; h<nMoves; h++) { 
       if(uniqueVisStates[h] > maxVal) { 
        maxInd = h; maxVal = uniqueVisStates[h]; 
       } else if(uniqueVisStates[h]==maxVal) { 
        if(abs(moves[h])<abs(moves[maxInd])) { 
         maxInd = h; 
        } 
       } 
      } 
      birdList[bn].update_Orientation(moves[maxInd]); 
      birdList[bn].update_Pos(birdList[bn].get_xPos()+cos(birdList[bn].get_orientation())*v*dt,birdList[bn].get_yPos()+sin(birdList[bn].get_orientation())*v*dt); 
     } 

     for(int bn=0; bn<nBirds; bn++) birdList[bn].finishUpdate(); 
     cout << ts << "\n"; 
    } 

    //OUTPUT DATA INTO A TEXT FILE. 
    for(int ts=0; ts<(nSteps-1); ts++) { 
     for(int bn=0; bn<nBirds; bn++) { 
      output << xPositions[ts][bn] << " " << yPositions[ts][bn] << " " << orientations[ts][bn] << "\n"; 
     } 
    } 

    delete[] possibleStates; 


    return 0; 
} 

bool checkCollision(int i, int nFut, Bird *birds, double xi, double yi) { 
    int cond = 1; int index, counti=0; 
    while(cond) { 
     index = couldCollide[nFut][i][counti]; 
     if(index==-1) break; 
     double xj = birds[index].get_futureX(nFut); 
     double yj = birds[index].get_futureY(nFut); 
     if((xi-xj)*(xi-xj)+(yi-yj)*(yi-yj) < 4*birdRad*birdRad) { 
      return 1; 
     } 
     counti++; 
     if(counti==nBirds) break; 
    } 
    return 0; 
} 

unsigned long int getVisualState(Bird *birdList, int nFut, int i, double cX, double cY, double cAng) { 
    //finds the visual state of bird i based on its current "exploring position" and the predicted positions of other birds at timestep nFut. 
    //visual state is defined by discretizing the bird's field of view into nSensors (relative to current orientation) and creating a vector of 
    //0s and 1s depending on whether each sensor is < half covered or not. This is then converted to an integer (as we are actually interested only 
    //in the number of unique visual states. 
    double relX, relY, relDist, dAng, s, dTheta, ang1, ang2; 
    //clear current visual state. 
    birdList[i].resetVisualState(); 

    for(int j=0; j<nBirds; j++) { 
     if(i==j) continue; 
     relX = birdList[j].get_futureX(nFut)-cX; 
     relY = birdList[j].get_futureY(nFut)-cY; 
     relDist = sqrt(relX*relX+relY*relY); 
     dAng = acos((cos(cAng)*relX+sin(cAng)*relY)/relDist); 
     dTheta = atan(birdRad/relDist); 
     s = cos(cAng)*relY - sin(cAng)*relX; 
     if(s<0) dAng = 2*M_PI-dAng; 
     ang1 = dAng - dTheta; ang2 = dAng + dTheta; 
     if(ang1 < 0) { 
      birdList[i].addInterval(0,ang2); 
      birdList[i].addInterval(2*M_PI+ang1,2*M_PI); 
     } else if(ang2 > 2*M_PI) { 
      birdList[i].addInterval(0,fmod(ang2,2*M_PI)); 
      birdList[i].addInterval(ang1,2*M_PI); 
     } else { 
      birdList[i].addInterval(ang1,ang2); 
     } 
    } 
    Node *sI = birdList[i].get_visualState(); 
    birdList[i].cleanUp(sI); 
    int ind1, ind2; 
    for(int k=0; k<nSensors; k++) sensorFrac[k]=0.0; //initialize. 
    while(sI->next->next != 0) { 
     ang1 = sI->value; ang2 = sI->next->value; 
     ind1 = floor(ang1/sensorRange); ind2 = floor(ang2/sensorRange); 
     if(ind2==nSensors) ind2--; //this happens if ang2 = 2pi (which can happen a lot). 
     if(ind1==ind2) { 
      sensorFrac[ind1] += (ang2-ang1)/sensorRange; 
     } else if(ind2-ind1==1) { 
      sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange; 
      sensorFrac[ind2] += (ang2-sensorRef[ind1])/sensorRange; 
     } else { 
      sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange; 
      sensorFrac[ind2] += (ang2-sensorRef[ind2-1])/sensorRange; 
      for(int y=ind1+1;y<ind2;y++) sensorFrac[y] = 1.0; 
     } 
     sI=sI->next->next; 
    } 
    //do final interval separately. 
    ang1 = sI->value; ang2 = sI->next->value; 
    ind1 = floor(ang1/sensorRange); ind2 = floor(ang2/sensorRange); 
    if(ind2==nSensors) ind2--; //this happens if ang2 = 2pi (which can happen a lot). 
    if(ind1==ind2) { 
     sensorFrac[ind1] += (ang2-ang1)/sensorRange; 
    } else if(ind2-ind1==1) { 
     sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange; 
     sensorFrac[ind2] += (ang2-sensorRef[ind1])/sensorRange; 
    } else { 
     sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange; 
     sensorFrac[ind2] += (ang2-sensorRef[ind2-1])/sensorRange; 
     for(int y=ind1+1;y<ind2;y++) sensorFrac[y] = 1.0; 
    } 
    int output = 0, multiplier = 1; 
    for(int y=0; y<nSensors; y++) { 
     if(sensorFrac[y]>0.5) output += multiplier; 
     multiplier *= 2; 
    } 

    return output; 
} 

void updateTree(double exploreX, double exploreY, double exploreO, Bird *bird, int bn, int nFut) { 
    double o,x,y; 
    if(checkCollision(bn,nFut,bird,exploreX,exploreY)) return; 
    int vs = getVisualState(bird,nFut,bn,exploreX,exploreY,exploreO); 
    possibleStates[counter] = vs; 
    counter++; 
    if(nFut < (nF-1)) { 
     for(int m=0; m<nMoves; m++) { 
      o = exploreO + moves[m]; 
      x = exploreX + cos(o)*v*dt; 
      y = exploreY + sin(o)*v*dt; 
      updateTree(x,y,o,bird,bn,nFut+1); 
     } 
    } else { 
     return; 
    } 
} 

「birdClasses.h」：

#ifndef BIRDCLASSES_H_INCLUDED 
#define BIRDCLASSES_H_INCLUDED 

#include <iostream> 
#include <cmath> 

using namespace std; 

//DEFINE SOME GLOBAL PARAMETERS OF THE SIMULATION 
const int nBirds = 50; 
const int nF = 6; //number of future timesteps to consider. 
const int nSteps = 200; 
const double v = 20, dt = 0.1, birdRad = 0.2; 

int numStates(int numMoves, int nFut) { 
    int num = 1; int multiplier = numMoves; 
    for(int i=1; i<nFut; i++) { 
     num += multiplier; 
     multiplier *= numMoves; 
    } 
    return num; 
} 

//Node class is just for a linked list (used in constructing the visual states), 
class Node { 
public: 
    int identifier; // 0 is left side of interval, 1 is right side 
    double value; //angular value. 
    Node *next; //pointer to the next interval. 
    void display(Node *start); 
}; 

//printout linked list if necessary (mainly for debugging purposes). 
void Node::display(Node *start) { 
    if(start != 0) { 
     double inter = start->value; 
     cout << inter << " "; 
     display(start->next); 
    } 
} 

//bird class. 
class Bird { 
    double currX, currY; 
    double updatedX, updatedY; 
    double currOrientation; 
    double futureX[nF], futureY[nF]; 
    Node *visualState; 
public: 
    Bird() { 
     currOrientation=0.0; currX = 0.0; currY = 0.0; 
     visualState = new Node; 
     visualState->value = 0.0; 
     visualState->next = new Node; 
     visualState->next->value = 0.0; 
     visualState->next->next = 0; 
    } 
    Bird(double x, double y, double o) { 
     currX = x; currY = y; currOrientation = o; 
     visualState = new Node; 
     visualState->value = 0.0; 
     visualState->next = new Node; 
     visualState->next->value = 0.0; 
     visualState->next->next = 0; 
    } 
    void set_position(double x, double y) { 
     currX = x; currY = y; 
    } 
    double get_xPos() { 
     return currX; 
    } 
    double get_yPos() { 
     return currY; 
    } 
    double get_orientation() { 
     return currOrientation; 
    } 
    double get_futureX(int ts) { 
     return futureX[ts]; 
    } 
    double get_futureY(int ts) { 
     return futureY[ts]; 
    } 
    //return pointer to first node. 
    Node* get_visualState() { 
     return visualState; 
    } 
    void updateFuture() { 
     //use current orientation and position to update future positions. 
     for(int i=0; i<nF; i++) { 
      futureX[i] = currX + v*(i+1)*cos(currOrientation)*dt; 
      futureY[i] = currY + v*(i+1)*sin(currOrientation)*dt; 
     } 
    } 
    void update_Pos(double x, double y) { 
     updatedX = x; 
     updatedY = y; 
    } 
    //run this after all birds have updated positions: 
    void finishUpdate() { 
     currX = updatedX; 
     currY = updatedY; 
    } 
    void update_Orientation(double o) { 
     currOrientation += o; 
    } 

    //add the interval defined by [l r] to the visual state. 
    void addInterval(double l, double r) { 
     int placed = 0; double cL = 0.0; double cR = 0.0; 
     if(visualState->value==0.0 && visualState->next->value==0.0) { //then this is first interval to place. 
      visualState->value = l; 
      visualState->next->value = r; 
      placed = 1; 
      return; 
     } 
     Node *curr_L = visualState; 
     Node *prev_L = visualState; 
     while(placed==0) { 
      cL = curr_L->value; 
      cR = curr_L->next->value; 
      if(l<cL && r<cL) { //add new interval before this one. 
       Node *newRoot = new Node; 
       newRoot->value = l; 
       newRoot->identifier = 0; 
       newRoot->next = new Node; 
       newRoot->next->value = r; 
       newRoot->next->next = curr_L; 
       if(curr_L == visualState) { 
        visualState = newRoot; 
       } else { 
        prev_L->next->next = newRoot; 
       } 
       placed = 1; 
      } else if(l <= cL && r >= cR) { 
       curr_L->value = l; 
       curr_L->next->value = r; 
       placed = 1; 
      } else if(l <= cL && r <= cR) { 
       curr_L->value = l; 
       placed = 1; 
      } else if(l >= cL && r <= cR) { 
       placed = 1; //dont need to do anything. 
      } else if(l >= cL && l<=cR && r >= cR) { 
       curr_L->next->value = r; 
       placed = 1; 
      } 

      if(l > cR && r > cR) { 
       if(curr_L->next->next != 0) { 
        prev_L = curr_L; 
        curr_L = curr_L->next->next; 
       } else { 
        Node *newEndL = new Node; 
        newEndL->value = l; 
        newEndL->identifier = 0; 
        newEndL->next = new Node; 
        newEndL->next->value = r; 
        newEndL->next->identifier = 1; 
        newEndL->next->next = 0; 
        curr_L->next->next = newEndL; 
        placed = 1; 
       } 
      } 
     } 
    } 
    //remove any overlaps. 
    void cleanUp(Node *start) { 
     Node *NP, *NNP; NP = start->next->next; 
     if(NP==0) return; 
     NNP = start->next->next->next->next; 
     double cL = start->value, cR = start->next->value, nL = start->next->next->value, nR = start->next->next->next->value; 

     if(nL < cR) { 
      if(nR > cR) { 
       start->next->value = nR; 
      } 

      start->next->next = NNP; 

     } 
     if(NNP!=0) cleanUp(NP); 
    } 
    //reset the visual state. 
    void resetVisualState() { 
     Node *cNode = visualState; 
     Node *nNode = visualState->next; 
     while(nNode != 0) { 
      delete cNode; 
      cNode = nNode; 
      nNode = nNode->next; 
     } 
     delete cNode; 
     delete nNode; 
     visualState = new Node; 
     visualState->identifier = 0; 
     visualState->value = 0.0; 
     visualState->next = new Node; 
     visualState->next->identifier = 1; 
     visualState->next->value = 0.0; 
     visualState->next->next = 0; 
     return; 
    } 
}; 

#endif // BIRDCLASSES_H_INCLUDED 

Answer 1

or if not just any suggestions for how I should actually debug this!

你可以嘗試設置捕獲點在gdb趕上std::bad_alloc例外：

(gdb) catch throw bad_alloc 

（見Setting Catchpoints）

如果你能夠在gdb中重現這個bad_alloc，你可以查看bt來查看這個異常的可能原因。

Answer 2

我認爲這是一個邏輯錯誤，並不一定與內存有關。

在無效addInterval（雙升，雙R）聲明

Node *curr_L = visualState; 
Node *prev_L = visualState; 

這些指針現在將指向任何成員的VisualState指向。

以後要更改的visualSTATE指向一個新創建的節點

Node *newRoot = new Node; 
// .... 
if(curr_L == visualState) { 
    visualState = newRoot; 

，但你的指針curr_L和prev_L仍將指向任何的VisualState指着面前。你改變這些指針唯一的一次是在

if(curr_L->next->next != 0) { 
    prev_L = curr_L; 
    curr_L = curr_L->next->next; 

這是一樣的

if(WHATEVER_VISUAL_STATE_USED_TO_POINT_TO->next->next != 0) { 
    prev_L = curr_L; 
    curr_L = curr_L->next->next; 

這是你的意圖？您可以通過在您的編輯器中查找* curr_L = *來跟蹤curr_L的分配。

我建議您在小數據示例上測試您的代碼，並確保您的代碼符合您的意圖。使用調試器或跟蹤輸出。使用
valgrind如果您有權訪問它，我想您會欣賞valgrind。