C++ STL Deque Explained — How It Works, When to Use It, and Pitfalls to Avoid

#include <iostream>
#include <deque>
#include <string>

int main() {
    // Simulate a customer service queue where agents join
    // the front (priority escalation) or the back (normal flow)
    std::deque<std::string> serviceQueue;

    // Normal customers join at the back — O(1)
    serviceQueue.push_back("Alice");
    serviceQueue.push_back("Bob");
    serviceQueue.push_back("Charlie");

    std::cout << "Queue after normal arrivals:\n";
    for (const auto& customer : serviceQueue) {
        std::cout << "  " << customer << "\n";
    }

    // A VIP customer gets priority — pushed to the FRONT — O(1)
    // With a vector, this would shift Alice, Bob, Charlie rightward
    // With deque, it simply fills a slot in the leading chunk
    serviceQueue.push_front("VIP_Diana");

    std::cout << "\nQueue after VIP joins at front:\n";
    for (const auto& customer : serviceQueue) {
        std::cout << "  " << customer << "\n";
    }

    // Random access still works — O(1) just like vector
    std::cout << "\nSecond customer in line: " << serviceQueue[1] << "\n";
    std::cout << "Third customer (at()): " << serviceQueue.at(2) << "\n";

    // Serve the front customer — O(1)
    std::cout << "\nNow serving: " << serviceQueue.front() << "\n";
    serviceQueue.pop_front();

    std::cout << "Queue after serving front:\n";
    for (const auto& customer : serviceQueue) {
        std::cout << "  " << customer << "\n";
    }

    // Check size and access back
    std::cout << "\nQueue size: " << serviceQueue.size() << "\n";
    std::cout << "Last in line: " << serviceQueue.back() << "\n";

    return 0;
}

#include <iostream>
#include <deque>
#include <vector>
#include <string>

// Classic sliding window maximum — finds the largest value
// in every window of size 'windowSize' across the dataset.
// The deque stores INDICES (not values) of useful candidates.
// Elements at the front are always the current window's maximum.
void printSlidingWindowMaximums(
    const std::vector<int>& sensorReadings,
    int windowSize)
{
    std::deque<int> candidateIndices; // stores indices into sensorReadings
    std::cout << "Sensor readings: ";
    for (int val : sensorReadings) std::cout << val << " ";
    std::cout << "\nWindow size: " << windowSize << "\n";
    std::cout << "Maximum per window: ";

    for (int i = 0; i < static_cast<int>(sensorReadings.size()); ++i) {

        // Step 1: Evict indices that are now outside the current window.
        // We only evict from the FRONT — O(1) pop_front
        while (!candidateIndices.empty() &&
               candidateIndices.front() <= i - windowSize) {
            candidateIndices.pop_front();
        }

        // Step 2: Remove indices from the BACK whose values are smaller
        // than the current reading — they can never be a future maximum
        // because the current element is newer AND larger.
        while (!candidateIndices.empty() &&
               sensorReadings[candidateIndices.back()] < sensorReadings[i]) {
            candidateIndices.pop_back(); // O(1) pop_back
        }

        // Step 3: Add current index to the back — O(1) push_back
        candidateIndices.push_back(i);

        // Step 4: Once we have a full window, the front is the max index
        if (i >= windowSize - 1) {
            std::cout << sensorReadings[candidateIndices.front()];
            if (i < static_cast<int>(sensorReadings.size()) - 1)
                std::cout << ", ";
        }
    }
    std::cout << "\n";
}

// Simple round-robin task dispatcher using deque
void demonstrateTaskDispatcher() {
    std::deque<std::string> taskQueue;

    // New tasks arrive at the back
    taskQueue.push_back("render_frame");
    taskQueue.push_back("process_input");
    taskQueue.push_back("play_audio");

    // Urgent task gets bumped to the front
    taskQueue.push_front("handle_crash_report");

    std::cout << "\nDispatching tasks in order:\n";
    int tickNumber = 1;
    while (!taskQueue.empty()) {
        std::cout << "  Tick " << tickNumber++ 
                  << ": executing [" << taskQueue.front() << "]\n";
        taskQueue.pop_front();
    }
}

int main() {
    std::vector<int> temperatureLog = {3, 1, 2, 5, 4, 8, 6, 7};
    printSlidingWindowMaximums(temperatureLog, 3);

    demonstrateTaskDispatcher();
    return 0;
}

#include <iostream>
#include <deque>
#include <vector>
#include <list>
#include <chrono>
#include <string>

