所以我遇到了一个编程竞赛问题，涉及在不同的图表上运行大量 DFS。
起初，我将我的图（邻接表表示）表示为一个集合向量：
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 秒内也无法通过测试。
我的问题是它与释放内部集合和列表的空间有关，但是向量的行为如何不同呢？
所以我的问题是，是否有人可以解释为什么会发生这种情况，以便我可以更好地理解 stl 容器在诸如您在另一个容器中有一个容器的情况下如何表现。
编辑：一些额外的信息：节点数约为 N=3000，测试次数超过 1000。这意味着我必须创建 1000 多个图表，这些图表都保存在变量“图表”中。我也知道 set 在 O(lgn) 时间内插入，而 vector 和 list 在 O(1) 中，所以我理解为什么 set只需要比向量长一点的时间。但是为什么 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();
}
}