C++ deques

---

Introduction

In C++, a deque (short for "double-ended queue") is a container in the C++ Standard Library that allows for efficient insertion and removal of elements from both ends. It is defined in the <deque> header and is part of the sequence containers in C++. Unlike a regular queue (std::queue), which allows insertion and removal only from the front and back, a deque allows inserting and deleting elements from both the front and the back efficiently.

Internally, std::deque is implemented as a dynamic array of blocks, which allows elements to be stored in a non-contiguous manner while providing constant-time access to both ends of the container.

---

Key Features of std::deque

• Double-Ended Access: You can add or remove elements from both ends of the deque efficiently, which makes it more versatile than other containers like vectors or lists.
• Efficient Insertions and Deletions: Insertions and deletions at the front and back are performed in constant time (O(1)), but insertions or deletions at the middle take linear time (O(n)).
• Random Access: Deques allow random access to elements, just like vectors, but also provide the advantage of faster insertions and deletions at both ends.
• Dynamic Sizing: Like vectors, deques can grow and shrink dynamically as elements are added or removed.
• Underlying Implementation: Internally, std::deque is implemented using blocks of arrays, unlike vectors which store elements contiguously.

---

Syntax

To declare a deque:

std::deque<T> deque_name;

Where:

• T: Type of the elements (e.g., int, std::string).

You can also initialize a deque with specific elements:

std::deque<T> deque_name = {element1, element2, element3};

---

Declaring and Initializing a Deque

Example 1: Basic Deque Declaration and Initialization

#include <iostream>
#include <deque>

int main() {
    // Declare and initialize a deque of integers
    std::deque<int> dq = {1, 2, 3, 4, 5};

    // Displaying elements using a range-based for loop
    for (int i : dq) {
        std::cout << i << " ";
    }

    return 0;
}

Explanation:

• The deque dq is initialized with the values {1, 2, 3, 4, 5}.
• A range-based for loop is used to iterate through the deque and print the elements.

---

Important Member Functions of std::deque

std::deque provides several member functions for performing operations like insertion, deletion, and access.

1. push_back() and push_front()

• Adds an element to the back (push_back()) or the front (push_front()) of the deque.

dq.push_back(6);  // Adds 6 to the back of the deque
dq.push_front(0); // Adds 0 to the front of the deque

2. pop_back() and pop_front()

• Removes an element from the back (pop_back()) or the front (pop_front()) of the deque.

dq.pop_back();    // Removes the element at the back
dq.pop_front();   // Removes the element at the front

3. front() and back()

• Accesses the front (front()) and back (back()) elements of the deque.

std::cout << "Front element: " << dq.front() << std::endl;  // Access front element
std::cout << "Back element: " << dq.back() << std::endl;    // Access back element

4. size()

• Returns the number of elements in the deque.

std::cout << "Size of deque: " << dq.size() << std::endl;

5. empty()

• Checks whether the deque is empty.

if (dq.empty()) {
    std::cout << "Deque is empty!" << std::endl;
} else {
    std::cout << "Deque is not empty!" << std::endl;
}

6. insert()

• Inserts an element at a specific position in the deque.

std::deque<int>::iterator it = dq.begin();
dq.insert(it + 2, 99);  // Inserts 99 at the 3rd position

7. erase()

• Removes one or more elements from the deque.

dq.erase(it);  // Removes the element at position `it`

8. clear()

• Removes all elements from the deque.

dq.clear();  // Clears the entire deque

9. resize()

• Resizes the deque to a specified size, adding default elements if necessary.

dq.resize(10);  // Resizes the deque to hold 10 elements

---

Iterating Through a Deque

You can iterate through a std::deque using various methods, such as traditional loops, range-based for loops, or iterators.

Example 1: Using a Traditional for Loop with Iterators

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {10, 20, 30, 40};

    // Traditional for loop using an iterator
    for (std::deque<int>::iterator it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Example 2: Using a Range-Based for Loop

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {1, 2, 3, 4, 5};

    // Range-based for loop
    for (int i : dq) {
        std::cout << i << " ";
    }

    return 0;
}

---

Advantages of std::deque Over Other Containers

1. Double-Ended Access: The ability to insert or remove elements from both ends efficiently is a significant advantage of deques over vectors or lists.
2. Efficient Operations: Insertions and deletions at both ends occur in constant time, while random access to elements in the middle is still efficient.
3. Dynamic Size: Deques automatically resize themselves when elements are added or removed, just like vectors, but they offer more flexibility with double-ended operations.
4. Random Access: Deques allow direct access to any element, unlike lists.

---

When to Use std::deque

Use std::deque when:

• You need efficient insertions or deletions at both ends of a container.
• You require random access to elements, like with a vector, but also need the flexibility of a double-ended queue.
• The order of insertion and deletion needs to be managed from both ends (e.g., for sliding windows, buffers, or queues).

---

Real-World Applications of Deques

1. Sliding Window Algorithms: Deques are used in algorithms that require keeping track of elements in a sliding window, such as finding the maximum or minimum in a subarray of a fixed size.
2. Double-Ended Queues: Deques can be used for implementing advanced queues where elements can be added or removed from both ends, such as in job scheduling or round-robin tasks.
3. Buffers: Deques are commonly used in systems where data needs to be read from both ends (e.g., in circular buffers).

---

---