Daily bit(e) C++. std::deque

Daily bit(e) C++ #208, не-непрерывный контейнер очереди с произвольным доступом: std::deque.

std::deque – не-непрерывный контейнер, который моделирует двустороннюю очередь, но при этом обеспечивает произвольный доступ, хотя и за счет одной дополнительной косвенности.

Элементы можно добавлять и удалять с каждого конца очереди с временной сложностью O(1) без инвалидации существующих итераторов (за исключением стертых элементов).

#include <queue>
#include <iostream>

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

    // Вдобавок к push_back и pop_back
    // также получаем то же самое для фронта.
    data.push_back(1);
    // data == {1}
    data.push_front(2);
    // data == {2, 1}
    data.push_back(3);
    // data == {2, 1, 3}

    for (auto v : data)
        std::cout << v << " ";
    std::cout << "\n";

    data.pop_front();
    data.pop_front();
    // data == {3}

    for (auto v : data)
        std::cout << v << " ";
    std::cout << "\n";

    // std::deque также предлагает тот же
    // интерфейс, что и std::vector.
    data.resize(7, 42);
    // data == {3, 42, 42, 42, 42, 42, 42}

    for (auto v : data)
        std::cout << v << " ";
    std::cout << "\n";

    // Линейные операции:
    // вставка/удаление в середине обеспечивают сложность O(n)
    data.insert(data.begin()+1, 7);
    // data == {3, 7, 42, 42, 42, 42, 42, 42}
    data.erase(data.begin()+2);
    // data == {3, 7, 42, 42, 42, 42, 42}

    for (auto v : data)
        std::cout << v << " ";
    std::cout << "\n";
}

Открыть пример на Compiler Explorer.

Теги