I was looking at STL containers and trying to figure out what they really are (i.e. the data structure used) when I came across the deque: at first, I thought it was a double linked list, which would allow insertion and deletion from both ends in constant time, but the promise made by the operator  to be done in constant time concerned me. Arbitrary access in a linked list should be O(n), right?
And how can it add elements in constant time if it's a dynamic array?
It should be noted that reallocation may occur, and thus O(1), like a vector, is an amortised cost.
So I'm curious about this structure that permits arbitrary access in constant time while never requiring relocation to a larger location.