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.

The declaration and initialisation of the deque can be done more efficiently by combining the two, whilst still allowing the loop to process the deque in the same way. This will include the names in the order that they are specified.

deque<string> names = {
    "Bob",
    "George",
    "Fred",
    "Alan"
};

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 = {
    "Bob",
    "George",
    "Fred",
    "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 declaration.
deque<string> names = {
    "Bob",
    "George",
    "Fred",
    "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 declaration.
deque<string> names = {
    "Bob",
    "George",
    "Fred",
    "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 declaration.
deque<string> names = {
    "Bob",
    "George",
    "Fred",
    "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 declaration.
deque<string> names = {
    "Bob",
    "George",
    "Fred",
    "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 declaration.
deque<string> names = {
    "Bob",
    "George",
    "Fred",
    "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 it the deque and the ‘back’ method, which returns the last item.

// Deque declaration.
deque<string> names = {
    "Bob",
    "George",
    "Fred",
    "Alan"
};

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

This will display the following in the console.

Bob
Alan

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));

Multidimensional Deques

Multidimensional deques are useful where you have more than one piece of information, so, to continue with the above example, if it were necessary to store the names of different groups of people, with four people in each group.

deque<deque<string>> names = {
    { "Bob", "George", "Fred", "Alan" },
    { "Andrew", "Fiona", "Simone", "Ben" },
    { "Zoe", "Taylor", "Christine", "Joanne" },
    { "Sally", "Amanda", "Arnold", "Tony" },
    { "Samantha", "Michael", "Tom", "Jimmy" }
};

A two dimensional deque, such as the one above, is in effect a deque of deques. As with a one dimensional deque, an individual element can be accessed in one of two ways, either deque syntax or array syntax. Examples of both of these are shown below, where the first value of the third inner deque, in this case ‘Zoe’, is output to the console.

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

In order to process the information in a two dimensional deque, nested ‘for’ loops need to be used, one to process the rows and another for the columns within each row. The number of rows to iterate over in the outer loop is calculated using the ‘size’ method of the outer deque, whilst the number of columns is calculated using the ‘size’ method of an inner deque.

In this example, the outer loop displays a heading for the group, with the inner loop displaying the individual names in the group, each on a separate line.

// Two dimensional deque.
deque<deque<string>> names = {
    { "Bob", "George", "Fred", "Alan" },
    { "Andrew", "Fiona", "Simone", "Ben" },
    { "Zoe", "Taylor", "Christine", "Joanne" },
    { "Sally", "Amanda", "Arnold", "Tony" },
    { "Samantha", "Michael", "Tom", "Jimmy" }
};

// Process the rows in the outer deque.
for (unsigned int i = 0; i < names.size(); ++i)
{
    // Group heading.
    cout << "Group " << i + 1 << ":" << endl;
    
    // Process the columns containing the names in the inner deque.
    for (unsigned int j = 0; j < names.at(i).size(); ++j)
    {
        // Group name.
        cout << names.at(i).at(j) << endl;
    }
    
    // Line space between groups.
    cout << endl;
}

The output from this is shown below.

Group 1:
Bob
George
Fred
Alan

Group 2:
Andrew
Fiona
Simone
Ben

Group 3:
Zoe
Taylor
Christine
Joanne

Group 4:
Sally
Amanda
Arnold
Tony

Group 5:
Samantha
Michael
Tom
Jimmy