11,805,316 members (65,362 online)

# The complete guide to STL: Part 3 - Deque

, 21 Oct 2007 CPOL 41.5K 35
 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.

## About the Author

 Software Developer (Senior) Romania
No Biography provided

## Comments and Discussions

 View All Threads First Prev Next
 My vote of 5 unpocolocos24-Nov-11 6:34 unpocolocos 24-Nov-11 6:34
 Last Visit: 31-Dec-99 18:00     Last Update: 9-Oct-15 11:57 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.