C++ Deque

In C++, a deque (double-ended queue) is a sequence container that allows fast insertions and deletions at both ends. It is part of the Standard Template Library (STL) and provides a more flexible alternative to vectors when you need efficient operations at both the front and back of the container.

Key Features of `std::deque`

Fast Access: Provides constant time access to elements at both the beginning and end.
Dynamic Size: Can grow and shrink dynamically as elements are added or removed.
Bidirectional Operations: Supports efficient insertion and deletion at both the front and the back.
Not Contiguous: Unlike vectors, deques are not required to store elements in contiguous memory locations. They typically use multiple chunks of memory.

Basic Syntax

To use std::deque, include the header and use the std::deque template class:

cpp
#include

Basic Operations

1. Declaration

cpp
std::deque<int> d;  // Creates an empty deque of integers

2. Initialization

cpp
std::deque<int> d1 = {1, 2, 3, 4}; // Initialize with values
std::deque<int> d2(5, 10); // Initialize with 5 elements, each with value 10

3. Adding Elements

To the Front: push_front()
To the Back: push_back()

cpp
d.push_front(1); // Add 1 to the front
d.push_back(2);  // Add 2 to the back

4. Removing Elements

From the Front: pop_front()
From the Back: pop_back()

cpp
d.pop_front(); // Remove the element from the front
d.pop_back();  // Remove the element from the back

5. Accessing Elements

Using [] Operator: Provides direct access to elements.
Using at() Method: Provides access with bounds checking.
Using front() and back(): Access the first and last elements respectively.

cpp
int front = d.front(); // Access the first element
int back = d.back();   // Access the last element

int value = d[1];      // Access the element at index 1
int safeValue = d.at(1); // Access the element at index 1 with bounds checking

6. Iteration

cpp
for (std::deque<int>::iterator it = d.begin(); it != d.end(); ++it) {
    std::cout << *it << " ";
}

// Using range-based for loop
for (const auto& elem : d) {
    std::cout << elem << " ";
}

7. Size and Capacity

cpp
std::size_t size = d.size(); // Get the number of elements
bool empty = d.empty();      // Check if the deque is empty

8. Clearing

cpp
d.clear(); // Remove all elements from the deque

Example Code

Here’s a complete example demonstrating some of these operations:

cpp
#include 
#include 

int main() {
    std::deque<int> d;

    // Adding elements
    d.push_back(1);
    d.push_back(2);
    d.push_front(0);
    d.push_front(-1);

    // Accessing elements
    std::cout << "Front element: " << d.front() << std::endl;
    std::cout << "Back element: " << d.back() << std::endl;

    // Iterating
    std::cout << "Deque elements: ";
    for (const auto& elem : d) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Removing elements
    d.pop_back();
    d.pop_front();

    std::cout << "Deque after pop operations: ";
    for (const auto& elem : d) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Key Points

Insertion and Deletion: std::deque allows efficient insertion and deletion at both ends.
Access: Provides fast random access to elements.
Memory: Unlike std::vector, std::deque does not store elements contiguously, which can affect performance and memory usage.

std::deque is suitable for scenarios where you need efficient operations at both ends of the sequence and can tolerate non-contiguous storage.

techmore.in