Deque

A deque is a container class template that implements a double-ended queue.

View version details

Contents

Definition
Description
Performance
Deque Operations
Page Comments

Definition

The deque template is defined in the standard header <deque>, and in the nonstandard backward-compatibility header <deque.h>.

#include<deque>
namespace std{
       template <class T, class Allocator = allocator<T> >
       class deque;
}

As with vectors, the type of the elements is passed as a first template parameter and may be of any type that is assignable and copyable. The optional second parameter defines the memory model, which by default is an allocator.

Description

The deque or "double ended-queue" is a Sequence very similar to the vector on the surface and can act as a direct replacement in many implementations. The main difference is that inserting and removing items from the beginning of a deque object are constant-time operations instead of being linear-time operations the way they are for vector. So if most operations take place at the beginning and ends of a sequence, you should consider using a deque data structure.

A simple example of creating a deque is:

std::deque<int> d; // creates deque of type int
std::deque<double> d; // creates deque of type double

Performance

Deques have the following differences compared with the abilities of vectors:

Deque allows constant time insertion/removal of elements from the beginning and end of a sequence while vector only allows elements to be inserted/removed from the end of a sequence in amortized constant time
Deque allows elements to be inserted/removed from arbitrary points in a sequence more efficiently than a vector can, although not in constant time
For sequences that consist of a large number of elements, a vector will allocate one large, contiguous block of memory while a deque will allocate several, smaller blocks of memory. Several small allocations tend to result in better performance under most operating systems
Deques provide all the capability needed to function as a stack or a queue
Deques grow more efficiently than vectors because a deque will allocate a new block of memory when the memory buffer is exausted and begin using it to store the new elements. A vector will allocate a new, larger block of memory to replace the previously used memory block and copy all of the elements to the new memory block

Deque Operations

Constructors and Destructor of Deques

Operation	Effect
deque< El > c	Creates an empty deque without any elements
deque< El > c1(c2)	Creates c1 as a copy of c2 of the same type(the copy has the same size as the original)
deque< El > c(nr)	Creates a deque c of size nr containing nr values, each equal to the default value of type El
deque< El > c(nr,el)	Creates a deque initialized with nr copies of element el
deque< El > c(beg,end)	Creates a deque initialized with the elements of the range [beg,end)
c.~deque < El >()	Destroy all components of c and free the associated memory

Nonmodifying Operations of Deques

Operation	Effect
c.size()	Returns a value of type `size_type` giving the number of values currently in c
c.empty()	Returns true if c is empty (contains zero values); otherwise returns false
c.max_size()	Returns the maximum number of elements possible
c1==c2	Returns if c1 is equal to c2
c1!=c2	Returns if c1 is not equal to c2 (equivalent to !(c1==c2))
c1<c2	Returns if c1 is less than c2
c1>c2	Returns if c1 is greater than c2 (equivalent to c2<c1)
c1<=c2	Returns if c1 is less than or equal to c2 (equivalent to !(c2<c1))
c1>=c2	Returns if c1 is greater than or equal to c2 (equivalent to !(c1<c2))
c.at(i)	Returns the element with index i (throws range error exception if i is out of range)
c[i]	Returns the element with index i (without range checking)
c.front()	Returns the first element (no check if a first element exists)
c.back()	Returns the last element (no check if a last element exists)
c.begin()	Returns a random access iterator for the first element
c.end()	Returns a random access iterator for the position after the last element
c.rbegin()	Returns a reverse iterator for the first element of a reverse iteration
c.rend()	Returns a reverse iterator for the position after the last element of a reverse iteration

Modifying Operations of Deques

Operation	Effect
c1=c2	Assigns c2 to c1, and returns the common value. The deque on the left of an assignment receives the values and size of the one on the right
c.assign(nr,el)	Assigns nr copies of el to c, overwriting the entire previous contents of c
c.assign(beg,end)	Assigns the elements of the range [beg,end)
c1.swap(c2)	Exchanges values in c1 with those in c2. The sizes are swapped as well
swap(c1,c2)	Same (as global function)
c.insert(pos,el)	Inserts el into c immediately before the value pointed to by pos, and returns an iterator pointing at the new component with value el
c.insert(pos,nr,el)	Inserts nr copies of el into c, immediately before the value pointed to by pos
c.insert(pos,beg,end)	Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)
c.push_back(el)	Adds el to the end of c, increasing the size of c by one
c.pop_back()	Removes the last value of c. The size of c is reduced by one
c.push_front(el)	Adds el to the front of c, increasing the size of c by one
c.pop_front()	Removes the first value of c. The size of c is reduced by one
c.erase(pos)	Removes the element at iterator position pos and returns the position of the next element
c.erase(beg,end)	Removes all elements of the range [beg,end) and returns the position of the next element
c.resize(nr)	Changes the number of elements to nr (if size() grows, new elements are created by their default constructor)
c.resize(nr, el)	Changes the number of elements to nr (if size() grows, new elements are copies of el)
c.clear()	Removes all values of c. The size of c is reduced to zero

References:

http://www.mtsu.edu
http://www.codeproject.com
Nicolai M. Josuttis: "The C++ Standard Library"

Example:

Example - creation of a deque

Problem

The following example of program illustrates creation of a deque.

Workings

#include <iostream>
using std::cout;
using std::endl;
 
#include <deque>     // deque class-template definition
#include <algorithm> // copy algorithm
#include <iterator>  // ostream_iterator
 
int main()
{
   std::deque< int > values; // create deque of type int
   std::ostream_iterator< int > output(cout, " ");
 
   values.push_front(2);
   values.push_front(3);
   values.push_back(1);
 
   cout << "values contains: ";
   // use subscript operator to obtain elements of values
   for ( int i = 0; i < values.size(); i++ )
      cout << values[i] << ' ';
   cout << endl;
   return 0;
}

Solution

Output:

values contains: 3 2 1

References:

http://www.smu.ca/academic/science/compsci

Page Comments

You must login to leave a messge