c++ - vector 数组还是数组 vector ？

Question

我是 C++ STL 的新手，无法理解图形表示。

vector<int> adj[N];

那么这会创建一个 vector 类型的数组还是创建一个数组 vector ？ BFS 代码似乎遍历了 adj[i] 的每个实例中存在的值列表，因此它看起来就像一个 vector 数组。 创建 vector 的语法是:

vector<int> F;

这将有效地创建一维 vector F。

有什么区别

vector< vector<int> > N; 

和

vector<int> F[N]

Answer 1

So does this (vector<int> adj[N];) create an array of type vector or does this create a vector of arrays?

它创建 vector 数组

What is the difference between

vector< vector<int> > N; 

and

vector<int> F[N]

在第一种情况下，您正在创建一个动态数组的动态数组( vector 的 vector )。每个 vector 的大小可以在运行时更改，所有对象都将在堆上分配。

在第二种情况下，您正在创建一个固定大小的 vector 数组。您必须定义 N在编译时，所有 vector 都将放在堆栈上^†，但是，每个 vector 都会在堆上分配元素。

我总是更喜欢 vector 大小写的 vector (或矩阵，如果您可以使用第三方库)，或 std::array的 std::array s 在编译时大小的情况下。

I'm new to C++ STL, and I'm having trouble comprehending the graph representation.

您也可以将图表表示为 std::unordered_map<vertex_type,std::unordered_set<vertex_type>> , 其中 vertex_type是顶点的类型( int 在您的情况下)。当边数不是很大时，可以使用这种方法来减少内存使用量。

---

^†:准确地说 - 并不总是在堆栈上 - 它可能是堆上复杂对象的一部分。而且，C++标准并没有定义任何栈和堆的要求，它只提供了存储时长的要求，例如自动、静态、线程或动态。