c++ - 使用 STL 的图形(列表 vector ，即邻接列表)- C++

Question

我试图解决与 Graphs 相关的问题，所以我刚开始将 Graph 表示为邻接表。代码如下 -

#include <iostream>
#include <list>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

class Graph
{

    private:
        vector<list<int> > aList;
    public:
        Graph(int nodenum=10):aList(nodenum)
        {
            cout << "Created an adjacency list with "<< nodenum<< " nodes" << endl;
        }

        void addEdge(int from, int to)
        {
            aList[from].push_back(to);
            cout << "Executed" << endl;
        }

        int size()
        {
            return aList.size();
        }

};


int main() {

    Graph gObj(4);    // Graph's size is 4 nodes. 
    gObj.addEdge(0,1);
    gObj.addEdge(1,2);
    gObj.addEdge(2,0);
    gObj.addEdge(3,2);

    cout << "Destroyed" << endl;

    return 0;
}

关于“reserve”的使用(/缺乏)，我注意到一件奇怪的事情(我不是 C++11 专家)。或者也许这是我真正出错的列表的初始化。

如果我这样做 -

Graph(int nodenum=10):aList(nodenum)
{
       cout << "Created an adjacency list with "<< nodenum<< " nodes" << endl;
}

我可以看到我所有的边都添加到图的顶点。 但是，如果我这样做 -

Graph(int nodenum=10)
{
       aList.reserve(nodenum);
       cout << "Created an adjacency list with "<< nodenum<< " nodes" << endl;
}

我注意到代码只是创建图形对象并中断，没有添加任何边。在 Mac Bash 上执行此操作后出现段错误。这是否与我没有考虑到 vector 由内部列表组成的“reserve”的使用有关？

初始化这个邻接表的正确方法是什么？

Answer 1

您将保留与调整大小混淆了。 Reserve是一种优化，它只是为以后推送元素留出空间，而不必重新分配内存。 使用您的第一个 Graph 构造函数实现或在第二个实现中通过调整大小更改保留