Sorry for the stupid question, couldn't find anything on stackoverflow, cuz have no idea how to google that.
I was solving one graph problem, and met this declaration of adjacency list 49661413, I am confused, how is it possible that vector of vectors is declared using vector<int> name[]
, and it is not a simple vector, I don't even realize what's that. Couldn't you please explain to me what's that or give me a link to website with some info? Thanks in advance
It's just an array. Each element of that array is a vector.
It's the same as
vector<vector<int>> name(N)
. but you usevector<int> name[N]
instead, replacingvector
with a normal array.The accessing is pretty much the same, but the fundamental representation is quite different, owing mainly to the fact that a
std::vector
allocates memory on the heap and not the stack.Suppose we are not in the global scope. Then
std::vector<int> a[N]
is an array of $$$N$$$ vector objects stored on the stack, with the contents of each vector being stored on the heap, whilestd::vector<std::vector<int>> a(N)
is an object with $$$O(1)$$$ memory being stored on the stack, with $$$O(N)$$$ vector objects stored on the heap (as pointers to those objects) and those objects themselves being stored on the heap. Using the first one may give an error about not being able to allocate that amount of memory on stack, while a heap usually has much more memory and hence the second one is more preferable.If it is declared in the global scope, then a similar thing holds, however instead of the stack, the array resides in the data segment (which gives more memory than the stack), and not in the stack, so that's why it's sometimes advised to use global variables in competitive programming, even though they're generally frowned upon (very rightfully, too) in software development.
However, note that there is literally zero overhead for using a vector as compared to an array (provided you use
std::vector::push_back
reasonably to avoid multiple reallocations, possibly usingstd::vector::reserve
), so it's always advisable to use more modern language features, and keeping your code modular to make it compact, easy to reason about and less prone to errors (for instance, forgetting to clear data structures etc). Something more on the performance ofstd::vector
.vector< int > name;
Here we've only a vector.vector< int >name [5];
Here we've 5 vectors. name[0] , name[1], name[2], name[3] and name[4].Google it and learn details.