Deque

In this tutorial, we will explore the deque (double-ended queue) container in C++ STL. A deque is a sequence container that allows fast insertion and deletion at both ends. It provides dynamic size arrays with efficient access to elements from both ends.

Introduction

The deque container is part of the Standard Template Library (STL) in C++. It stands for "double-ended queue" because it supports fast insertions and deletions at both the front and back. This makes it different from a vector, which only allows efficient operations at the back. Deques are particularly useful when you need to frequently add or remove elements from either end of the container.

Core Content

What is a Deque?

A deque is a sequence container that supports fast insertions and deletions at both the front and back. It is implemented as a series of chunks or blocks, which allows for efficient access to elements from both ends. This makes deques ideal for applications where you need frequent modifications at both ends.

Basic Operations

Creating a Deque

You can create a deque using the std::deque template class. Here's how you can declare and initialize a deque:

1#include <iostream>
2#include <deque>
3 
4int main() {
5  std::deque<int> dq = {1, 2, 3, 4, 5};
6  
7  for (const auto& elem : dq) {
8      std::cout << elem << " ";
9  }
10  
11  return 0;
12}

1 2 3 4 5

Adding Elements

You can add elements to a deque using push_front() and push_back() methods. These methods allow you to insert elements at the front and back of the deque, respectively.

1#include <iostream>
2#include <deque>
3 
4int main() {
5  std::deque<int> dq = {1, 2, 3};
6  
7  dq.push_front(0); // Add element at the front
8  dq.push_back(4);  // Add element at the back
9  
10  for (const auto& elem : dq) {
11      std::cout << elem << " ";
12  }
13  
14  return 0;
15}

0 1 2 3 4

Removing Elements

You can remove elements from a deque using pop_front() and pop_back() methods. These methods allow you to delete elements from the front and back of the deque, respectively.

1#include <iostream>
2#include <deque>
3 
4int main() {
5  std::deque<int> dq = {0, 1, 2, 3, 4};
6  
7  dq.pop_front(); // Remove element from the front
8  dq.pop_back();  // Remove element from the back
9  
10  for (const auto& elem : dq) {
11      std::cout << elem << " ";
12  }
13  
14  return 0;
15}

1 2 3

Random Access

One of the advantages of deques is that they support random access, similar to vectors. You can access elements by their index using the [] operator or the at() method.

1#include <iostream>
2#include <deque>
3 
4int main() {
5  std::deque<int> dq = {10, 20, 30, 40, 50};
6  
7  // Accessing elements using the [] operator
8  std::cout << "Element at index 2: " << dq[2] << std::endl;
9  
10  // Accessing elements using the at() method
11  try {
12      std::cout << "Element at index 4: " << dq.at(4) << std::endl;
13  } catch (const std::out_of_range& e) {
14      std::cerr << "Out of range error: " << e.what() << std::endl;
15  }
16  
17  return 0;
18}

Element at index 2: 30
Element at index 4: 50

Deque vs Vector

Practical Example

Let's create a practical example that demonstrates the use of a deque. We'll implement a simple application that simulates a queue with frequent insertions and deletions at both ends.

1#include <iostream>
2#include <deque>
3 
4int main() {
5  std::deque<int> dq;
6  
7  // Adding elements to the deque
8  dq.push_back(1);
9  dq.push_back(2);
10  dq.push_front(0);
11  dq.push_front(-1);
12  
13  std::cout << "Deque after initial insertions: ";
14  for (const auto& elem : dq) {
15      std::cout << elem << " ";
16  }
17  std::cout << std::endl;
18  
19  // Removing elements from the deque
20  dq.pop_back();
21  dq.pop_front();
22  
23  std::cout << "Deque after removals: ";
24  for (const auto& elem : dq) {
25      std::cout << elem << " ";
26  }
27  std::cout << std::endl;
28  
29  return 0;
30}

Deque after initial insertions: -1 0 1 2 
Deque after removals: 0 1

Summary

• Deques are sequence containers that support fast insertions and deletions at both ends.
• They use a series of chunks or blocks, allowing for efficient access to elements from both ends.
• Deques support random access, similar to vectors.
• Use deques when you need frequent modifications at both ends; otherwise, consider using vectors for better performance.

What's Next?

In the next tutorial, we will explore the stack container in C++ STL. A stack is a LIFO (Last In, First Out) data structure, which is useful for scenarios where you need to process items in reverse order. Stay tuned!