// Measures how long it takes to insert N elements at the FRONT
// of each container type. This highlights deque's core advantage.
template<typename DurationType>
std::string formatMicroseconds(DurationType duration) {
    auto us = std::chrono::duration_cast<std::chrono::microseconds>(duration).count();
    return std::to_string(us) + " microseconds";
}

void benchmarkFrontInsertions(int elementCount) {
    std::cout << "Benchmarking " << elementCount 
              << " front insertions:\n";

    // --- deque: uses push_front, O(1) amortized ---
    {
        std::deque<int> dataDeque;
        auto startTime = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < elementCount; ++i) {
            dataDeque.push_front(i); // O(1) — no shifting
        }
        auto endTime = std::chrono::high_resolution_clock::now();
        std::cout << "  deque push_front:  "
                  << formatMicroseconds(endTime - startTime) << "\n";
    }

    // --- vector: must use insert at begin(), O(n) each time ---
    {
        std::vector<int> dataVector;
        dataVector.reserve(elementCount); // give it a fair start
        auto startTime = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < elementCount; ++i) {
            // This shifts ALL existing elements right on every call
            dataVector.insert(dataVector.begin(), i);
        }
        auto endTime = std::chrono::high_resolution_clock::now();
        std::cout << "  vector insert(begin): "
                  << formatMicroseconds(endTime - startTime) << "\n";
    }

    // --- list: O(1) push_front but no random access ---
    {
        std::list<int> dataList;
        auto startTime = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < elementCount; ++i) {
            dataList.push_front(i); // O(1) but heap allocation per node
        }
        auto endTime = std::chrono::high_resolution_clock::now();
        std::cout << "  list push_front:   "
                  << formatMicroseconds(endTime - startTime) << "\n";
    }

    std::cout << "\n";
}

int main() {
    benchmarkFrontInsertions(10000);
    benchmarkFrontInsertions(50000);
    return 0;
}

#include <iostream>
#include <deque>
#include <string>
#include <algorithm>

// Demonstrates safe vs unsafe iterator usage with deque
void safeRemoveCompletedTasks(std::deque<std::string>& workQueue) {
    std::cout << "Before cleanup: ";
    for (const auto& task : workQueue) std::cout << "[" << task << "] ";
    std::cout << "\n";

    // UNSAFE PATTERN — DO NOT DO THIS:
    // Storing an iterator and then calling push_back or push_front
    // while iterating can invalidate the iterator silently.
    //
    // auto it = workQueue.begin();
    // workQueue.push_back("new_task");  // may invalidate 'it'!
    // ++it;  // undefined behavior

    // SAFE PATTERN 1: Use erase() which returns the next valid iterator.
    // Remove all tasks marked as "DONE_*"
    auto it = workQueue.begin();
    while (it != workQueue.end()) {
        if (it->substr(0, 5) == "DONE_") {
            // erase() returns iterator to the element AFTER the erased one
            // This is the correct way to erase during iteration
            it = workQueue.erase(it);
        } else {
            ++it;
        }
    }

    std::cout << "After cleanup:  ";
    for (const auto& task : workQueue) std::cout << "[" << task << "] ";
    std::cout << "\n";
}

void safeRemoveWithRemoveEraseIdiom(std::deque<std::string>& workQueue) {
    // SAFE PATTERN 2: The remove-erase idiom — cleaner for simple predicates
    // std::remove_if moves matching elements to the end, returns new logical end
    // deque::erase then physically removes them
    workQueue.erase(
        std::remove_if(workQueue.begin(), workQueue.end(),
            [](const std::string& task) {
                return task.substr(0, 5) == "DONE_";
            }),
        workQueue.end()
    );
}

int main() {
    std::deque<std::string> taskQueue = {
        "render_ui",
        "DONE_load_config",
        "process_events",
        "DONE_init_audio",
        "update_physics"
    };

    safeRemoveCompletedTasks(taskQueue);

    // Reset for second demo
    std::deque<std::string> taskQueue2 = {
        "DONE_prefetch_assets",
        "stream_video",
        "DONE_run_diagnostics",
        "upload_telemetry"
    };

    std::cout << "\nRemove-erase idiom demo:\n";
    std::cout << "Before: ";
    for (const auto& t : taskQueue2) std::cout << "[" << t << "] ";
    std::cout << "\n";

    safeRemoveWithRemoveEraseIdiom(taskQueue2);

    std::cout << "After:  ";
    for (const auto& t : taskQueue2) std::cout << "[" << t << "] ";
    std::cout << "\n";

    return 0;
}