std::deque последовательный контейнер двусторонней очереди

- deque расшифровывается как double-ended queue (двусторонняя очередь или дек) и позволяет эффективно добавлять или убавлять элементы в начале и конце очереди (в векторе только в конце). Подключается через #include <deque>;

- К элементам deque можно обращаться по индексу.

- Обращение к элементам очереди по индексу требует 2 разыменования указателя (в std::vector требуется только одно разыменование - что быстрее)

- deque располагает свои элементы кусочно-непрерывно (в отличие от вектора, где все элементы идут непрерывно), в непрерывных блоках (страницах) одинакового размера. Например, для std::deque они могут занимать 4 килобайта.

- Вставка и удаление элементов с любого конца deque не приводит к инвалидации ссылок или указателей на элементы (но не итераторов).

- Сложность случайного доступа - постоянная  O(1)

- Сложность вставки или удаления элементов в начале или конце очереди - постоянная O(1)

- Сложность вставки или удаления элементов - линейная O(n)

МетодОписаниеПримерСложность
[] Доступ к элементу по индексу. cout << deq.[20]; O(1)
assign(size_t index) Доступ к элементу по индексу. Выбрасывает исключение при выходе за границы. cout << deq.at(20); O(1)
at(size_t index) Доступ к элементу по индексу. Выбрасывает исключение при выходе за границы. cout << deq.at(20); O(1)
back() Доступ к последнему элементу. cout << deq.back(); O(1)
begin() Возвращает итератор на первый элемент. auto i = deq.begin(); O(1)
clear() Удаляет все элементы дека. deq.clear(); O(n)
deque Конструктор без аргументов. Создает новый пустой дек. deque<int> deq; O(1)
deque(int size) Конструктор. Создает дек с заданным количеством элементов deque<int> deq(10); O(n)
deque(int size, int value) Конструктор. Создает дек с количеством элементов size и значением value deque<int> deq(10, 3); O(n)
deque({initializer_list init}) Конструктор с инициализацией deque<int> deq({0, 1, 4, 9, 16}); O(n)
deque(const deque v) Конструктор копирования. Создает дек из другого контейнера. deque<int> deq1(deq);
deque<int> deq(v); 		O(n)
deque(iterator it1, iterator it2) Конструктор. Создает дек из диапазона итераторов другого контейнера. deque deq2(deq.begin(), deq.end());
deque deq2(v.begin(), v.end()); 		O(n)
empty() Возвращает пустой ли дек. if(!deq.empty); O(1)
end() Возвращает итератор на место после последнего элемента. auto i = deq.end(); O(1)
erase(iterator pos) Удаляет элемент(ы) из заданной позиции. deq.erase(deq.begin() + 2);
deq.erase(deq.begin() + 2, deq.end()); 		O(n)
front() Доступ к первому элементу. cout << deq.front(); O(1)
insert(iterator pos, ) Вставляет элемент(ы) в заданную позицию. deq.insert(deq.begin() + 2, 10);
deq.insert(deq.begin() + 2, {3, 4, 5});
deq.insert(deq.begin(), deq.end() - 3, deq.end()); 		O(n)
max_size() Возвращает максимально возможный размер дека. size_t msize = deq.max_size(); //2305843009213693951 O(1)
pop_back() Удаляет элемент с конца дека. deq.pop_back(); O(1)
push_back(const T& value) Вставляет элемент со значением value в конец дека. deq.push_back(10); O(1)
push_front(const T& value) Вставляет элемент со значением value в начало дека. deq.push_front(20); O(1)
rbegin() Возвращает реверсивный итератор на конец дека. auto i = deq.rbegin(); O(1)
rend() Возвращает реверсивный итератор на начало дека. auto i = deq.rend(); O(1)
resize(size_t new_size) Изменяет количество элементов дека до new_size deq.resize(1000); O(n)
size() Возвращает размер дека. size_t size = deq.size(); O(1)
swap(deque& v2) Обменивает содержимое деков deq.swap(deq1); O(1) 

#include <iostream> // cout
#include <deque>    // degue

