c++ - 性能崩溃 C++(std vector bad_allocation)

Question

以下代码是关于实时搜索邻居的。一旦将新节点添加到我的图中，就会调用该节点的函数 updateSeqNeighbours。我所知道的是，新节点肯定是最后添加的节点的邻居。在下一步中，我使用这个事实来查看先前添加的节点的邻域，找到最接近新节点的那个，然后在该邻域中搜索最近的邻域。

例如，我仅重复此操作 3 次，以将一个节点的邻居数量限制为 4，以保持恒定的计算时间范围。它工作得很好，除了在大约 30 个节点之后计算时间增加得非常快，每增加一个节点就会导致 bad_alloc 异常。

#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_ */

图表:

#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_ */

我怀疑是内存不足导致的。然而，每 4 个邻居有 40 个节点对我来说听起来不是什么大问题。有人知道出了什么问题吗？

编辑:德语错误，所以我需要猜测:类 std::bad_alloc 的项目 prSimulation1.exe 中出现异常。异常地址:'0x5476016'。进程已停止。

Answer 1

你的 seqNeighbours是vector<Node> .这意味着它存储邻居本身，而不是指向它们或它们的索引的指针。因此，复制构造函数复制所有邻居。反过来，复制每个邻居需要复制它的邻居，这需要复制它们的邻居，依此类推。您的任务还复制所有邻居，这需要复制他们的邻居，依此类推。这意味着每个拷贝都会以指数方式增加内存负载，直到系统无法存储所有邻居、邻居的邻居等。

PS:在旁注中，称为“列表”的 vector 不是一个好主意。它就像一个叫做“vector”的列表，一个叫做“map”的集合，或者一只叫做 Dog 的猫。