c++ - 使用 malloc 分配空间给 list 指针不工作

Question

class graph
{

    int v;
    list<int> *adj;
    void dfsutil(int v,bool visited []);
    public:
    graph(int v)
    {
        this->v=v;
        //adj = new list<int>[v];
        adj = (list<int> *)malloc(v*sizeof(list<int>));
    }
    void addedge(int v,int w);
    void dfs(int v);
};


void graph::addedge(int v,int w)
{
    adj[v].push_back(w);
}

void graph::dfsutil(int v,bool visited[])
{
    list<int>::iterator i;
    cout<<v<<" ";
    visited[v]=true;

    for(i=adj[v].begin();i!=adj[v].end();i++)
    {
        if(!visited[*i])
            dfsutil(*i,visited);
    }
}

void graph::dfs(int v)
{
    int i=0;
    bool visited[this->v];
    for(i=0;i<this->v;i++)
        visited[i]=false;
    dfsutil(v,visited);
    for(i=0;i<v;i++)//this loop is required if there are multiple component of the graph
        if(!visited[i])
            dfsutil(i,visited);
}

int main()
{
    // Create a graph given in the above diagram
    graph g(4);
    g.addedge(0, 1);
    g.addedge(0, 2);
    g.addedge(1, 2);
    g.addedge(2, 0);
    g.addedge(2, 3);
    g.addedge(3, 3);

    cout << "Following is Depth First Traversal (starting from vertex 2) \n";
    g.dfs(2);

    return 0;
}

在上面的代码中，如果尝试使用上面写的 malloc 为列表 *adj 分配空间，它不能正常工作，而如果我们使用 new，它可以正常工作，正如上面评论部分所写的那样，我不明白为什么

Answer 1

当您使用 malloc 时，您没有创建 std::list objects 数组。 malloc 所做的只是从堆中分配内存——不创建任何对象。因此，尝试使用您的 std::list，就好像它们是正确创建的一样，将导致未定义的行为。

您应该使用诸如 std::vector 的容器来存储您的列表对象:

#include <vector>
#include <list>

class graph
{
    int v;
    std::vector<std::list<int>> adj;
    void dfsutil(int v,bool visited []);
    public:
        graph(int num) : v(num), adj(num) {}
    void addedge(int v,int w);
    void dfs(int v);
};

注意不需要分配内存。其余代码应该保持不变，因为 vector 有一个重载的 operator [] 来访问项目。