c++ - 在 C++ 中使用 vector 与列表的图形表示

Question

所以我遇到了一个编程竞赛问题，涉及在不同的图上运行大量 DFS。

起初我将我的图(邻接表表示)表示为集合 vector :

vector< set<int> > graph;

每次使用空集时，也根据给定的节点数初始化一个图:

set<int> tmpSet;

然后我就这样初始化了它:

for(int j=0;j<N;j++)//N was the number of nodes needed for the graph
   graph.push_back(tmpSet);

我用过

graph.clear();

每次清空图形。

为了之后插入边，我使用了 std::set 的插入函数。

//Insert directed edge from u to v
graph[u].insert(v);
graph[v].insert(u);

结果是程序消耗了太多内存并且速度太慢而无法通过测试。使用 push_back 函数的 std::list 发生了同样的事情，这是一个常数时间操作。然后，当我更改为 std::vector 时，内存消耗变得最小，我在 3 秒内通过了测试，而 std::set 和 std::list 即使在 20 秒内也无法通过它们。

我的问题是，它与释放内部集合和列表的空间有关，但 vector 的行为为何不同？

所以我的问题是，是否有人可以解释为什么会发生这种情况，以便我可以更好地理解 STL 容器在容器内有另一个容器的情况下的行为。

编辑:一些额外信息:节点数约为 N=3000，测试数超过 1000。这意味着我必须创建超过 1000 个图表，所有图表都保存在变量“图表”中。我还知道 set 插入的时间复杂度为 O(lgn)，而 vector 和 list 的时间复杂度为 O(1)，所以我理解为什么 set 比 vector 花费的时间只多一点。但是为什么 std::list 也失败了？另外让我提一下，set 和 list 以 100Mb 的内存使用量结束，而 vector 以 3Mb 结束

好的最终编辑，这是我的代码，用于准确显示我如何使用图表(列表版本)。程序中的任何其他地方都不会释放内存或更改图形数据。

vector< list<int> > graph;
list<int> tmpList;
int T; //num of test cases
int N; //num of nodes
int M; //num of edges
int main ()
{
    int u,v;
    scanf("%d",&T);//Read test cases
    for(int i=0;i<T;i++){

        scanf("%d %d",&N,&M);//Read number of nodes and number of edges
        for(int j=0;j<N;j++)
            graph.push_back(tmpList);

        for(int j=0;j<M;j++){
            scanf("%d %d",&u,&v);//Read edge from u to v
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        dfs();
        graph.clear();
    }
}

Answer 1

当您使用 std::set 保存相邻节点编号时，您插入并在对数时间内获取一个元素，这很慢。但是，当您使用 std::vector insert(push_back) 并获取元素时，它们是在常数时间内完成的，因此存在时间差异。因此，当您不需要在集合中查找某些元素时，您应该使用 std::vector，否则使用 std::set。

std::list 和std::vector 的区别可能是因为clear 函数。对于 list 它是线性的但对于 vector 它是原子化常数。