Why is an STL deque not implemented as just a circular vector?
<p>I always thought that in C++ standard template library (STL), a double-ended queue (deque) is a size-variable array (like a vector) with circular boundary conditions, meaning there's a head pointer <code>i</code> and a tail pointer <code>j</code> both pointing to some position of an array <code>a[0..L-1]</code>. A push_front is <code>i--</code>, a push_back is <code>j++</code>, a pop_front is <code>i++</code>, and a pop_back is <code>j--</code>. When either pointer <code>i</code> or <code>j</code> reaches <code>L</code> or <code>-1</code>, it reappears on the other end of the array (<code>0</code> and <code>L-1</code> respectively). If the array size gets exhausted (pointers <code>i==j</code> after insering a new element), a larger space with double the original size is reallocated to <code>a[]</code> and data gets copied just like in a vector. There's also <code>O(1)</code> time random access taking into account the circular boundary condition. But someone tells me that inside an STL deque there's actually a pointer array pointing to many fixed-length array segments. It's much more complicated than a circular vector. What's the benefit of not using a simple circular vector to implement the functions of a deque? Will the random access get slower?</p>