Use the Deque Container in C++

  1. Use the std::deque Container to Process Fast Queue Insert/Remove Operations
  2. Use std::push_back/std::push_front Methods to Insert Elements Into std::deque
  3. Use Wrapper Function for push_front Method to Implement Fixed Sized Queue

This article will demonstrate multiple methods about how to use the std::deque container in C++.

Use the std::deque Container to Process Fast Queue Insert/Remove Operations

std::deque implements a double-ended queue that provides constant time insertion and deletion operations on its ends. Thus, this data structure should be utilized in scenarios where such operations make up most of the transactions. On the downside, std::deque elements are not stored in consecutive memory locations, and it needs some extra operation to handle operations, resulting in more object sizes than the std::vector container. The following example shows a deque of strings constructed from the vector object. Note that a new element from the string input is recommended to be added using the emplace_back method.

#include <iostream>
#include <deque>
#include <vector>

using std::cout; using std::deque;
using std::endl; using std::string;
using std::vector;

template<typename T>
void printElements(deque<T> &d)
{
    cout << "[ ";
    for (const auto &item : d) {
        cout << item << ", ";
    }
    cout << "\b\b ]" << endl;
}

int main()
{
    vector<string> vec = {"plie", "flie", "blie", "clie"};;

    deque<string> deque2(vec.begin(), vec.end());
    deque2.emplace_back("hlie");
    printElements(deque2);

    exit(EXIT_SUCCESS);
}

Output:

[ plie, flie, blie, clie, hlie ]

Use std::push_back/std::push_front Methods to Insert Elements Into std::deque

std::deque has multiple built-in functions to provide rich features for element manipulation. The most common of them are push_back and push_front methods, which add the given objects as elements to the corresponding side of the deque. Notice that these functions have their reversed methods to remove the elements - pop_back and pop_front. The following example shows the basic usage of the above methods.

#include <iostream>
#include <deque>
#include <vector>

using std::cout; using std::deque;
using std::endl; using std::string;
using std::vector;

template<typename T>
void printElements(deque<T> &d)
{
    cout << "[ ";
    for (const auto &item : d) {
        cout << item << ", ";
    }
    cout << "\b\b ]" << endl;
}

int main()
{
    vector<string> vec = {"plie", "flie", "blie", "clie"};;

    deque<string> deque2(vec.begin(), vec.end());

    string str1("alie");
    deque2.push_back(str1);
    printElements(deque2);
    deque2.push_front(str1);
    printElements(deque2);

    deque2.pop_back();
    deque2.pop_front();
    printElements(deque2);

    exit(EXIT_SUCCESS);
}

Output:

[ plie, flie, blie, clie, alie ]
[ alie, plie, flie, blie, clie, alie ]
[ plie, flie, blie, clie ]

Use Wrapper Function for push_front Method to Implement Fixed Sized Queue

Another method to utilize the std::deque container to operate on it as the fixed-sized stack that stores n number of elements, and when it’s full, it automatically removes an element from the back on each new insertion. In this case, we implemented this feature by wrapping push_front and pop_back methods in a separate function. Note that the same functionality can also be achieved using the std::stack container adapter, which is extensively described on this page.

#include <iostream>
#include <deque>

using std::cout; using std::deque;
using std::endl; using std::string;

template<typename T>
void printElements(deque<T> &d)
{
    cout << "[ ";
    for (const auto &item : d) {
        cout << item << ", ";
    }
    cout << "\b\b ]" << endl;
}

template<typename T>
void pushElement(T &elem, deque<T> &d)
{
    d.push_front(elem);
    d.pop_back();
}

int main()
{
    deque<int> deque1 = {3, 5, 7, 9};
    int i1 = 11;

    printElements(deque1);
    pushElement(i1, deque1);
    printElements(deque1);

    exit(EXIT_SUCCESS);
}

Output:

[ 3, 5, 7, 9 ]
[ 11, 3, 5, 7 ]