C++ 向量数组还是数组向量？

array of vectors or vector of arrays?

提问by thematroids

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

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

vector<int> adj[N];

So does this create an array of type vector or does this create a vector of arrays? The BFS code seems to traverse through a list of values present at each instance of adj[i], and hence it seems works like an array of vectors. Syntax for creating a vector is:

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

vector<int> F;

which would effectively create a single dimensional vector F.

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

What is the difference between

之间有什么区别

vector< vector<int> > N; 

and

和

vector<int> F[N]

回答by awesoon

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

那么这个 ( vector<int> adj[N];) 是创建了一个类型为 vector 的数组还是创建了一个数组向量呢？

It creates array of vectors

它创建向量数组

What is the difference between

vector< vector<int> > N; 

and

vector<int> F[N]

之间有什么区别

vector< vector<int> > N; 

和

vector<int> F[N]

In the first case you are creating a dynamic array of dynamic arrays (vector of vectors). The size of each vector could be changed at the run-time and all objects will be allocated on the heap.

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

In the second case you are creating a fixed-size array of vectors. You have to define Nat compile-time, and all vectors will be placed on the stack^?, however, each vector will allocate elements on the heap.

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

I'd always prefer vector of vectors case (or the matrix, if you could use third-party libraries), or std::arrayof std::arrays in case of compile-time sizes.

我总是喜欢矢量情况下的矢量（或矩阵，如果你可以使用第三方库），或std::array的std::arrayS IN编译时尺寸的情况下。

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

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

You may also represent graph as a std::unordered_map<vertex_type,std::unordered_set<vertex_type>>, where vertex_typeis the type of vertex (intin your case). This approach could be used in order to reduce memory usage when the number of edges isn't huge.

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

---

---

^?: To be precise - not always on stack - it may be a part of a complex object on the heap. Moreover, C++ standard does not define any requirements for stack or heap, it provides only requirements for storage duration, such as automatic, static, thread or dynamic.

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

回答by thematroids

Short Answer:
It's an array of vector <int>s.

简短回答：
它是一个vector <int>s数组。

Long Answer:
When reading a declaration such as

长答案：
当阅读声明时，例如

vector<int> adj[N];

The compiler uses a method known as the "spiral-"or "clockwise-rule"in order to interpret what it means. The idea behind the spiral rule is that you start at the variable name, and move outwards in a clockwise spiral in order to figure out what type of variable it is. For example:

编译器使用一种称为“螺旋规则”或“顺时针规则”的方法来解释它的含义。螺旋规则背后的想法是从变量名称开始，以顺时针螺旋向外移动，以确定它是什么类型的变量。例如：

char* str [10];

Can be interpreted like this:

可以这样解释：

        ____
       |    |
char* str [10];
  |_________|

Making stran array of 10 char*s.

制作str一个 10char*秒的数组。

Therefore, vector<int> adj[N];is an array of vectors rather than a vector of arrays

因此，vector<int> adj[N];是向量数组而不是数组向量

Practice makes perfect:

熟能生巧：

1: What does int * foo [ ];mean?

1：什么int * foo [ ];意思？

Answer:

回答：

"foo" is an array of pointers to integers

“foo”是一个指向整数的指针数组

2: What does int * (*foo [ ] )();mean?

2：什么int * (*foo [ ] )();意思？

Answer:

回答：

"foo" is an array of pointers to functions returning pointers to integers

“foo”是一个指向函数的指针数组，返回指向整数的指针

3: What does int * (*(*foo [ ] )())();mean?

3：什么int * (*(*foo [ ] )())();意思？

Answer:

回答：

"foo" is an array of pointers to functions returning pointers to functions returning pointers to integers

“foo”是一个指向函数的指针数组，返回指向函数的指针，返回指向整数的指针

回答by Martin Gardener

vector<int> arr[N];

It displays an array of vector, each array[i] would have a vector stored in it that can traverse through many values. It is like a an Array of Linked List where the heads are only stored in array[i] positions.

它显示一个向量数组，每个数组[i] 都会存储一个向量，可以遍历许多值。它就像一个链表数组，其中头部仅存储在 array[i] 位置。

vector<vector<int> > N vs vector<int> F[N]

The difference between 2D Vector and an Array of Vector is that 2D Vectors can span in size while array of vectors have their dimension fixed for the array size.

二维向量和向量数组之间的区别在于，二维向量的大小可以跨越，而向量数组的维数对于数组大小是固定的。

回答by Marco Giordano

Under the hood a vector still uses array, it is implementation specific but is safe to think that:

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

vector<int>

internally creates an int[]. What vectors gives you is that it abstract from you the part where if you want to re-size you don't have to re-allocate manually etc, it does that for you (plus much more of course). When you do: vector<vector<int>>you are going to create a vector of vectors, meaning a 2D matrix. You can nest it as much as you want. Vector takes in a type T and allocates an array of that type. so if you pass vector as type T, it will effectively do what you did in your first line, an array of vector<int>. Hope it makes sense

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