Skip to content

Latest commit

 

History

History
52 lines (36 loc) · 2.98 KB

std_deque.md

File metadata and controls

52 lines (36 loc) · 2.98 KB

The std::deque (Double-Ended Queue) is a container provided by the C++ Standard Library that allows fast insertion and deletion at both its beginning and its end. Unlike std::vector, which provides fast insertion and deletion at its end but is slow at the beginning, std::deque maintains a balanced performance for these operations at both ends.

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements.

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location. On the other hand, deques typically have large minimal memory cost

Basic Usage

Here's a simple example to demonstrate the basic functionality of std::deque.

#include <iostream>
#include <deque>

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

    // Add elements to the deque
    d.push_back(1);  // [1]
    d.push_front(0); // [0, 1]
    d.push_back(2);  // [0, 1, 2]

    // Access elements
    std::cout << "Front: " << d.front() << std::endl; // Output: Front: 0
    std::cout << "Back: " << d.back() << std::endl;   // Output: Back: 2

    // Remove elements from the deque
    d.pop_front(); // [1, 2]
    d.pop_back();  // [1]

    // Size of the deque
    std::cout << "Size: " << d.size() << std::endl; // Output: Size: 1

    return 0;
}

Characteristics

  • Random Access: Provides fast random access with the operator[] or the at() member function.

  • Dynamic Size: Like vectors and lists, deques can grow and shrink dynamically at runtime.

  • Element Order: Elements have their relative order maintained, meaning that an element that was pushed before another will come out before that other element if accessed sequentially.

Memory

Unlike std::vector, which uses a single array, std::deque generally uses multiple fixed-size arrays. The index-to-element mapping is performed internally, making random access still relatively fast, but it might incur a small overhead compared to std::vector.

When to Use std::deque

  1. When you need fast insertions/deletions at both ends.
  2. When random access is required but the overhead of shifting elements in a std::vector is not acceptable.
  3. When you don't need the elements to be stored in contiguous memory.