Двусторонняя очередь (Deque)

Двусторонняя очередь (Deque)

deque - вид последовательности, которая, подобно вектору, поддерживает итераторы произвольного доступа. Кроме того она поддерживает операции вставки и стирания в начале или в конце за постоянное время; вставка и стирание в середине занимают линейное время. Как с векторами, управление памятью обрабатывается автоматически.

template ‹class T, template ‹class U› class Allocator = allocator›

class deque {

public:

 // typedefs:

 typedef iterator;

 typedef const_iterator;

 typedef Allocator‹T›::pointer pointer;

 typedef Allocator‹T›::reference reference;

 typedef Allocator‹T›::const_reference const_reference;

 typedef size_type;

 typedef difference_type;

 typedef Т value_type;

 typedef reverse_iterator;

 typedef const_revcrse_iterator;

 // размещение/удаление:

 deque();

 deque(size_type n, const T& value = T());

 deque(const deque‹T, Allocator›& x);

 template ‹class InputIterator›

 deque(InputIterator first, InputIterator last);

 ~deque();

 deque‹T, Allocator›& operator=(const deque‹T,Allocator›& x);

 void swap(deque‹T, Allocator›& x);

 // средства доступа:

 iterator begin();

 const_iterator begin() const;

 iterator end();

 const_iterator end() const;

 reverse_iterator rbegin();

 const_reverse_iterator rbegin();

 reverse_iterator rend();

 const_reverse_iterator rend();

 size_type size() const;

 size_type max_size() const;

 bool empty() const;

 reference operator[](size_type n);

 const_reference operator[](size_type n) const;

 reference front();

 const_reference front() const;

 reference back();

 const_reference back() const;

 // вставка/стирание:

 void push_front(const T& x);

 void push_back(const T& x);

 iterator insert(iterator position, const T& x = T());

 void insert(iterator position, size_type n, const T& x);

 template

 void insert(iterator position, InputIterator first, InputIterator last);

 void pop_front();

 void pop_back();

 void erase(iterator position);

 void erase(iterator first, iterator last);

};

template ‹class T, class Allocator›

bool operator==(const deque‹T, Allocator›& x, const deque‹T, Allocator›& y);

template ‹class T, class Allocator›

bool operator‹(const deque‹T, Allocator›& x, const deque‹T, Allocator›& y);

iterator - итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.

const_iterator - постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

difference_type - знаковый целочисленный тип. Точный зависит от исполнения и определяется в Allocator.

insert (вставка) в середину двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. insert и push (помещение) с обоих концов двусторонней очереди делают недействительными все итераторы двусторонней очереди, но не влияют на действительность всех ссылок на двустороннюю очередь. В худшем случае вставка единственного элемента в двустороннюю очередь занимает линейное время от минимума двух расстояний: от точки вставки - до начала и до конца двусторонней очереди. Вставка единственного элемента либо в начало, либо в конец двусторонней очереди всегда занимает постоянное время и вызывает единственный запрос конструктора копии T. То есть двусторонняя очередь особенно оптимизирована для помещения и извлечения элементов в начале и в конце.

erase (стирание) в середине двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. erase и pop (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Очередь диспетчеризации задач

Из книги автора

Очередь диспетчеризации задач TDE всех задач, которые могут выполняться на процессоре в любой данный момент времени, объединены в структуру данных, называемую очередью диспетчеризации задач TDQ (task dispatching queue). TDQ реализована как связный список в памяти, в котором TDE


Очередь видеомонтажа

Из книги автора

Очередь видеомонтажа Окно очереди видеомонтажа, расположенное в левой части окна Video Post (Видеомонтаж), представляет собой список событий, выполняемых последовательно сверху вниз. Если в списке присутствуют события, являющиеся дочерними по отношению к другим событиям


Очередь (Queue)

Из книги автора

Очередь (Queue) Любая последовательность, поддерживающая операции front, push_back и pop_front, может использоваться для модификации queue. В частности, могут использоваться list и deque.template ‹class Container›class queue { friend bool operator==(const queue‹Container›& х, const queue‹Container›& y); friend bool operator‹(const


Очередь с приоритетами (Priority queue)

Из книги автора

Очередь с приоритетами (Priority queue) Любая последовательность, с итератором произвольного доступа и поддерживающая операции front, push_back и pop_front, может использоваться для модификации priority_queue. В частности, могут использоваться vector и deque.template ‹class Container, class Compare = less‹Container::value_type›


Очередь по приоритету

Из книги автора

Очередь по приоритету Фактически, упомянутый пример обусловливает название новой структуры данных, называемой очередью по приоритету. Для очереди по приоритету (priority queue) определены две базовых операции: добавление элемента (как и ранее) и извлечение элемента с


6.17. Очередь и очередь с приоритетами

Из книги автора

6.17. Очередь и очередь с приоритетами Абстракция очереди реализует метод доступа FIFO (first in, first out – “первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь


У11.10 Модуль "очередь"

Из книги автора

У11.10 Модуль "очередь" Напишите класс, реализующий очередь (стратегию доступа "первый пришел - первый ушел", FIFO - "first in - first out"). Задайте подходящие утверждения в стиле класса STACK этой


Очередь сообщений

Из книги автора

Очередь сообщений Если вы в данный момент не подключены к Интернету, ваши сообщения будут помещаться в очередь, а потом, когда вы подключитесь, будут отправлены получателям.Для вызова окна очереди SMS выполните команду Сообщения > Очередь SMS. Появится окно c перечнем


Почему республиканский заворот «Обамакэра» бьёт в первую очередь по айтишникам Сергей Голубицкий

Из книги автора

Почему республиканский заворот «Обамакэра» бьёт в первую очередь по айтишникам Сергей Голубицкий Опубликовано 04 октября 2013 В минувшую субботу палата представителей США приняла две поправки, в очередной раз притормозившие реализацию «Закона о