In this article, we will learn about the concept behind a deque and different ways to initialize a deque in C++ Standard Template Library (STL).

Table of contents:

1. What is a Deque?
2. C++ default constructor
3. C++ fill constructor
4. C++ range constructor
5. C++ move constructor
6. C++ copy constructor
7. C++ initializer_list constructor

Let us get started with Different ways to initialize Deque in C++ STL.

What is a Deque?

A deque, also known as double-ended queues, are indexed sequence containers part of the STL. The benefit of a deque is that it has the ability to expand and contract at both the ends (front and back), through insertion and deletion of elements at run time. Unlike a vector, a deque does not store its elements at contiguous memory locations and its memory is usually dynamically allocated. The following is a visual representation of a deque:

In order to implement a deque, we must first use the class "deque" from the STL as a header. This allows us make use of any functions available in the STL. We will also implement using namespace std, in order to make cleaner the coding process.

#include <deque> 
using namespace std;

Below is a list of member functions we will be utilizing in this article:

1. size(): returns the total number of elements deque contains.
2. begin(): returns first element of a deque.

Below is a list of 6 ways to initialize a deque from the deque header:

1. C++ default constructor
2. C++ fill constructor
3. C++ range constructor
4. C++ move constructor
5. C++ copy constructor
6. C++ initializer_list constructor

Lets look at the details of initialization for each way:

1. C++ default constructor

The C++ default contructor will give us the ability to construct an empty deque and initialize it with zero elements. This initialization technique gives us a time complexity of 0(1).

Implementation

int main() {

   deque<int> d;

   cout << "Size of deque = " << d.size() << endl;

   return 0;
}

Output

Size of deque = 0

2. C++ fill constructor

The C++ fill constructor will give us the ability to construct and initialize a deque with n number of elements and assign a value to each element. Using [] lets us access particular elements of the deque. This initialization technique gives us a linear time complexity of 0(n).

Implementation

int main() {

   deque<int> d(4, 7);

   cout << "Elements of deque are" << endl;

   for (int i = 0; i < d.size(); ++i)
      cout << d[i] << endl;

   return 0;
}

Output

Elements of deque are
7
7
7
7

3. C++ range constructor

The C++ range constructor will give us the ability to construct a deque and initialize it with elements that are in a range between first to last using {}. This initialization technique gives us a linear time complexity of 0(n).

Implementation

int main() {

   deque<int> d1 = {1, 2, 3, 4, 5, 6, 7};
   deque<int> d2(d1.begin(), d1.begin() + 5);

   cout << "Elements of deque are" << endl;

   for (int i = 0; i < d2.size(); ++i)
      cout << d2[i] << endl;

   return 0;
}

Output

Elements of deque are
1
2
3
4
5

4. C++ move constructor

The C++ move constructor will give us the ability to construct a new deque and initialize with elements from another deque. This initialization technique gives us a linear time complexity of 0(n).

Implementation

int main() {

   deque<int> d1 = {1, 2, 3, 4};
   deque<int> d2(move(d1));

   cout << "Size of deque d1 is " << d1.size() << endl;
   cout << endl;

   cout << "Elements of deque d2 are" << endl;

   for (int i = 0; i < d2.size(); i++)
      cout << d2[i] << endl; 

   return 0;
}

Output

Size of deque d1 is 0

Elements of deque d2 are
1
2
3
4

5. C++ copy constructor

The C++ copy constructor will give us the ability to construct a new deque and initialize it with a copy of elements present in another existing deque. This initialization technique gives us a linear time complexity of 0(n).

Implementation

int main() {

   deque<int> d1 = {1, 2, 3};
   deque<int> d2(d1);

   cout << "Elements of deque d2 are" << endl;

   for (int i = 0; i < d2.size(); ++i)
      cout << d2[i] << endl;

   return 0;
}

Output

Elements of deque d2 are
1
2
3

6. C++ initializer_list constructor

The C++ initializer_list constructor will give us the ability to construct a deque from a previously initialized list. This initialization technique gives us a linear time complexity of 0(n).

Implementation

int main() {

   auto list = {1, 2, 3};
   deque<int> d(list);

   cout << "Elements of deque d are" << endl;

   for (int i = 0; i < d.size(); i++)
      cout << d[i] << endl;

   return 0;
}

Output

Elements of deque d are
1
2
3

The following are deque member functions that can be used to insert and remove elements from a deque:

1. push_front(): Inserts new element at the front of a deque.
2. push_back(): Inserts new element at the end of a deque.
3. pop_front(): Removes first element from a deque.
4. pop_back(): Removes last element from a deque

Implementation of push_front() and push_back()

int main() {

  deque<int> dequeList;
  dequeList.push_front(1); // SECOND IN LIST INDEX 1
  dequeList.push_front(2); // FRONT OF LIST INDEX 0
  dequeList.push_back(3);  // INDEX 2
  dequeList.push_back(4);  // INDEX 3
  
  for (int i = 0; i < dequeList.size(); i++)
      cout << dequeList[i] << endl;
}

Output

2
1
3
4

Implementation of pop_front() and pop_back()

int main() {

  deque<int> dequeList;
  dequeList.push_front(1); // SECOND IN LIST INDEX 1
  dequeList.push_front(2); // FRONT OF LIST INDEX 0
  dequeList.push_back(3);  // INDEX 2
  dequeList.push_back(4);  // INDEX 3
  
  dequeList.pop_back(); 
  dequeList.pop_front(); 
  
  
  for (int i = 0; i < dequeList.size(); i++)
      cout << dequeList[i] << endl;
}

Output

1
3

Practical applications of deque

1. Internet Browser History: Recently visited websites will be inserted to one end of the deque, when history limit is reached, elements at front are removed from deque to make room for new insertions.
2. Storing a software application's list of undo operations.

With this article at OpenGenus, you must have the complete idea of Different ways to initialize Deque in C++ STL.