Stl Deque Accessing by Index Is O(1)

STL deque accessing by index is O(1)?

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.

how does random access of an element in deque gives constant time complexity?

A deque is typically implemented as a two-layer structure, the top level is an array of pointers to fixed-sized chunks. Using knowledge of that size it is constant complexity to determine which chunk holds the item of interest and constant complexity to determine which item in the chunk is being requested.

Just because it is constant does not indicate that it is always a simple direct memory access, only that all accesses for that particular operation will require the same steps.

Does deque provide O(1) complexity when inserting on top

The cppreference entry for std::deque gives the following complexity:

The complexity (efficiency) of common operations on deques is as follows:

• Random access - constant O(1)
• Insertion or removal of elements at the end or beginning - amortized constant O(1)
• Insertion or removal of elements - linear O(n)

which is consistent with the draft C++ standard section 23.3.3.1 Class template deque overview which says (emphasis mine):

A deque is a sequence container that, like a vector (23.3.6), supports random access iterators. In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time. That is, a deque is especially optimized for pushing and popping elements at the beginning and end. As with vectors, storage management is handled automatically.

For std::vector cppreference says:

The complexity (efficiency) of common operations on vectors is as follows:

• Random access - constant O(1)
• Insertion or removal of elements at the end - amortized constant O(1)
• Insertion or removal of elements - linear in distance to the end of the vector O(n)

which is consistent with the draft standard section 23.3.6.1 Class template vector overview:

A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency.[...]

What really is a deque in STL?

A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector.

There’s a great analysis of the performance characteristics and how it compares to the vector over at CodeProject.

The GCC standard library implementation internally uses a T** to represent the map. Each data block is a T* which is allocated with some fixed size __deque_buf_size (which depends on sizeof(T)).

Complexity of stl deque::insert()

std::deque is normally (always?) implemented as a collection of chunks of memory, but it won't normally insert a whole new chunk just for you to insert one new element in the middle of the collection. As such, it'll find whether the insertion point is closer to the beginning or end, and shuffle the existing elements to make room for the new element in an existing chunk. It'll only add a new chunk of memory at the beginning or end of the collection.

Random access iterators and deque

The RandomAccessIterator concept requires that the + and - operations must be implemented in constant time:

From [iterator.concept.random.access]:

The RandomAccessIterator concept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.

This means that any standard-compliant container that implements a random-access iterator must provide constant-time element retrieval.

std::deque is contiguous memory container or not?

There is no conflict between the two quotes. Scott uses the term "contiguous container" in a sense a little wider than you might have seen it used elsewhere.

Scott writes (emphasize mine):

Contiguous-memory containers (also known as array-based containers] store their elements in one or more (dynamically allocated) chunks of memory, [...]

As the quote from cppref states, std::deque uses multiple arrays to store the elements. Within each array the elements are contiguous. Scott does not claim that all elements in a std::deque are contiguous in one chunk of memory.

deque::insert() at index?

There is a deque::insert(iterator pos, const T&x) function taking the position pos as deque::iterator and a single element. Using this method you could insert all elements one by one. pos can easily be obtained (if you have an index before which you want to insert the element) by deque.begin()+index. The insert method returns an iterator for the newly inserted element, simply increment this returned iterator to get the next position:

deque::iterator it = myDeque.begin()+index;
while(n--) {
  it = myDeque.insert(it, currentElement);
  it++;
  currentElement = ... // However you get your next element ...
}

This however cantake O(n*k) time, since insertion of a single element is (iirc) a linear time operation iirc.

The second overload is deque::insert(iterator pos, InputIterator f, InputIterator l): Remember that simple pointers also fulfill the requirements of an STL input iterator, so if you have a C-Style array T array[] of length n containing your elements, you could insert all elements from this array with

d.insert(pos, array, array+n);

This operation can be carried out in linear time, i.e. O(n+k). I'm not sure if this is guaranteed by the standard, but I suppose that most implementation will do it efficiently.

EDIT

I quickly checked with Microsoft's implementation, they do it by a sequence of either push_back or push_front, whatever is closer to pos and then rotating the elements to their final place, which guarantees the above O(n+k) complexity. Of course, that could also be done "by hand" like:

size_type _Off = pos - d.begin();
size_type _Oldsize = d.size();
if (_Off <= d.size() / 2)
{   // closer to front, push to front then rotate
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  size_type _Num = d.size() - _Oldsize;
  std::reverse(d.begin(), d.begin() + _Num); // flip new stuff in place
  std::rotate(d.begin(), d.begin() + _Num, begin() + _Num + _Off);
}
else
{ // closer to back
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  std::rotate(begin() + _Off, begin() + _Oldsize, end());
}

(I copied the code from Microsofts implementation of deque::insert, removing debug code and exception handling,

Deque index-iterator conversion

we need to make begin() + i which will take linear time.

No it won't.

Iterators that support operator+ should do it in constant time (this is true for the standard iterators, user-defined iterators could define operator+ that is linear, but that would be unconventional).

Iterators that don't support it in constant time need to be advanced with std::advance not operator+

std::deque::iterator is a random-access iterator, so begin() + i is valid and takes constant-time.

---

Related Topics