Leistungseinschränkung C++ (Standardvektor bad_allocation)

Question

Im folgenden Code wird in Echtzeit nach Nachbarn gesucht. Sobald ein neuer Knoten zu meinem Graphen hinzugefügt wird, wird die Funktion für diesen Knoten aufgerufen. Was ich weiß ist, dass der neue Knoten definitiv dem letzten hinzugefügt wird. Im nächsten Schritt benutze ich diese Tatsache, um in der Nähe des zuvor hinzugefügten Knotens zu suchen, den nächsten zu finden und dann diese Nachbarschaft nach dem nächsten Nachbarn zu durchsuchen.

Ich wiederhole dies nur zum Beispiel 3 mal, um die Anzahl der Nachbarn für einen Knoten auf 4 zu begrenzen, um einen konstanten Zeitrahmen für die Berechnung zu behalten. Es funktioniert wunderbar, außer nach ~ 30 Knoten steigt die Berechnungszeit sehr schnell mit jedem zusätzlichen Knoten, was zu einer bad_alloc Ausnahme führt.

#ifndef GRAPH_NODE_H_ 
#define GRAPH_NODE_H_ 

#include <vector> 
#include <cmath> 

#include <iostream> 

using namespace std; 

class Node { 
public: 
    double x; 
    double y; 

    Node* nodePrev; 

    vector<Node> seqNeighbours; 

    //Constructor 
    Node(); 
    Node(double x, double y); 
    virtual ~Node(); 

    //Operator functions 
    Node& operator=(const Node& n); 

    //Get&Set 
    int getID(); 

    //Public member functions 
    void addNeighbour(Node& n); 

    bool isSeqNeighbour(int ID); 

    int updateSeqNeighbours(); 

    double distanceTo(Node& n); 

private: 
    static int count; 
    int ID; 

    void _setDefaults(); 
}; 

int Node::count = 0; 

Node::Node() { 
    _setDefaults(); 
} 

Node::Node(double x, double y) { 
    _setDefaults(); 
    this->x = x; 
    this->y = y; 
} 

Node::~Node() { 
    // TODO Auto-generated destructor stub 
} 

//Operator functions 
Node& Node::operator=(const Node& n) { 
    if (this != &n) { 
     ID = n.ID; 
      x = n.x; 
      y = n.y; 
     seqNeighbours.clear(); 
     seqNeighbours = n.seqNeighbours; 
     nodePrev = n.nodePrev; 
    } 
    return *this; 
} 

//Get&Set 
int Node::getID() { 
    return this->ID; 
} 

//Public member functions 
void Node::addNeighbour(Node& n) { 
    seqNeighbours.push_back(n); 
} 

double Node::distanceTo(Node& n) { 
    return sqrt((n.x-x)*(n.x-x) + (n.y-y)*(n.y-y)); 
} 

bool Node::isSeqNeighbour(int ID) { 
    for (int i = 0; i < seqNeighbours.size(); i++) { 
     if (seqNeighbours[i].getID() == ID) { 
      return true; 
     } 
    } 
    return false; 
} 

int Node::updateSeqNeighbours() { 
    if (nodePrev == NULL) { 
     return 1; 
    } else { 
     Node seed = *nodePrev; //previous node as seed 
     seqNeighbours.push_back(seed); 

      for (int i = 0; i < 3; i++) { 
        if (seed.nodePrev == NULL) break; 
        double minDist = 15353453; 
        Node closest; 
        for (int j = 0; j < seed.seqNeighbours.size(); j++) { 
          double dist = distanceTo(seed.seqNeighbours[j]); 
          if (dist < minDist) { 
            minDist = dist; 
            closest = seed.seqNeighbours[j]; 
          } 
        } 
        if (minDist < 150) { 
          seqNeighbours.push_back(closest); 
        } 
        seed = closest; 
      } 
      cout << "neighbours = " << seqNeighbours.size() << endl; 
    } 
    return 0; 
} 

void Node::_setDefaults() { 
    x = 0; 
    y = 0; 
    ID = count; 
    nodePrev = NULL; 
    seqNeighbours.clear(); 
    count++; 
} 
#endif /* GRAPH_NODE_H_ */ 

Graph:

#ifndef GRAPH_GRAPH_H_ 
#define GRAPH_GRAPH_H_ 

#include <vector> 
#include <iostream> 
#include "Node.h" 

using namespace std; 

class Graph { 
public: 
    Graph(); 
    virtual ~Graph(); 

    vector<Node> list; 

    void addNode(Node& n); 
    void addSeqNode(Node& n); 


private: 
    void _setDefaults(); 
}; 

Graph::Graph() { 
    // TODO Auto-generated constructor stub 

} 

Graph::~Graph() { 
    // TODO Auto-generated destructor stub 
} 

void Graph::addNode(Node& n) { 
    list.push_back(n); 
} 

void Graph::addSeqNode(Node& n) { 
    if (!list.empty()) { 
     n.nodePrev = &list.back(); 
    } 
    n.updateSeqNeighbours(); 
    list.push_back(n); 
} 

void Graph::_setDefaults() { 
    list.clear(); 
} 


#endif /* GRAPH_GRAPH_H_ */ 

ich aus der Erinnerung vermuten läuft verursacht dies. Aber 40 Knoten mit jeweils 4 Nachbarn sind für mich kein Problem. Irgendeine Idee, was schief geht?

Edit: Fehler in Deutsch, so muss ich erraten: Eine Ausnahme im Projekt prSimulation1.exe der Klasse std :: Bad_alloc angetroffen. Adresse der Ausnahme: '0x5476016'. Der Prozess wurde gestoppt.

Answer 1

Ihre seqNeighbours ist vector<Node>. Das heißt, es speichert die Nachbarn selbst, keine Zeiger auf sie oder ihre Indizes. Der Kopierkonstruktor kopiert daher alle Nachbarn. Das Kopieren jedes Nachbarn wiederum erfordert das Kopieren seiner Nachbarn , was das Kopieren ihrer Nachbarn erfordert, und so weiter. Ihre Aufgabe kopiert auch alle Nachbarn, die ihre Nachbarn kopieren müssen, und so weiter. Dies bedeutet, dass jede Kopie die Speicherlast exponentiell erhöht, bis das System nicht alle Nachbarn, Nachbarn von Nachbarn usw. speichern kann.

PS: Nebenbei bemerkt ist ein Vektor namens "Liste" eine schlechte Idee. Es ist wie eine Liste namens "Vektor", eine Menge namens "Karte" oder eine Katze namens Hund.