Двусторонняя очередь (deque, double-ended queue) — это контейнерная структура данных, которая позволяет эффективно добавлять и удалять элементы как с начала, так и с конца.
Её основные характеристики:
push_front, pop_front, push_back, pop_back выполняются в среднем за время O(1).std::vector, элементы std::deque не обязательно хранятся в едином непрерывном блоке памяти. Он обычно реализован как последовательность блоков фиксированного размера.Сравнение с std::vector и std::list:
| Характеристика | std::vector | std::deque | std::list |
|---|---|---|---|
| Доступ по индексу | O(1) | O(1) | O(n) |
| Вставка/удаление в начале | O(n) | O(1) |
Двусторонняя очередь (deque, double-ended queue) — это контейнерная структура данных, которая позволяет эффективно добавлять и удалять элементы как с начала, так и с конца.
Её основные характеристики:
push_front, pop_front, push_back, pop_back выполняются в среднем за время O(1).std::vector, элементы std::deque не обязательно хранятся в едином непрерывном блоке памяти. Он обычно реализован как последовательность блоков фиксированного размера.Сравнение с std::vector и std::list:
| Характеристика | std::vector | std::deque | std::list |
|---|---|---|---|
| Доступ по индексу | O(1) | O(1) | O(n) |
| Вставка/удаление в начале | O(n) | O(1) |
Зарегистрируйтесь или войдите, чтобы получить доступ к полным ответам на все вопросы из банка вопросов.