Why would I prefer using vector to deque

c++ stl vector deque
Leon picture Leon · Mar 17, 2011 · Viewed 41.4k times · Source

Since

  1. they are both contiguous memory containers;
  2. feature wise, deque has almost everything vector has but more, since it is more efficient to insert in the front.

Why whould anyone prefer std::vector to std::deque?

Answer

phooji picture phooji · Mar 17, 2011

Elements in a deque are not contiguous in memory; vector elements are guaranteed to be. So if you need to interact with a plain C library that needs contiguous arrays, or if you care (a lot) about spatial locality, then you might prefer vector. In addition, since there is some extra bookkeeping, other ops are probably (slightly) more expensive than their equivalent vector operations. On the other hand, using many/large instances of vector may lead to unnecessary heap fragmentation (slowing down calls to new).

Also, as pointed out elsewhere on StackOverflow, there is more good discussion here: http://www.gotw.ca/gotw/054.htm .

Related questions

How is sort for std::deque implemented?

Not so far I've learned how std::deque is implemented under the hood, and discovered that it's something like an array of pointers to n-byte arrays, where the data is actually stored. So now I have a couple of questions …

Read More
What is the easiest way to initialize a std::vector with hardcoded elements?

I can create an array and initialize it like this: int a[] = {10, 20, 30}; How do I create a std::vector and initialize it similarly elegant? The best way I know is: std::vector<int> ints; ints.push_back(10); ints.…

Read More
How do I erase an element from std::vector<> by index?

I have a std::vector<int>, and I want to delete the n'th element. How do I do that? std::vector<int> vec; vec.push_back(6); vec.push_back(-17); vec.push_back(12); vec.erase(???);

Read More