C++ Deques

A deque, or double ended queue, is a type of sequence container, along with STL arrays, vectors and lists, which is provided as part of the Standard Template Library (STL).

A deque can hold multiple values of the same type, similarly to arrays and vectors. There are additional similarities with vectors in their flexibility of adding and removing values, but deques take things further, by allowing items to be easily added and removed from the front, as well as the back. The number of values to be stored in a deque doesn’t need to be specified when it is defined either. The size can dynamically grow and shrink as required.

The example below creates a deque of strings called names, adds four names using the ‘push_back’ and ‘push_front’ methods, then, with a range based ‘for’ loop, displays the names in the console. The ‘push_back’ method adds values to the back of the deque, whilst the ‘push_front’ method adds values to the front. In order to make use of deques, the ‘deque’ header file needs to be included.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

for (auto name: names)
{
    cout << name << endl;
}

The output from this will be as follows.

Alan
Fred
Bob
George

Notice the order of the names, as the ‘push_front’ method was used for adding ‘Fred’ and ‘Alan’, they are at the front of the deque and not the back.

Note that, like with an array and a vector, an ordinary ‘for’ loop could be used, as shown below, but a range based ‘for’ loop is simpler.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

for (unsigned int i = 0; i < names.size(); ++i)
{
    cout << names.at(i) << endl;
}

Here, the ‘size’ method of the deque is used to help determine the number of iterations of the loop, whilst the ‘at’ method, in conjunction with the loop counter variable, ‘i’, provides access to the individual deque values. As with arrays and vectors, each element in a deque has an index value, which starts at zero. An unsigned integer is again used for the loop counter.

The ‘at’ method is one of two ways to access individual values stored inside a deque. Deques can also be accessed using array like syntax.

cout << names.at(0) << endl;
cout << names[0] << endl;

Both of the above will display the first element contained within the deque. Similarly, a value within a deque can be updated using deque syntax, with the ‘at’ method or, array like syntax.

names.at(1) = "Janice";
names[1] = "Janice";

Here, the second element in the deque is updated to ‘Janice’ in both cases.

An ordinary ‘for’ loop can also be used in conjunction with an iterator to loop through a deque, in a similar way as with STL arrays.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Iterator declaration.
deque<string>::iterator i;

// Loop through the deque with the iterator.
for (i = names.begin(); i != names.end(); ++i)
{
    cout << *i << endl;
}

Here, the ‘begin’ and ‘end’ methods are used to denote the start and end of the deque. The ‘end’ method does not point to the last item in the deque, but instead points to just after the last item, which is why ‘not equal to’ is used in the loop, rather than ‘less than or equal to’. Notice that when displaying the values in the deque, within the loop, an asterisk precedes the iterator, in order to refer to the actual values within the deque. This example will display the names on a separate line as before.

It isn’t absolutely necessary to declare the iterator prior to the loop, it can be done as part of the loop.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the deque with the iterator.
for (deque<string>::iterator i = names.begin(); i != names.end(); ++i)
{
    cout << *i << endl;
}

To further simplify this, the ‘auto’ keyword can be used, which forces the compiler to determine that an iterator is to be used.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the deque with the iterator.
for (auto i = names.begin(); i != names.end(); ++i)
{
    cout << *i << endl;
}

To ensure that the values within the deque are not altered within the loop, the ‘begin’ and ‘end’ methods can be replaced by ‘cbegin’ and ‘cend’.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the deque with the iterator.
for (auto i = names.cbegin(); i != names.cend(); ++i)
{
    cout << *i << endl;
}

If required, it is also possible to loop through the deque in reverse by replacing the ‘begin’ and ‘end’ methods with ‘rbegin’ and ‘rend’.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

// Loop through the deque with the iterator.
for (auto i = names.rbegin(); i != names.rend(); ++i)
{
    cout << *i << endl;
}

In order to remove a value from a deque, there are a couple of different ways, depending on which value needs to be deleted. If the first or last value in the deque needs to be removed, then the ‘pop_front’ and ‘pop_back’ methods can be used respectively.

names.pop_front();
names.pop_back();

If a specific value needs to be removed and the index is known, the ‘erase’ method can be utilised.

names.erase(names.begin()+2);

Here, the value with an index of two, in this case, ‘Fred’, will be removed.

Some other useful methods to note are the ‘front’ method, that returns the first item in the deque and the ‘back’ method, which returns the last item.

deque<string> names;
names.push_back("Bob");
names.push_back("George");
names.push_front("Fred");
names.push_front("Alan");

cout << names.front() << endl;
cout << names.back() << endl;

This will display the following in the console.

Alan
George

It is also possible to sort the values within a deque using the ‘sort’ function. In the case of the ‘names’ deque above, this will place the values in alphabetic order. The ‘algorithm’ header file must be included for the ‘sort’ function to be utilised.

sort(begin(names), end(names));