I just started learning graphs data structure and came through the adjacency matrix and adjacency lists. The Adjacency list use vector<int> vec[n], where n is the number of vertices. But I think that the working of vector<int> vec[n] i.e so-called adjacency list is same as the vector of vectors...i.e vector<vector<int>> vec. Please help me out with this!

CodePudding user response：

Let's start simple

int arr[n]'
std::vector<int> vec;

arr is a C array of ints. This data type is very bare bone. You can't (easily) get its size and lacks all of the modern OOP features. It has a lot of other problems like not being able to return this data type, or have it as a function parameter (as parameter what looks like a C array data type is in fact a pointer type).

vec is proper C container representing a dynamic vector. You can access its size, you can grow, shrink it etc.

Don't use C arrays. Use standard containers. std::vector should be the first choice. If the size is known at compile time and doesn't change use std::array instead.

vector<int> vec[n]

Is a freakish Frankenstein's monster. It's a C array of vectors of ints.

is same as the vector of vectors...i.e vector<vector<int>> vec

Close. The C equivalent would be std::array<std::vector<int>, n>.

---

Note: there are some compilers (most notably gcc and clang) that accept n as a non constant size for a C array (the so called Variable Length Arrays), but that isn't standard and portable.

CodePudding user response：

Both are not equivalent

std::vector<int> vec[n];

declares an fixed size array of size n where n must be known at compile time (or a compiler extension must be available). During the initialization of vec the constructors of all n vectors are called. These vectors are allocated on the stack.

std::vector<std::vector<int>> vec;

creates an empty vector of vectors though. The constructor of std::vector<int> is never called. You need to call

vec.resize(n);

to change the size of vec to n calling the constructors of std::vector<int> n times. In contrast to std::vector<int> vec[n]; n does not need to be a compile time constant with this approach. Furthermore you can apply other operations on a std::vector<std::vector<int>> changing the number of elements further.

In the second version the std::vector<int> objects are allocated on the heap. (The elements of the std::vector<int>s are stored different locations on the heap.)

CodePudding user response：

In this declaration

std::vector<int> vec[n];

there is declared an array. You can not resize the array for example removing or adding new elements.

On the other hand, using this declaration

std::vector<std::vector<int>> vec( n );

you can resize the vector removing or adding new elements.

Another problem is that arrays do not have the assignment operator. Also arrays do not have comparison operators.

CodePudding user response：

vector<int> vec[n];

• is an array (a so called C-Style array) of size n with elements of type vector<int>
• vec can't grow / shrink in size, however it's elements can (.resize(), .push_back(), .pop_back())

---

vector<vector<int>> vec;

• is a two dimensional vector of type int
• vec can grow / shrink to any size, and it's element can do so as well.

---

which one is better? For your case the vector<vector<int>> probably, but it really depends on the use, C-Style arrays require you know the size before, but can be more optimized as the memory will be on the stack. For example, if you know the size of the matrix beforehand, you can use a pure 2d C-Style array:

int matrix[n][m];

With C-Style arrays you loose the size when passed to a function, so std::array is preferred here, they are as optimized and come with utilities such as .size(), .back() etc:

std::array<std::array<int, m>, n> matrix;