The complete guide to STL: Part 3 - 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.