向量数组还是数组向量? [英] 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<int> adj[N];)会创建向量类型的数组还是会创建一个向量类型的数组? 向量数组?

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

它创建向量数组

两者之间有什么区别

What is the difference between

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.

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

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,std::unordered_set<vertex_type>>，其中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屋！