int main() {
    std::deque<std::string> deq({"my"});    // Создали дек
    deq.push_back("Victor!");               // Добавили элемент в конец дека
    deq.push_front("Hi");                   // Добавили элемент в начало дека
    deq.insert(deq.end() - 1, "friend");    // Добавили элемент в предпоследнюю позицию дека
    for(auto& i : deq){                     // Перебираем элементы дека
        std::cout << i << " ";              //Hi my friend Victor!
    }
}

Двумерная двусторонняя очередь std::deque


#include <iostream> // cout
#include <deque>    // deque
#include <vector>   // vector
int main(){
    //std::deque<std::deque<int>> deq1(2, std::deque<int>(3));    // Создаем двумерный массив размером 2х3
    std::deque<std::deque<int>> deq{ // Создаем двумерный массив с инициализацией
    {0, 1},
    {2, 3},
    {4, 5},
    {6, 7},
    };
    for(size_t x = 0; x < deq.size(); x++){                // Перебор x
        for(size_t y = 0; y < deq[x].size(); y++){         // Перебор y
            std::cout << deq[x][y] << " ";     // Выводим значения элементов контейнера
        }
    std::cout << '\n';
    }
}
/* Вывод программы
0 1
2 3
4 5
6 7
*/

Сортировка std::deque

Для сортировки контейнеров используется функция std::sort(), подключаемая через #include <algorithm> 

#include <iostream>  // cout
#include <deque>     // deque
#include <algorithm> // sort()
int main() {
    std::deque<int> data{3, 1, 4, 1, 5, 9, 2, 6};
    std::sort(data.begin(), data.end()); // Сортировка очереди по возростанию
    for(int n : data){ // Перебираем элементы контейнера
        std::cout << n << ' '; //1 1 2 3 4 5 6 9
    }
    std::cout << "\n";

    std::sort(data.rbegin(), data.rend()); // Сортировка очереди по убыванию
    //std::sort(data.begin(), data.end(), greater<int>()); // Аналогично сортировка очереди по убыванию
    for(auto n : data){ // Перебираем элементы контейнера
        std::cout << n << ' '; //9 6 5 4 3 2 1 1
    }
    std::cout << "\n";
}

Для сортировки контейнеров с типами данных для которых не определен оператор < потребуется реализовать этот функционал. 


#include <iostream>  // cout
#include <deque>     // deque
#include <algorithm> // sort()

struct Point{   // Структура точки
    int x;  // Координата x
    int y;  // Координата y
    int r;  // Радиус
};

int main() {
    std::deque<Point> points{{2, 0, 2}, {2, 3, 4}, {0, 1, 1}, {3, 4, 5}} ; // Завели очередь структур точек

    std::sort(points.begin(), points.end(), [](const Point &x, const Point &y){ // Сортируем массив с лямбдой
        return x.r < y.r;   // Определяем критерий сортировки
    });

    for(auto i : points){ // Перебираем элементы контейнера
        std::cout << i.x << " " << i.y << " " << i.r << "\n";
    }
}

/* Вывод программы - отсортированные в очереди точки в соответствии с радиусом
0 1 1
2 0 2
2 3 4
3 4 5
*/
2023-12-15



Понравилась страница?
Добавить в закладки
Или поделиться!

Связанные темы

array - статический массив (после создания размер не изменяется). Быстрее вектора.
Выбор контейнера из стандартной библиотеки С++.
deque - двусторонняя очередь (дек). Эффективное вставка-удаление по концам очереди.
forward_list - односвязный список с эффективной вставкой/удалением в начало списка.
list - двусвязный список с эффективной вставкой/удалением в любом месте списка.
map - словарь сортированных уникальных пар ключ-значение.
multimap - словарь сортированных неуникальных пар ключ-значение.
multiset - множество сортированных неуникальных элементов.
priority_queue - очередь с приоритетом (с сортировкой значений).
queue - очередь FIFO first in, first out "первый пришел - первый ушел".
set - множество сортированных уникальных элементов.
stack - стек LIFO last in, first out "последний пришел - первый ушел".
unordered_map - словарь несортированных уникальных пар ключ-значение.
unordered_multimap - словарь несортированных неуникальных пар ключ-значение.
unordered_multiset - множество несортированных неуникальных значений.
unordered_set - множество несортированных уникальных значений.
vector - вектор (массив) значений с изменяемым размером.