What is a deque container in C++?

std::deque (double-ended queue) is a sequential container that allows efficient addition and removal of elements at both the beginning and the end. It is implemented as a sequence of memory blocks, providing quick access to any element by index (similar to std::vector), but without the need to move existing elements when inserting/removing at the beginning.

Main characteristics:

• Random access: Elements are accessible by index with O(1) complexity.
• Insertion/removal at the end: Performed with O(1) complexity.
• Insertion/removal at the beginning: Performed with O(1) complexity.
• Insertion/removal in the middle: Performed with O(n) complexity, where n is the number of elements between the insertion/removal point and the nearest end.
• Contiguous storage: Elements are stored in several contiguous memory blocks, but not necessarily in one large block like std::vector.
• Iterators: std::deque iterators are not guaranteed to remain valid after insertions/removals, except at the ends (after push_back/pop_back and push_front/pop_front), unless the inserted/removed element caused reallocation of all blocks.

Used when frequent insertion or removal of elements at both ends is required, as well as arbitrary access.

Example usage:

#include <deque>
#include <iostream>

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

    dq.push_back(10); // Add to the end
    dq.push_front(5);  // Add to the beginning
    dq.push_back(15); // Add to the end

    // Contents: 5, 10, 15

    std::cout << "Element at index 1: " << dq[1] << std::endl; // Access by index

    dq.pop_front(); // Remove from the beginning
    dq.pop_back();  // Remove from the end

    // Contents: 10

    std::cout << "Remaining element: " << dq.front() << std::endl; // Access first element

    return 0;
}

Comparison with std::vector:

Feature	std::vector	std::deque
Insertion/removal at end	Amortized O(1)	O(1)
Insertion/removal at beginning	O(n)	O(1)
Insertion/removal in middle	O(n)	O(n)
Arbitrary access	O(1)	O(1)
Contiguous storage	Guaranteed	Not guaranteed (memory blocks)
Iterator validity	Invalidated on reallocation/insertion/removal except at the end	Less guarantees, depends on operation