Menu
Besides the fact that the standard defines it to be contiguous, why is std::vector contiguous?
If it runs out of space, it needs to reallocate a new block and copy the old block to the new one before continuing.
What if it wasn't contiguous? When the storage fills up, it would just allocate a new block and keep the old block. When accessing through an iterator, it would do simple >, < checks to see which block the index is in and return it. This way it doesnt need to copy the array every time it runs out of space.
Would this really work/be better? or am i missing something?
914
Yes, the elements of a std::vector are guaranteed to be contiguous.
Yes the memory of std::array is contiguous.
All the data in a vector is contiguous where the std::list allocates separately memory for each element.
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.
If std::vector didn't guarantee contiguousness, a new container would be invented which did.
The contiguity guarantee makes it easier to inter-operate with existing code that expects a contiguous array, and also gives very good performance because it is cache-friendly. (Inserting/deleting in the middle is in practice very fast for moderate sizes because of this.)
Copying the array on expansion is surprisingly cheap - if you append to a vector a million elements one at a time, each element will have been copied on average around once.
150
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
