STL deque accessing by index is O(1)?

Question

I've read that accessing elements by position index can be done in constant time in a STL deque. As far as I know, elements in a deque may be stored in several non-contiguous locations, eliminating safe access through pointer arithmetic. For example:

abc->defghi->jkl->mnop

The elements of the deque above consists of a single character. The set of characters in one group indicate it is allocated in contiguous memory (e.g. abc is in a single block of memory, defhi is located in another block of memory, etc.). Can anyone explain how accessing by position index can be done in constant time, especially if the element to be accessed is in the second block? Or does a deque have a pointer to the group of blocks?

Update: Or is there any other common implementation for a deque?

Answer 1

If deque is implemented as a ring buffer on top of std::vector, which reallocates itself when it grows in size, then accessing by index is indeed O(1).

The standard provides evidence that such implementation was meant--at least it conforms to standard in complexity estimations. Clauses 23.2.1.3/4 and 23.2.1.3/5 require that

• inserting to the beginning or to the end of a deque require constant time, while insertion to the middle requires linear time of deque's size

• when erasing elements from the deque, it may call as many assignment operators, as the distance from the elements being erased to the end of the deque is.

And, of course, you should count on standard requirements instead of your own vision on how containers and algorithms could be implemented.

Answer 2

I found this deque implementation from Wikipedia:

Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.

I guess it answers my question.