向量数组还是数组向量？

Question

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

 vector<int> adj[N];

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

 vector<int> F;

这将有效地创建一维向量 F。

和有什么区别

vector< vector<int> > N;

和

vector<int> F[N]

原文由 thematroids 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

那么这（ vector<int> adj[N]; ）是创建一个向量类型的数组还是创建一个数组向量？

它创建向量数组

和有什么区别

vector< vector<int> > N;

和

vector<int> F[N]

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

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

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

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

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

---

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

原文由 awesoon 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

在引擎盖下，向量仍然使用数组，它是特定于实现的，但可以安全地认为：

 vector<int>

在内部创建一个 int[]。向量给您的是它从您那里抽象出如果您想重新调整大小而不必手动重新分配等的部分，它会为您做到这一点（当然还有更多）。当您这样做时： vector<vector<int>> 您将创建一个向量向量，即二维矩阵。您可以随意嵌套它。 Vector 接受类型 T 并分配该类型的数组。因此，如果您将向量作为类型 T 传递，它将有效地执行您在第一行中所做的事情，即 vector<int> 的数组。希望有意义

原文由 Marco Giordano 发布，翻译遵循 CC BY-SA 3.0 许可协议