向量数组还是数组向量? [英] array of vectors or vector of arrays?

问题描述

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

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

vector<int> adj[N];

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

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:

vector<int> F;

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

which would effectively create a single dimensional vector F.

和

vector< vector<int> > N; 

和

vector<int> F[N]

推荐答案

这样做 (vector adj[N];) 是否创建了一个向量类型的数组，或者这是否创建了一个数组向量?

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

它创建向量数组

有什么区别

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.

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

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

我总是更喜欢向量案例(或矩阵，如果你可以使用第三方库)，或 std::array 的 std::array>s 在编译时大小的情况下.

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

我是 C++ STL 的新手，我无法理解图表代表.

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

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

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

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

^†: 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.

这篇关于向量数组还是数组向量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！