Menu
I know that std::vector<T> internally stores it's data contiguously (unless it is std::vector<bool>) both in the old C++03 standard and the new C++11.
Nice stackoverflow questions that deal with this and quote the standard: answer, answer.
What about the data inside nested vectors std::vector <std::vector <T> >? How is that stored?
If every internal vector needs to store it's data contiguously, how can it be true that &v[n] == &v[0] + n for all 0 <= n < v.size().
To phrase this slightly different, is it possible to access all the elements stored in such nested structure "simply" and sequentially (via a pointer or similar) the same way it can be done for a 1-D vector?
436
Yes, if: you only ever need to add stuff to the end of your vector of vectors, and. you're willing to replace the vector of vectors construct with a custom data structure.
Vectors are assigned memory in blocks of contiguous locations. When the memory allocated for the vector falls short of storing new elements, a new memory block is allocated to vector and all elements are copied from the old location to the new location. This reallocation of elements helps vectors to grow when required.
Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays.
std::pair is a struct, the standard says the compiler determines the layout though the order must be maintained, so in the instance of std::pair<char,char> your compiler may decide to place 3-byte padding after each char for optimal alignment, so no you can't assume contiguous memory layout - end of story.
No. The elements of a vector are stored in a dynamically allocated block of memory; otherwise, the capacity of the vector could not increase. The vector object just holds a pointer to that block.
The requirement that the elements be stored sequentially applies only to the elements themselves, and not to any dynamically allocated members of those elements.
136
To answer your final question: No. The elements of a vector of vectors are not stored contiguously.
Consider the following code:
std::vector<std::vector<int> > vv;
.... fill in v[0], v[1], v[2], etc
std::vector <int> & v = vv[1];
v.push_back (23);
If they were all stored contiguously, then this would cause each element in vv[2], vv[3], etc to move. How would that possibly work, since you're just affecting a single vector 'v'?
35
std::vector< std::vector<T> > is a vector of objects, that are stored in contiguous block of memory. The fact that these objects are vectors too is irrelevant though.
Although elements of the vector are stored in the contiguous block of memory, the memory where elements reside is not the part of the vector object itself.
"is it possible to access all the elements stored in such nested structure "simply" and sequentially (via a pointer or similar) the same way it can be done for a 1-D vector?"
For accessing elements of std::vector, it's better to use operator[] or at() method than retrieving the address of first element and using pointer arithmetic. For multidimensional arrays represented as vector of vectors, I suggest you to stay with operator[], which is easy to use and easy to read as well: myVector[i][j]. Worth to see vector::at vs. vector::operator[] as well :)
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
