Основы deque
На C++ двусторонняя очередь deque — это контейнер последовательности для быстрой вставки и удаления элементов в начале и в конце.
В отличие от векторов vector, двусторонними очередями deque не гарантируется сохранение всех элементов в смежных ячейках памяти.
Начнем с простого примера deque:
#include <deque>
#include <iostream>
int main() {
std::deque<int> d = {1, 2, 3};
d.push_front(0);
d.push_back(4);
for (int num : d) {
std::cout << num << " ";
}
// Вывод: 0 1 2 3 4
return 0;
}
Этим кодом демонстрируются основные операции. Но каков принцип работы deque?
Внутренняя структура Deque
Deque обычно реализуется в виде набора отдельно выделяемых массивов фиксированного размера с дополнительным учетом распределения памяти для их отслеживания. Эту структуру часто называют map, но это не контейнер std::map.
Вот упрощенное представление:
[ ptr ][ ptr ][ ptr ][ ptr ][ ptr ] // Массив указателей «map»
| | | | |
v v v v v
[block][block][block][block][block] // Блоки фактических данных
Каждый блок — это непрерывный кусок памяти, в котором хранятся элементы. Map — массив указателей на эти блоки.
Реализация базовой deque
Создадим упрощенную версию deque:
template <typename T>
class SimpleDeque {
private:
static const size_t BLOCK_SIZE = 8;
T** map;
size_t map_size;
size_t start;
size_t finish;
size_t size;
size_t front_block;
size_t back_block;
public:
SimpleDeque() : map(nullptr), map_size(0), start(0), finish(0), size(0), front_block(0), back_block(0) {
map_size = 8;
map = new T*[map_size];
for (size_t i = 0; i < map_size; ++i) {
map[i] = nullptr;
}
map[0] = new T[BLOCK_SIZE];
}
void push_back(const T& value) {
if (size == 0 || finish == BLOCK_SIZE) {
if (back_block == map_size - 1) {
// Меняем размер «map»
size_t new_map_size = map_size * 2;
T** new_map = new T*[new_map_size];
for (size_t i = 0; i < map_size; ++i) {
new_map[i] = map[i];
}
for (size_t i = map_size; i < new_map_size; ++i) {
new_map[i] = nullptr;
}
delete[] map;
map = new_map;
map_size = new_map_size;
}
if (map[back_block + 1] == nullptr) {
map[back_block + 1] = new T[BLOCK_SIZE];
}
++back_block;
finish = 0;
}
map[back_block][finish] = value;
++finish;
++size;
}
T& operator[](size_t n) {
size_t block = (start + n) / BLOCK_SIZE;
size_t offset = (start + n) % BLOCK_SIZE;
return map[front_block + block][offset];
}
size_t get_size() const {
return size;
}
~SimpleDeque() {
for (size_t i = 0; i < map_size; ++i) {
delete[] map[i];
}
delete[] map;
}
};
В этой неполной реализации показаны базовая структура и операция push_back — для понимания основ достаточно.
Управление памятью в deque
Одно из ключевых преимуществ deque — эффективное управление памятью. В отличие от vector, которому по мере роста требуется перераспределять и копировать все элементы, в deque при необходимости выделяются новые блоки без перемещения имеющихся элементов.
Рассмотрим этот сценарий:
std::deque<int> d;
for (int i = 0; i < 1000000; ++i) {
d.push_back(i);
}
В векторе vector это чревато перераспределениями и копированиями. В двусторонней очереди deque при необходимости просто выделяются новые блоки, имеющиеся же элементы остаются нетронутыми.
Произвольный доступ в deque
В deque, как и в vector, обеспечивается доступ к элементам за постоянное время, но из-за блочной структуры реализация здесь сложнее:
template <typename T>
T& SimpleDeque<T>::operator[](size_t n) {
size_t block = (start + n) / BLOCK_SIZE;
size_t offset = (start + n) % BLOCK_SIZE;
return map[front_block + block][offset];
}
Этой функцией вычисляется, в каком блоке находится элемент и его смещение внутри этого блока.
Вставка и удаление спереди и сзади
Отличительная особенность deque — эффективные вставка и удаление с обоих концов. Вот как реализуется push_front:
template <typename T>
void SimpleDeque<T>::push_front(const T& value) {
if (size == 0 || start == 0) {
if (front_block == 0) {
// Изменение размера «map» выполняется аналогично «push_back»
}
if (map[front_block - 1] == nullptr) {
map[front_block - 1] = new T[BLOCK_SIZE];
}
--front_block;
start = BLOCK_SIZE;
}
--start;
map[front_block][start] = value;
++size;
}
Этой функцией обрабатывается случай, когда спереди выделяется новый блок. Аналогично тому, как в push_back обрабатывается выделение сзади.
Реализация итератора
Из-за блочной структуры итераторы для deque сложнее, чем для vector. Вот упрощенный итератор:
template <typename T>
class SimpleDequeIterator {
private:
SimpleDeque<T>* deque;
size_t index;
public:
SimpleDequeIterator(SimpleDeque<T>* d, size_t i) : deque(d), index(i) {}
T& operator*() {
return (*deque)[index];
}
SimpleDequeIterator& operator++() {
++index;
return *this;
}
bool operator!=(const SimpleDequeIterator& other) const {
return index != other.index;
}
};
Этот итератор обращается к элементам при помощи оператора [] deque, которым блочная структура управляется внутри.
Реальный сценарий: планировщик процессов
Рассмотрим практическое применение deque в простом планировщике процессов:
#include <deque>
#include <string>
#include <iostream>
struct Process {
std::string name;
int priority;
int burst_time;
Process(std::string n, int p, int b) : name(n), priority(p), burst_time(b) {}
};
class Scheduler {
private:
std::deque<Process> high_priority;
std::deque<Process> low_priority;
public:
void add_process(const Process& p) {
if (p.priority > 5) {
high_priority.push_back(p);
} else {
low_priority.push_back(p);
}
}
void run() {
while (!high_priority.empty() || !low_priority.empty()) {
if (!high_priority.empty()) {
Process p = high_priority.front();
high_priority.pop_front();
std::cout << "Running high priority process: " << p.name << std::endl;
p.burst_time -= 2;
if (p.burst_time > 0) {
high_priority.push_back(p);
}
} else {
Process p = low_priority.front();
low_priority.pop_front();
std::cout << "Running low priority process: " << p.name << std::endl;
p.burst_time -= 1;
if (p.burst_time > 0) {
low_priority.push_back(p);
}
}
}
}
};
int main() {
Scheduler scheduler;
scheduler.add_process(Process("P1", 7, 5));
scheduler.add_process(Process("P2", 4, 3));
scheduler.add_process(Process("P3", 6, 4));
scheduler.add_process(Process("P4", 3, 2));
scheduler.run();
return 0;
}
Процессы различной приоритетности управляются в этом планировщике двумя deque, ведь deque эффективна в операциях и в начале, и в конце контейнера.
Производительность
У эффективности этих операций в deque имеется оборотная сторона:
- Расход памяти: при блочной структуре в конце каждого блока остается неиспользуемое пространство.
- Эффективность кэширования при операциях обхода в deque ниже, чем в vector. Причина — несмежное размещение в памяти.
- Инвалидация итератора и ссылок при добавлении или удалении элементов.
Вот простой тест производительности для сравнения vector и deque:
#include <vector>
#include <deque>
#include <chrono>
#include <iostream>
template<typename T>
void benchmark(T& container, int operations) {
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < operations; ++i) {
container.push_back(i);
}
for (int i = 0; i < operations; ++i) {
container.pop_front();
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Time taken: " << diff.count() << " seconds" << std::endl;
}
int main() {
const int OPERATIONS = 1000000;
std::vector<int> v;
std::deque<int> d;
std::cout << "Vector: ";
benchmark(v, OPERATIONS);
std::cout << "Deque: ";
benchmark(d, OPERATIONS);
return 0;
}
По тесту производительности, в этих операциях deque быстрее. Особенно в pop_front, выполняемой вектором vector за O(n), а двусторонней очередью deque за O(1).
Заключение
Мы изучили реализацию deque на C++, нюансы производительности и применимые сценарии.
Блочной структурой обеспечивается эффективная вставка и удаление элементов в начале и в конце, поэтому deque идеальна для сценариев, где элементы часто добавляются или удаляются с обеих сторон.
Реализация deque сложнее, чем для vector. Однако применяемое в vector сохранение элементов в смежных участках памяти сбалансировано здесь с узловой структурой списка.
Поэтому deque — универсальный контейнер, который хорош в самых разных сценариях: от планирования процессов до управления операциями отмены/повтора в программном обеспечении.
Читайте также:
- Удаление последнего символа строки на C++: методы и их применение
- Чем отличается C++ от C#?
- Шаблон проектирования прототипов в современном C++
Читайте нас в Telegram, VK и Дзен
Перевод статьи ryan: How Deque is Implemented in C++: An In-Depth Look
