На этом шаге мы приведем общие сведения о деках.
Дек очень похож на вектор. Он тоже работает с элементами, оформленными в динамический массив, поддерживает произвольный доступ и обладает практически тем же интерфейсом. Различие заключается в том, что динамический массив дека открыт с обоих концов. По этой причине дек быстро выполняет операции вставки и удаления как с конца, так и с начала.
Рис.1. Логическая структура дека
Дек обычно реализуется в виде набора блоков; первый и последний блоки наращиваются в противоположных направлениях.
Рис.2. Внутренняя структура дека
Чтобы использовать дек в программе, необходимо включить в нее заголовочный файл <deque>:
#include <deque>
Тип дека определяется как шаблон класса в пространстве имен std:
namespace std {
template <class Т,
class Allocator = allocator<T> >
class deque;
}
Как и в случае с вектором, тип элементов дека передается в первом параметре шаблона. Допускается любой тип, поддерживающий присваивание и копирование. Необязательный второй параметр шаблона определяет модель памяти, по умолчанию используется модель allocator.
На следующем шаге мы рассмотрим возможности деков.
