title: What really is a deque in STL?
body: <p>I was looking at STL containers and trying to figure what they really are (i.e. the data structure used), and the <em>deque</em> stopped me: I thought at first that it was a double linked list, which would allow insertion and deletion from both ends in constant time, but I am troubled by <a href="http://en.cppreference.com/w/cpp/container/deque/operator_at" rel="noreferrer">the promise made</a> by the operator [] to be done in constant time. In a linked list, arbitrary access should be O(n), right?</p>
  
  <p>And if it's a dynamic array, how can it <a href="http://en.cppreference.com/w/cpp/container/deque/push_back" rel="noreferrer">add elements</a> in constant time? It should be mentioned  that reallocation may happen, and that O(1) is an amortized cost, <a href="http://en.cppreference.com/w/cpp/container/vector/push_back" rel="noreferrer">like for a vector</a>.</p>
  
  <p>So I wonder what is this structure that allows arbitrary access in constant time, and at the same time never needs to be moved to a new bigger place.</p>