STL DEQUE a.k.a. DECK

STL DEQUE

• Acronym of double-ended queue.
• Double-ended queues are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.
• They allow for the individual elements to be accessed through random access iterators, with storage always handled automatically (expanding and contracting as needed).
• Individual elements can be accessed by their position index.
• Iteration over the elements can be performed in any order.
• Elements can be efficiently added and removed from any of its ends (either the beginning or the end of the sequence).

COMPARISON TO VECTORS


Therefore they provide a similar functionality as the one provided by vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence and not only at its end. On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.

Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.


Example:

// deque::empty
# include < iostream >
# include < deque >
using namespace std;

int main ()
{
  deque< int > mydeque;
  int sum (0);

  for (int i=1;i<=10;i++) mydeque.push_back(i);

  while (!mydeque.empty())
  {
     sum += mydeque.front();
     mydeque.pop_front();
  }

  cout << "total: " << sum << endl;
  
  return 0;
}