Руководство по стандартной библиотеке шаблонов STL

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


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

template class Allocator = allocator> class deque { public: // typedefs: typedef iterator; typedef const_iterator; typedef Allocator::pointer pointer; typedef Allocator ::reference reference; typedef Allocator::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& x); template deque(InputIterator first, InputIterator last); ~deque(); deque& operator=(const deque& x); void swap(deque& 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 bool operator==(const deque& x, const deque& y); template bool operator& x, const deque& 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 (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.

Содержание раздела