DEQUE

Deque is a sequence container. The deque class implements a double-ended queue. The STL deque has many similarities with vector but they differ in one important respect: you can manipulate with both ends of deque. The deque class provides random access with constant time insertions and deletions at both the front and the rear of the container.  It supports random access iterator and [ ] operator is overloaded. It means that a deque object can be indexed like an array, and an element can be accessed using the subscript notation. 

Deques are sequence containers of choice when fast random access is needed, and if insertions or deletions are required at the beginning and the end of the sequence. It is perfect container to use if you will be frequently moving from one end to the other, for example, when rotating the contents of the container.  If many insertions and/or deletions must be done at interior positions, a better choice is a list.

  To use deque class include <deque>.

 The template specification for deque:

template <class T, class Allocator=allocator <T> > class deque 

where T is  the type of data being stored and Allocator specifies the allocator which defaults to the standard allocator.  For most cases you will simply use the default allocator.

 Deque has following constructors: 

explicit deque (const Allocator &a=Allocator() );

Constructs an empty deque.

explicit deque (size_type num, const T &val=T(),                                            const Allocator &a=Allocator() );

Constructs a deque that has num elements with value val

deque (const deque <T, Allocator> &ob);

deque’s copy constructor.

template <class InIter> deque (InIter start, InIter end,                                   const Allocator &a=Allocator() );

Constructs a deque that contains the elements in the range specified by start and end.

Although deques allow array-style indexing, their elements can be also accessed through an iterator. The iterator is defined by container classes. To obtain an iterator for deque:

deque <T>::iterator i;    

It also supports reverse iterator. The deque class overloads the assignment operator =. It also defines comparison operators:   ==, <, <=, !=, >, >=    

 Some of the most commonly used member functions: 

Member

Description

iterator begin ();

Returns an iterator to the first element in the deque.

iterator end ();

Returns an iterator to the end of the deque.

reference front();

Returns a reference to the first element in the deque

reference back();

Returns a reference to the last element in the deque

bool empty ();

Returns true if the deque contains no elements.

iterator erase (iterator i)

Removes the element pointed to by i. Returns an iterator to the element after the one removed.

iterator erase (iterator start, iterator end);

Removes the elements in range start to end. Returns an iterator to the element after the one removed.

iterator insert (iterator i, const T &val);

Inserts val immediately before the element specified by i.  An iterator to the element is returned.

void insert (iterator i, size_type num,                                         const T &val);

Inserts num copies of val immediately before the element specified by i.

template <class InIter>                                void insert (iterator i, InIter start, InIter end);

Inserts the sequence defined by start and end immediately before the element specified by i.

void pop_back ();

Removes the last element in the deque.

void pop_front ();

Removes the first element in the deque

void push_back (const T &val);

Adds an element with the value specified by val to the end of the deque.

void push_front (const T &val);

Adds an element with the value specified by val to the front of the deque.

size_type size () const;

Returns the number of elements currently in the deque.

Example: 

#include <deque>
#include <string>
#include <algorithm>
#include <assert.h>
#include <iostream>
using namespace std;

template<class T> // template function print
void print(deque<T> d) {
for(int i = 0; i < d.size(); i++) 
cout<<d[i]<<"\t";
cout<<endl;
}

main() {
deque<int> di;
deque<string> ds;

for(int i = 0; i < 20; i++)
di.push_back(i);
assert(!di.empty());
print(di);

cout<<"Changing values of elements in range 3 through 7...\n";
for(i = 3; i < 8; i++)
di[i] = 100;
print(di);

cout<<"Removing elements in range 1 through 7...\n";
for(i = 0; i < 8; i++)
di.pop_front();
print(di);

di.clear();
assert(di.empty());
cout<<endl;

assert(ds.empty());
ds.push_back("John");
ds.push_front("Tom");
ds.push_front("Jane");
ds.push_back("Anna");
assert(!ds.empty());
print(ds);

cout<<"\nSorting elements...\n";
sort(ds.begin(), ds.end());
print(ds);

cout<<"\nRemoving last element...\n";
ds.pop_back(); 
print(ds);

return 0;
}