Why is std::vector contiguous?

Question

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?

`std::vector` is the abstraction over a C-style dynamic array. What you're describing sounds a whole lot like `std::deque`. — Xeo, Nov 09 '13 at 12:46
That's why you have e.g. [`std::deque`](http://en.cppreference.com/w/cpp/container/deque) for when you don't need contiguous memory access. — Some programmer dude, Nov 09 '13 at 12:46
There are lots of use cases where contiguous storage is required or a significant improvement from a performance perspective. — Joe, Nov 09 '13 at 12:47
The question is equivalent to "Why is the class for managing a dynamic array called `vector`?". It has to be called something. — Mike Seymour, Nov 09 '13 at 13:38
The comments and answers talking about `std::deque` should note that it is optimized for inserts, not traversal/appends, and thus normally has small nodes: MSVC uses only 16 bytes! libstd++ uses a more reasonable 512 bytes, but comments that with "no investigation has been done since inheriting the SGI code". A traversal/`append()` tuned container would presumably grow to something more like 4/16K before "blocking" the data, so there may be some room for alternatives here. — Simon Buchan, Nov 22 '13 at 05:20

Alan Stokes · Accepted Answer · 2013-11-09T13:15:07.303

27

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.

edited Nov 09 '13 at 13:15

answered Nov 09 '13 at 12:48

Alan Stokes

18,815
3
45
64

1

To be fair, "some constant number of times" -- is the growth factor of `std::vector` set by the standard? If the `std::vector` grows by a factor of 1.5, you'll get an average of 2 copies, if a growth factor of 2, 1 copy. – Yakk - Adam Nevraumont Nov 09 '13 at 13:36
Agreed. The standard requires amortized O(1) for append which I believe implies exponential growth, but certainly doesn't specify a factor. – Alan Stokes Nov 09 '13 at 13:40
What do you mean by if it grows by a factor of 1.5 or 2? and what's the difference between amortized O(1) and O(1)? – deller Nov 09 '13 at 17:06
5

If the vector becomes full you need to make it bigger, and you need to do it by increasing the size by some factor. (Just adding a constant amount each time works very badly). That factor can be 2, but 1.5 has some advantages. Anything > 1 theoretically gives the same amortized O(1) behaviour. And O(1) would imply that every append took constant time; amortized O(1) means on average they have constant time, but occasional ones are slow (at the point where the array gets copied). – Alan Stokes Nov 09 '13 at 17:17
The first line of this response is technically untrue. For those familiar with previous versions of the standard, `std::vector` didn't guarantee contiguousness in the past (though every implementation did provide it). It was modified so that it did. – Pseudonym Nov 21 '13 at 05:21
"if you append to a vector a million elements one at a time, each element will have been copied on average around once." How is this possible? Isn't every element copied to a new array every time the capacity is increased? – cambunctious Aug 19 '16 at 19:42
1

@cambunctious Most of the copies occur while the vector is much smaller than its final size. Suppose the capacity is doubled each time. Then the last 500k elements never got copied at all - they were inserted at their final positions. The previous 250k got copied exactly once, when the capacity went from 500k to 1000k. The 125k before that were copied twice, and so on. The very first element will have been copied around 20 times, but that has little effect on the average. – Alan Stokes Aug 22 '16 at 04:59
@Alan Stokes Mind blown. Thanks for explaining, I'm glad to have that understanding. – cambunctious Aug 22 '16 at 05:07

score 13 · Answer 2 · edited Nov 09 '13 at 15:12

The standard C++ library defines a non-contiguous array-like container, too: std::deque<T>. Iteration over a std::deque<T> is much slower than iterating over a std::vector<T>. If the operation is fairly trivial, it may be something like 5 times slower: these are actual times I get when comparing accumulating a sequence of integers. This is the cost you are paying for a non-contiguous representation!

The reason for this fairly steep slowdown is that gcc knows how to vectorize the loop over a std::vector<int> but not for a std::deque<int>. Even without vectorization the iteration is about 30% slower. That is, the fairly small cost of std::vector<T>'s re-allocations actually don't really matter that much!

Renan Gemignani · Answer 3 · 2013-11-09T15:18:10.350

There are a few reasons for this:

First, iteration over a contiguous container is a lot faster than over a non-contiguous one due to two factors: the first is branch prediction - the processor doesn't need to throw away its pipeline every time you finish reading one of the sub-containers, and less pipeline resets means faster code. The second is that it's much easier to fully cache a contiguous block of memory than a bunch of assorted small blocks, making it much more likely that your array is cached on its entirety.

Second, there's a lot of C++ code being written out there that has to interact with C code, and a lot of that code will expect a contiguous space of memory when receiving an array/buffer, because that's the least data structure implementation-dependent way to do it. When you're interacting with code that expects buffers/arrays constantly, the overhead of converting your std::deque into an array takes its toll compared to the practically instantaneous passage of an std::vector to an array (which can be basically just giving a pointer to the internal array).

All of this justifies the existence of a contiguous container. As others have said, when you don't need either fast iteration or contiguousness of memory, you can always use an std::deque.

Steve · Answer 4 · 2013-11-09T13:21:07.507

By making std::vector contiguous, it can be treated much like an array. However, it's also resizable. Its size is definable at runtime, rather than compile time. Also, a vector can be used to allocate memory for functions that require a buffer. The advantage of this is the memory will be free'd by the vector when it goes out of scope. For example, when using ReadFile a vector can be used to create a buffer.:

unsigned int bytesRead = 0;
std::vector<char> buffer(fileSize);
// open file, etc.
ReadFile(hFileIn, buffer.data(), buffer.size(), &bytesRead, nullptr);

Note that data is new in C++11. In older code you will probably seen an equivalent &(buffer.at(0)) or &(buffer[0]) which returns the address of the first element.

A std::deque would be a better fit for what you're describing.

score 3 · Answer 5 · answered Nov 09 '13 at 16:28

As a complement to the other answers (they are quite complete), there is one situation when you do prefer vectors to not be contiguous: when you need to resize a vector concurrently. That is why Intel Thread Building Block provides tbb::concurrent_vector, which is more or less what you said you would expect

"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."

Then, a comparison between tbb::concurrent_vector and std::vector would give you a better understanding of the advantages (speed) and disadvantages (cannot grow std::vector concurrently) of contiguous memory. I expect tbb::concurrent_vector to be better optimized than std::deque and that is why tbb::concurrent_vector vs std::vector is a more fair comparison.

Why is std::vector contiguous?

5 Answers5

Linked