What is deque in C++: Explanation and Example

In C++, a deque (double-ended queue) is a sequence container that allows fast insertion and deletion at both the front and back ends. It combines the features of vectors and lists, providing efficient random access and flexible resizing from both ends.

How It Works

Think of a deque as a flexible line of people where you can add or remove people quickly from either the front or the back. Unlike a simple queue where you can only add at the back and remove from the front, a deque lets you do both at either end.

Internally, a deque manages multiple chunks of memory instead of one continuous block like a vector. This design allows it to grow or shrink efficiently at both ends without moving all elements around. You can also access elements quickly by their position, similar to an array.

Example

This example shows how to create a deque, add elements to both ends, and access them.

cpp

#include <iostream>
#include <deque>

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

    d.push_back(10);   // Add 10 at the back
    d.push_front(20);  // Add 20 at the front
    d.push_back(30);   // Add 30 at the back

    std::cout << "Deque elements: ";
    for (int num : d) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    std::cout << "Front element: " << d.front() << "\n";
    std::cout << "Back element: " << d.back() << "\n";

    return 0;
}

Output

Deque elements: 20 10 30 
Front element: 20
Back element: 30

When to Use

Use a deque when you need a container that supports fast insertion and deletion at both the front and back ends, unlike a vector which is slow at the front. It is ideal for situations like implementing queues, double-ended queues, or buffers where you add and remove items from both ends.

For example, a deque is useful in real-time systems where you process tasks in order but sometimes need to add urgent tasks at the front. It also works well when you want random access to elements but still need flexible resizing.

Key Points

• Double-ended: Supports fast insertions/removals at both front and back.
• Random access: Allows accessing elements by index quickly.
• Memory: Uses multiple memory blocks internally for flexibility.
• Use cases: Good for queues, buffers, and situations needing flexible ends.

Key Takeaways

A deque allows fast insertion and deletion at both front and back ends.

It provides quick random access to elements by index.

Deque uses multiple memory blocks internally for efficient resizing.

Use deque when you need flexible ends and fast access, unlike vector or list.

Ideal for queues, double-ended queues, and buffers with dynamic ends.