STL deque accessing by index is O(1)?

c++ stl deque random-access
jasonline picture jasonline · Feb 19, 2010 · Viewed 12.9k times · Source

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

jasonline picture jasonline · Feb 22, 2010

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.

Related questions

What really is a deque in STL?

I was looking at STL containers and trying to figure what they really are (i.e. the data structure used), and the deque stopped me: I thought at first that it was a double linked list, which would allow insertion …

Read More
What's the difference between deque and list STL containers?

What is the difference between the two? I mean the methods are all the same. So, for a user, they work identically. Is that correct??

Read More
Why would I prefer using vector to deque

Since they are both contiguous memory containers; feature wise, deque has almost everything vector has but more, since it is more efficient to insert in the front. Why whould anyone prefer std::vector to std::deque?

Read More