1

这是一个基本的指针问题，但这让我困惑了一段时间。我已经实现了一个加权图，使用 C++map作为底层数据结构，如下所示：

std::map<int, std::vector<Edge> > edgeList;

此映射将节点 id (an) 保存为键，并使用 a作为值保存该节点int上的边列表vector

我已经为每个节点初始化了边缘列表，如下所示：

for(int i = 0; i< n; i++){
        std::vector<Edge> vi;
        edgeList.insert(std::make_pair(i,vi)); // initialize with empty vector (at least, that's the intent)
    }

现在，在向图中添加边时，当我尝试检索vector与每个节点对应的边列表时，如下所示：

std::vector<Edge> vList = edgeList.at(v); // v is the node id here

返回一个空的vectorvList，尽管我之前已经向该 vList 添加了边。

另一方面，

std::vector<Edge> &vList = edgeList.at(v);

似乎为我的目的工作正常。谁能解释一下为什么第一个实现不起作用而第二个起作用？

编辑：将边添加到图形的代码如下：

void Graph::addEdge(Edge e){

    // retrieve start and end node for this edge
    int v = e.either(); // returns either end of the edge
    int w = e.other(v);

    // retrieve edge lists for these nodes
    std::vector<Edge> vList = edgeList.at(v); // doesn't work
    std::vector<Edge> wList = edgeList.at(w); // doesn't work

    // add this edge to the list of edges
    vList.push_back(e);
    wList.push_back(e);
}
4

2 回答 2

2

该std::map::at函数返回对std::vector给定索引处的引用。当您将其分配给非参考变量时，您将制作向量的副本。您执行的任何插入操作都将在向量的副本上，在方法结束时超出范围，而您的目标向量只是愉快地位于地图中并且不受影响。

相反，如果您添加&, thenvList将真正成为存储在地图中的实际矢量的别名。vList现在，对地图元素所做的任何更改都是真正的。如果您愿意，您可以将引用视为变相的指针。在这种情况下，你会明确地写

std::vector<Edge> *vList = &edgeList.at(v);

而不是，例如，

std::vector<Edge> *vList = new std::vector();
*vList = edgeList.at(v);

实际上，下面的例子更清楚地说明了这一点：

using namespace std;

int i = 0;

int& get_i()
{
    return i;
}

int main()
{
   cout << "i = " << i << ", &i = " << &i << endl;

   int j = get_i();
   j++;
   cout << "i = " << i << ", j = " << j << ", &j = " << &j << endl; 

   int& k = get_i();
   k++;
   cout << "i = " << i << ", k = " << k << ", &k = " << &k << endl; 

   return 0;
}
于 2013-11-06T22:54:42.690 回答
1

当你这样做时：

std::vector<Edge> vList = edgeList.at(v);

您正在地图中创建矢量的副本。

当你这样做时：

std::vector<Edge> &vList = edgeList.at(v);

您将获得对该向量的引用。

如果您将元素添加到副本中，它们将不会添加到地图中（因为它只是一个副本，并且与原件没有任何关系）。如果您将元素添加到引用中，它会添加到地图中，因为它是同一个向量。

于 2013-11-06T22:54:02.967 回答