vector vs. deque

[dellthinker]

I'm finally seeing C++ coding in a different light, maybe the same as the more advanced developers here. I've recently found out that vector's are probably the 'best' way of storing array information, however I found out about deque's. According to the documentation on cplusplus.com

While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocation's are avoided.

So in personal opinion, would deque's be a better choice for creating array's than vectors?
Does massive reallocation's in vectors subject the array to a buffer overflow if it was ever 'flooded' with information?

[Paul McKenzie]

So in personal opinion, would deque's be a better choice for creating array's than vectors?

One major advantage of vector is that it is compatible with any 'C' or C-like routine that expects a contiguous buffer of type T (i.e. an array of T). The deque is not compatible and cannot be used this way.

A lot of C++ code uses vector not only as a resizable array, but for the purpose of using an RAII type that is compatible with legacy functions that take a T* or array of T.

Does massive reallocation's in vectors subject the array to a buffer overflow if it was ever 'flooded' with information?

I don't know what you're referring to. Please explain.

Regards,

Paul McKenzie

[nuzzle]

According to the documentation on cplusplus.com

I find this quote highly misleading.

In fact exponential growth (typically used by vector implementations) has proved more efficient than linear growth (typically used by deque implementations) in most scenarios.

So adding items to the end of a vector is likely to be much faster than adding the same number to the end of a deque, especially if the number is large.

And you're no more likely to run out of memory with vector than with deque. Not with typical usage. The question will be how much memory you have and how many items you store, not whether you store them in a vector or a deque.

[monarch_dodra]

The advantage of a deque is a relatively low worst case push_back. When you have a 1,000,000 item vector, and you need to push_back the 1,000,001st item, the reallocation is going to hurt... a lot.

They are just two different containers, they resemble each other, but at the end of the day, there are just too many considerations give you a clear cut answer.

Both vector and deque offer pretty good push_back performance. Vector seems to have a pretty good overall average case, but a bad worst case, whereas deque have an alright worst case.

Something else to consider is that deques never re-allocate. Objects are never copied around.

...

Oh yeah, push_front.

...

Personally, I usually stick with vectors, because I never need push_front, and enjoy the pointer/iterator compatibility, and the C-array style compatibility. And I'm more fluent in vector.

[Moschops]

There are many different containers to choose from; each is implemented differently, with different relative strengths. Ultimately, it's up to you to choose the best one for your purposes based on the task at hand and your own abilities, but it's worth knowing about them all.

Take a look at this diagram; it shows how someone out there picks a container type to use, and should give some idea of the relative strengths of each.

http://www.liamdevine.co.uk/code/images/container.png

[nuzzle]

The advantage of a deque is a relatively low worst case push_back. When you have a 1,000,000 item vector, and you need to push_back the 1,000,001st item, the reallocation is going to hurt... a lot.

It may take equally long to push_back the million-first item to a deque. For this reason the performance guarantee for push_back is given in amortized time. (and it's constant for both vector and deque)

If you're "hurt" by the possible bad performance of a single push_back, for example if you have hard real-time requirements, you shouldn't use any of these containers.

Something else to consider is that deques never re-allocate. Objects are never copied around.

All dynamic data structures reallocate, it's in their nature. And when deque reallocates, items may get "copied around".

[nuzzle]

Here's an interesting study,

http://www.codeproject.com/KB/stl/vector_vs_deque.aspx

[GNiewerth]

I´d like to add that deque has a larger overhead than vector, this can be a serious problem if you need to store huge amounts of data, especially with small data types. At least STLport and Dinkumware use small block sizes (2-8 Elements, depending on the data type´s size) and, IIRC, 3 pointers, which can sum up in enormous RAM consumption.

[dellthinker]

> I don't know what you're referring to. Please explain.

I suppose my original question that I didn't ask was which of the two would have a greater capacity as far as holding array's of strings or int's. Or do they have operations that are so similar that the both of them would hold the same amount of data?

When I read the following I questioned whether vector would be least resourceful when storing many arrays....

While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage,

Or, is it possible that they both store the same amount of information, whether it be a million or infinity.

[Lindley]

A vector will use less memory to store the same number of objects. Both are limited in size only by available memory, so in that respect a vector may be considered to have greater "capacity". However, when you start pushing the bounds of available memory with a single container, it's time to start questioning your design.