Debuggen einen bad_alloc Fehler C++

Question

Wenn ich mein Code alles laufen scheint aber nach einer bestimmten Anzahl von Zeitschritten zu funktionieren (in der Regel ~ 100, aber eine andere Zahl jedes Mal) erhalte ich die Fehlermeldung:

„genannt terminate nach dem Werfen einer Instanz von 'std :: bad_alloc' "

Nicht wirklich sicher, wie man über das Debuggen dieses gehen, da es nicht jedes Mal am gleichen Punkt der Code ausgeführt wird. Ich werde meinen Code posten, aber er ist ziemlich lang und ist zugegebenermaßen etwas durcheinander (dies ist mein erster wirklicher Versuch, ein Programm in C++ zu schreiben), aber ich werde versuchen, die Struktur zu erklären und wo ich den wahrscheinlichsten Ort dafür erwarten würde der Ursprung des Fehlers sein.

Die grundlegende Struktur ist, dass ich eine Reihe von "Vögeln" (eine Klasse, die ich definiere), die wählen, wie sie sich bei jedem Zeitschritt durch eine ziemlich komplizierte Berechnung aktualisieren. Dabei ruft es regelmäßig die Funktion getVisualState auf, um eine verlinkte Liste zu aktualisieren, die jeder Vogel als "visual state" speichert. Ich glaube, das ist die einzige Zeit, in der ich dynamisch Speicher während der Simulation zuteile, also gibt es eine ziemlich gute Chance, dass dies die Quelle des Fehlers ist. Die Funktion Bird :: resetVisualState() sollte den zugewiesenen Speicher löschen, nachdem er benutzt wurde (aber es scheint nicht so, als ob ich nicht genug Speicher habe, zumindest im Task-Manager).

Wenn jemand etwas sehen kann, denken sie vielleicht die Quelle des Problems, das wäre fantastisch, oder wenn nicht nur irgendwelche Vorschläge, wie ich das eigentlich debuggen sollte!

#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!

Sie können versuchen, in Catchpoint gdb zu setzen std::bad_alloc Ausnahme zu fangen:

(gdb) catch throw bad_alloc 

(Siehe Setting Catchpoints)

Wenn Sie dieses bad_alloc in gdb reproduzieren können, können Sie sich bt ansehen, um den möglichen Grund für diese Ausnahme zu sehen.

Answer 2

Ich denke, das ist ein Logikfehler und nicht unbedingt Speicher bezogen.

In Leere addInterval (Doppel l, Doppel r) Sie erklären

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

Diese Zeiger nun zu, was visual zeigt auf markierten Punkt des Mitglieds.

später auf Sie visual ändern zu einem neu erstellten Knoten

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

aber Ihre Zeiger curr_L und prev_L noch zu Punkt-zu-Punkt, was auch immer visual bis vor hinwies.Das einzige Mal, wenn Sie diese Zeiger ändern, ist bei

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

die die gleiche wie

ist

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

Ist das Ihre Absicht? Sie können die Zuordnung von curr_L verfolgen, indem Sie in Ihrem Editor nach * curr_L = * suchen.

Ich würde vorschlagen, testen Sie Ihren Code auf eine kleine Datenprobe und stellen Sie sicher, dass Ihr Code Ihren Absichten folgt. Verwenden Sie Debugger oder Trace-Ausgaben. Verwenden Sie
valgrind wenn Sie Zugriff darauf haben, denke ich, dass Sie Valgrind schätzen werden.