-1

我有两个节点指针向量。

vector<Node*> tmp; 

vector<Node*> nodes;

我说tmp = nodes;

如果 I delete nodes, thentmp也被删除。

有什么方法可以tmp在修改时不进行nodes修改，例如将其设为 const？

我基本上在运行 Dijkstra's。但该算法在确定最短路径时总是删除节点向量。这意味着我只能做一次从源到目的地的最短路径。

如果我有一个图表 0--->1--->2--->3 即

CGraph g;

g.Dijkstras(0);
g.PrintShortestRouteTo(2);
g.Dijktras(2);         
g.PrintShortestRouteTo(3);    <-- source is still 0 since nodes is deleted
                                  therefore I get the path from 0 to 2


  class Node
{
public:
    Node(int id)
        : id(id), previous(NULL),
        distanceFromStart(INT_MAX)
    {
        nodes.push_back(this);
    }
public:
    int id;
    Node* previous;
    int distanceFromStart;
};

vector<Node*> nodes;

void CGraph::Dijkstras(int source)
{

    nodes[source]->distanceFromStart =  0;   


    for (int i = 0; i < (int)nodes.size(); i++)
        cout << nodes[i]->distanceFromStart << " " ;

    cout << "------------------------" << endl;

    while (nodes.size() > 0)
    {
        Node* smallest = ExtractSmallest(nodes);
        //cout << "Smallest: " << smallest->id << " ";
        //Node* smallest = nnodes[1];
        vector<Node*>* adjacentNodes =
            AdjacentRemainingNodes(smallest);
        const int size = adjacentNodes->size();
        for (int i=0; i<size; ++i)
        {
            Node* adjacent = adjacentNodes->at(i);
            int distance = Distance(smallest, adjacent) +
                smallest->distanceFromStart;
            if (distance < adjacent->distanceFromStart)
            {
                adjacent->distanceFromStart = distance;
                adjacent->previous = smallest;
            }
        }
        delete adjacentNodes;
    }
}
4

4 回答 4

1

你不能写delete nodes，因为nodes它不是一个指针。如果你这样写，代码将无法编译。

当你写这个：

vector<Node*> tmp = nodes;

然后你制作一个向量对象的副本，而不是向量的内容。向量的两个副本中的向量内容相同。因此，如果您更改一个向量的内容，该更改也将反映在该向量的另一个副本中。

如果您还想复制内容，请写下：

std::vector<Node*> tmp;
tmp.reserve(nodes.size()):

//include <algorithm> for std::transform
std::transform(nodes.begin(),   
               nodes.end(),
               std::back_inserter(tmp),
               [](Node const *node) { return new Node(*node); });

注意：上面的代码只能在 C++11 中编译，因为它使用 lambda 表达式。在 C++03 中，您可以使用函数或仿函数来代替它。

考虑使用智能指针，例如std::unique_ptr<Node>或std::shared_ptr<Node>代替Node*. 智能指针管理内存本身，您需要担心它。但是，如果你使用智能指针，那么上面的代码会有点不同，但如果你想复制内容，基本思想是一样的。

于 2012-06-07T05:22:02.990 回答
0

管理此问题的一种方法是改用共享指针

vector<shared_ptr<Node> > tmp;

这样，即使 tmp/Nodes 在其他对象（Node* 指向的对象）之前超出范围，仍然存在。

于 2012-06-07T05:23:10.050 回答
0

如果它是一个类，您可能需要为 Node 实现一个复制构造函数，然后循环通过“节点”将每个项目复制到 tmp 中

tmp.clear();

for(vector<Node*>::iterator it = nodes.begin(); it != nodes.end(); it++)
{
    Node* copy = new Node((*it));

    tmp.push_back(copy);
}
于 2012-06-07T05:24:24.240 回答
0

你的问题有点令人困惑，但我的解释是：

std::vector<Node *> *tmp;
std::vector<Node *> *nodes;

nodes = somehow_gets_dynamically_created_vector();
tmp = nodes;
// perhaps do other things with nodes
delete nodes;

然后，代码保持tmp悬空状态（即，它指向已释放的内存）。但。这应该是安全的：

std::vector<Node *> tmp;
std::vector<Node *> *nodes;

nodes = somehow_gets_dynamically_created_vector();
tmp = *nodes;
// perhaps do other things with nodes
delete nodes;

现在，在您的示例代码中，唯一看起来与您描述的内容模糊相似的代码是代码如何处理adjacentNodes变量。而且，我收集到nodes由于这delete adjacentNodes条线而发生了一些不好的事情。我会确保该AdjacentRemainingNodes功能正在执行您认为应该执行的操作。至少它应该返回由调用提供的值，该值new std::vector<Node *>在该函数主体内执行的代码中的某处。如果没有，则deleteonadjacentNodes无效。

但也许你心里有不同的意思。相反，如果您的意思是在复制nodes到tmp之后tmp看到更新的值到distantFromStart，那么这是使用指针的结果。您可以通过不在向量中使用指针来避免该问题。

std::vector<Node> tmp;
std::vector<Node> nodes;

tmp = nodes;

但是，您将需要定义一个复制构造函数或以其他方式弄清楚如何处理该previous成员。例如，复制构造函数可以只将previous成员设置为NULL而不是从 LHS 复制值。

Node::Node (const Node &lhs)
    : id(lhs.id), previous(NULL), distanceFromStart(lhs.distanceFromStart)
 {}

但是你应该做任何合适的事情。

于 2012-06-07T08:22:09.580 回答