A deque is a sequential container optimized for fast, indexed based access and efficient insertion at either of its extremities, that is, at its beginning or end. This section provides an overview of deque .

Iterator Type

Implementation

When a deque is constructed, it has no associated storage. As items are added, blocks of storage are added to the beginning or end of the deque as necessary. As a result of this architecture, items are efficiently inserted at either extremity. Insertions and erasures expand the deque in the direction involving the least amount of copying.

A deque allocates storage in 4K blocks (a usual page size) of contiguous memory and uses an array to keep track of its blocks. Once a block is allocated to a deque , it is not deallocated until the block is destroyed.

Insertion Notes

Inserting a single item at the beginning or end of a deque takes constant time and causes a single call to the item's copy constructor. Inserting a single item into an arbitrary position takes linear time in the minimum of the distance from the insertion point to the beginning of the deque and the distance from the insertion point to the end of the deque .

If an item is inserted into a deque at an extremity, iterators and references to elements remain valid. If an item is inserted somewhere other than an extremity, all iterators and references are invalidated. If an insertion causes reallocation of memory space, all iterators and references are invalidated.

Erasure Notes

When erasing an item from a deque , the destructor is called once for each erased item and the assignment operator is called once for each item left in the deque before and after the erased item.

If the first or last item of a deque is erased, all iterators and references remain valid. If an item is erased from somewhere other than an extremity, all iterators and references are invalidated.

Common Uses

A deque is useful when order, compact storage, and fast insertion at extremities are important. A deque is ideal for implementing any kind of first in, first out (FIFO) structure. If a strict FIFO structure prohibiting index based access is required, consider using a queue adapter with a deque as the underlying container. If fast insertion near the middle of a sequential structure is desirable, consider using a list instead of a deque .

Interface

A deque has almost the same interface as a vector . Following are some additional functions.

The insert() function is required because the iterator for a deque is not simply a C pointer. Insertion and deletion of the first element in a deque has the performance of O(1). Use the pop_front() and push_front() functions to take advantage of this feature. Following is an example using these functions.

Example <ospace/osstd/examples/deque1.cpp>


  #include <iostream>
#include <deque>

void
main()
  {
  deque< int > d;
  d.push_back( 4 ); // Add after end.
  d.push_back( 9 );
  d.push_back( 16 );
  d.push_front( 1 ); // Insert at beginning.

  size_t i;
  for ( i = 0; i < d.size(); ++i )
    cout << "d[ " << i << " ] = " << d[ i ] << "\n";
  cout << "\n";

  d.pop_front(); // Erase first element.
  d[ 2 ] = 25; // Replace last element.

  for ( i = 0; i < d.size(); ++i )
    cout << "d[ " << i << " ] = " << d[ i ] << "\n";
  }

d[0] = 1
d[1] = 4
d[2] = 9
d[3] = 16
d[0] = 4
d[1] = 9
d[2] = 25