STL internals: deque implementation

c++ stl internals
cprogrammer picture cprogrammer · Apr 20, 2011 · Viewed 13.4k times · Source

I am using a std::deque for storing a large collection of items.
I know that deques is implemented as a list of vectors. The size of those vectors cannot be set but I wander what is the algorithm for choosing that size.

Answer

AProgrammer picture AProgrammer · Apr 20, 2011

deque is implemented as a vector of vectors (a list of vectors would impede the constant time random access). The size of the secondary vectors is implementation dependent, a common algorithm is to use a constant size in bytes.

Related questions

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
Iteration over std::vector: unsigned vs signed index variable

What is the correct way of iterating over a vector in C++? Consider these two code fragments, this one works fine: for (unsigned i=0; i < polygon.size(); i++) { sum += polygon[i]; } and this one: for (int i=0; i < …

Read More