12,883,114 members (37,149 online)
alternative version

#### Stats

46.4K views
37 bookmarked
Posted 21 Oct 2007

# The complete guide to STL: Part 3 - Deque

, 21 Oct 2007 CPOL
 Rate this:
An introduction to STL deque.

## Introduction to deque

In the third part of the tutorial series, we will learn about the STL deque container. The deque (double ended queue) container combines the facilities offered by the vector and the list into a single class. It occupies noncontiguous memory, divided into large contiguous memory blocks, allocated proportionally to the growth of the container and managed by vectors of pointers. This implementation allows the use of all basic vector operations, and also the `push_front()` and `pop_front()` functions. The implementation also allows using the `[]` operator for accessing an element, just like in the vector case. Using indexed access assumes going through a preliminary phase first, where the memory block containing the searched element is identified. The rest happens like in the vector case.

All the information necessary for understanding deque was presented when the vector container was introduced. Thus, we will leave most of the details out of this article, concentrating on the examples, for a better understanding of how to use the deque container.

### Creating a deque: Constructors

In order to use deque, we must include its header `<deque>`.

```#include <deque>
using namespace std;```

In the following examples, we create some deque objects and we use the copy constructor on deques.

```// create an empty deque

deque<double> deq0;

// create a deque with 5 empty elements

deque<double> deq1(5);

// create a deque with 5 elements, each element having the value 2.0

deque<double> deq2(5, 2.0);

// create a deque based on an array

double array[8] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
deque<double> deq3(array, array + 8);

// use the copy constructor to copy the contens of deq3 in deq3copy

deque<double> deq3copy(deq3);```

### Printing the elements of a deque

Just like in the vector case, to print the elements of a deque, we can use the `[]` operator, the `at()` member function, and iterators. Below, we create the `print()` function for printing a deque:

```void print(deque<double> deq, char * name)
{
deque<double>::iterator it;

cout << name << ": ";

for(it = deq.begin(); it != deq.end(); ++it)
cout << *it << " ";

cout << endl;
}```

Below, we print the elements of the deque in reverse order:

```double array[8] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
deque<double> deq(array, array + 8);

print(deq, "deq");

// print the deque in reverse order

cout << "deq in reverse order: ";
deque<double>::reverse_iterator rit;
for(rit = deq.rbegin(); rit != deq.rend(); ++rit)
cout << *rit <<  " ";

// Output

// deq: 3.45 67 10 0.67 8.99 9.78 6.77 34.677

// deq in reverse order: 34.677 6.77 9.78 8.99 0.67 10 67 3.45```

### Inserting elements into a deque

For inserting elements into a deque, we can use the `push_back()`, `push_front()`, and `insert()` functions.

```deque<double> deq;
deque<double>::iterator it;

// add an element at the end of the deque

deq.push_back(6.67);

// add an element at the beginning of the deque

deq.push_front(4.56);

print(deq, "deq");

// insert an element in the second position of the deque

it = deq.begin();
++it;
deq.insert(it, 40.04);

print(deq, "deq");

// insert an element three times at the beginning of the vector

it = deq.begin();
deq.insert(it, 3, 0.5);

print(deq, "deq");

// insert the first four values from the array at the end of the deque

double array[8] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
it = deq.end();
deq.insert(it, array, array + 4);

print(deq, "deq");

// Output

// deq: 4.56 6.67

// deq: 4.56 40.04 6.67

// deq: 0.5 0.5 0.5 4.56 40.04 6.67

// deq: 0.5 0.5 0.5 4.56 40.04 6.67 3.45 67 10 0.67```

### Removing elements from a deque

For removing elements from a deque, we can use the `pop_back()`, `pop_front()`, and `erase()` functions.

```double array[10] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677, 10.25, 89.76};
deque<double> deq(array, array + 10);
deque<double>::iterator it;

print(deq, "deq");

// remove the last element of the deque

deq.pop_back();

print(deq, "deq");

// remove the first element of the deque

deq.pop_front();

print(deq, "deq");

// erase the third element of the deque

it = deq.begin();
it += 2;
deq.erase(it);

print(deq, "deq");

// remove all elements from the deque

deq.clear();

if(deq.empty())
cout << "deq is empty" << endl;

// Output

// deq: 3.45 67 10 0.67 8.99 9.78 6.77 34.677 10.25 89.76

// deq: 3.45 67 10 0.67 8.99 9.78 6.77 34.677 10.25

// deq: 67 10 0.67 8.99 9.78 6.77 34.677 10.25

// deq: 67 10 8.99 9.78 6.77 34.677 10.25

// deq is empty```

### Sizing and resizing a deque

For this purpose, the `resize()` function will be used. Unlike the vector, deque does not have the `capacity()` and `reserve()` member functions.

```deque<double> deq;
deq.push_back(3.45);
deq.push_back(19.26);
deq.push_back(3.517);

cout << "deq size is " << deq.size() << endl;
print(deq, "deq");

// case when new size <= size of vector

deq.resize(1);

cout << "deq size is " << deq.size() << endl;
print(deq, "deq");

// case when new size > size of vector

deq.resize(5);

cout << "deq size is " << deq.size() << endl;
print(deq, "deq");

// Output

// deq size is 3

// deq: 3.45 19.26 3.517

// deq size is 1

// deq: 3.45

// deq size is 5

// deq: 3.45 0 0 0 0```

### Two dimensional deques

Just like two dimensional vectors are vectors of vectors, two dimensional deques are deques of deques.

```deque< deque<double> > matrix;

deque<double> deq1(5, 8.43);
deque<double> deq2(4, 12.099);

matrix.push_back(deq1);
matrix.push_front(deq2);

deque< deque<double> >::iterator it2d;
for(it2d = matrix.begin(); it2d != matrix.end(); ++it2d)
print(*it2d, "row");

// Output

// row: 12.099 12.099 12.099 12.099

// row: 8.43 8.43 8.43 8.43 8.43```

In the above code, notice that we called the `print()` function to print a deque. This shows that an element of a two dimensional deque is, indeed, a deque.

### Deques of user defined elements

Deques can store pointers and also user defined elements. In what follows, we will combine those two possibilities, and we will create a deque that stores pointers of user defined elements.

First, we create the `Point` class, also presented when we discussed vector.

```class Point
{
int x;
int y;

public:

// constructor

Point()
: x(0), y(0)
{
}

// constructor

Point(int px, int py)
: x(px), y(py)
{
}

// copy constructor

Point(const Point& pt)
: x(pt.x), y(pt.y)
{
cout << "Inside the copy constructor!" << endl;
}

// print the Point

void print()
{
cout << "Point: " << x << ", " << y << endl;
}

// destructor

~Point()
{
}
};```

Now, we define a deque capable of storing pointers to `Point` objects:

```deque<Point*> deq;

Point * p1 = new Point(1, 4);
Point * p2 = new Point(3, 5);
Point * p3 = new Point(10, 43);

deq.push_back(p1);
deq.push_back(p2);
deq.push_back(p3);

for(int index = 0; index < deq.size(); ++index)
deq.at(index)->print();```

### Complexity

The deque container is not recommended for insertion/deletion in/from the interior of the container. These operations are optimized only in the idea of minimizing the number of copied elements, for keeping the illusion that the elements are stored contiguous.

The deque container cannot contain invalid iterators because it doesn't give up the allocated memory. Even when inserting an element in a completely occupied memory block, an additional memory block is allocated, but all loaded iterators point to memory zones that still belong to the program.

The deque container is preferred over vector when the number of stored elements cannot be predicted or varies between runs. For high performance programs, the deque is used when the container is constructed, and then the container is copied into a vector, for easier data processing.

## Share

 Software Developer (Senior) Romania
No Biography provided

## You may also be interested in...

 First Prev Next
 Very good serie unpocolocos24-Nov-11 6:39 unpocolocos 24-Nov-11 6:39
 My vote of 5 unpocolocos24-Nov-11 6:34 unpocolocos 24-Nov-11 6:34
 very good series toxcct18-Nov-07 5:16 toxcct 18-Nov-07 5:16
 nice ThatsAlok17-Nov-07 0:04 ThatsAlok 17-Nov-07 0:04
 really it is impressive, a nice refresher "Opinions are neither right nor wrong. I cannot change your opinion. I can, however, change what influences your opinion." - David CrowNever mind - my own stupidity is the source of every "problem" - Mixture cheers, Alok Gupta VC Forum Q&A :- I/IV Support CRY- Child Relief and You
 Re: nice cristitomi17-Nov-07 8:50 cristitomi 17-Nov-07 8:50
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Apr-17 22:52 Refresh 1