Объектно-ориентированное программирование на c++

ООП 2021 Лекция 12 Двусторонняя очередь: deque Адаптеры контейнеров: stack, queue, priority_queue. Создание DLL [e-mail]

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

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

Когда что применять

• - vectоr - тип последовательности, которая используется по умолчанию.
• - list нужно использовать, когда имеются частые вставки и удаления из середины последовательности.
• - deque - структура данных для выбора, когда большинство вставок и удалений происходит в начале или в конце последовательности.

• deque можно рассматривать как vector, чья внутренняя память разделена на части.
• deque хранит блоки, или "страницы" объектов; реальный размер страниц стандартом не определяется и зависит в первую очередь от размера объекта T и от выбора, сделанного разработчиком стандартной библиотеки.
• Такое разбиение на страницы требует хранения одного дополнительного указателя на страницу, что приводит к дополнительным расходам, составляющим доли бита на один объект.
• Например, в системе с 8-битовыми байтами и 4-битовыми целыми числами и указателями deque с 4-Кбайтовой страницей приводит к расходам памяти, равным 1/32=0.03125 бита на один int. Других накладных расходов не имеется, поскольку deque не хранит никаких дополнительных указателей или другой информации для отдельных объектов T.
• В стандарте нет требования, чтобы страницы deque представляли собой С-массивы, однако это общепринятый способ реализации.

• Рассмотрите возможность предпочтения deque по умолчанию вместо vector, особенно когда содержащийся тип является классом или структурой, а не встроенным типом, если только вам действительно не нужно, чтобы память контейнера была непрерывной.
• vector и deque предлагают почти идентичные интерфейсы и, как правило, взаимозаменяемы. deque также предлагает push_front () и pop_front (), чего вектор не делает. Правда, вектор предлагает capacity() и reserve(), чего нет у дека, но это не потеря - эти функции на самом деле являются слабостью вектора.
• Основное структурное различие между vector и deque заключается в том, как два контейнера организуют свое внутреннее хранилище: deque распределяет свое хранилище по страницам, или "кускам", с фиксированным количеством содержащихся элементов на каждой странице; Именно поэтому deque часто сравнивают с колодой карт, хотя его название первоначально произошло от "двусторонней очереди" из-за способности эффективно вставлять элементы в любом конце последовательности. С другой стороны, вектор выделяет непрерывный блок памяти и может эффективно вставлять элементы только в конце последовательности.

• Страничная организация дека дает значительные преимущества:
• 1. deque предлагает операции insert() и erase() с постоянным временем в передней части контейнера, в то время как вектор этого не делает- отсюда и примечание в стандарте об использовании дека, если вам нужно вставить или стереть на обоих концах последовательности.
• 2. deque использует память более удобным для операционной системы способом, особенно в системах без виртуальной памяти. Например, 10 -мегабайтный вектор использует один 10-мегабайтный блок памяти, который обычно менее эффективен на практике, чем 10-мегабайтный дек, который может поместиться в ряд меньших блоков памяти.
• 3. Дек проще в использовании и по своей сути более эффективен для роста, чем вектор. Единственные операции, поставляемые вектором, которых нет у deque, - это capacity() и reserve (), и это потому, что deque в них не нуждается! Например, вызов reserve() перед большим числом вызовов push_back () может исключить перераспределение все более крупных версий одного и того же буфера каждый раз, когда он обнаруживает, что текущий буфер недостаточно велик. У deque нет такой проблемы, и наличие deque::reserve() перед большим количеством вызовов push_back() не исключило бы никаких выделений памяти, потому что ни одно из выделений не является избыточным; deque должен выделить одинаковое количество дополнительных страниц, независимо от того, делает ли он это все сразу или по мере того, как элементы фактически добавляются. (по материалу http://www.gotw.ca/gotw/054.htm)

•  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);
• }; // конец deque
• template
• bool operator==(const deque& x, const deque& y);
•  
• template
• bool operator<(const deque& x, const deque& y);

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

• assign присвоить контейнеру данные
• push_back вставить в конец
• push_front вставить в начало
• pop_back удалить последний
• pop_front удалить первый
• insert вставка
• erase стирание (удаление)
• swap обмен
• clear очищение контейнера
• emplace создает и вставляет
• emplace_front создает и вставляет в начало
• emplace_back создает и вставляет в конец

• Модификаторы

insert

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

Пример

• #include
• #include
• #include
• int main () {
• std::deque mydeque;
• // установить некоторые начальные значения:
• for (int i=1; i<6; i++) mydeque.push_back(i); // 1 2 3 4 5
• std::deque::iterator it = mydeque.begin();
• ++it;
• it = mydeque.insert (it,10); // 1 10 2 3 4 5
• // " it " теперь указывает на недавно вставленный 10
• mydeque.insert (it,2,20); // 1 20 20 10 2 3 4 5
• // " it " больше недействителен!
• it = mydeque.begin()+2;
• std::vector myvector (2,30);
• mydeque.insert (it,myvector.begin(),myvector.end()); // 1 20 30 30 20 10 2 3 4 5

• std::cout << "mydeque contains:";
• for ( it=mydeque.begin(); it != mydeque.end(); ++it)
• std::cout << ' ' << *it;
• std::cout << '\n';
• return 0;
• }
• Output:
• mydeque contains: 1 20 30 30 20 10 2 3 4 5

erase

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

Пример

• #include
• #include
• int main () {
• std::deque mydeque;
• // установить некоторые значения (от 1 до 10)
• for (int i=1; i<=10; i++) mydeque.push_back(i);
• // стереть шестой элемент
• mydeque.erase (mydeque.begin()+5);
• // стереть первые 3 элемента:
• mydeque.erase (mydeque.begin(),mydeque.begin()+3);
• std::cout << "mydeque contains:";
• for (std::deque::iterator it = mydeque.begin(); it!=mydeque.end(); ++it)
• std::cout << ' ' << *it;
• std::cout << '\n';
• return 0;
• }
• Output:
• mydeque contains: 4 5 7 8 9 10

Пример еще

• #include ‹iostream.h›
• #include
• int main() {
• deque d;
• d.push_back(4); // Add after end.
• d.push_back(9);
• d.push_back(16);
• d.push_front(1); // Insert at beginning.
• for (int i = 0; i < d.size(); i++)
• cout << "d[" << i << "] = " << d[i] << endl;
• cout << endl;
• d.pop_front(); // Erase first element.
• d[2] = 25; // Replace last element.
• for (i = 0; i < d.size(); i++)
• cout << "d[" << i << "] = " << d[i] << endl;
• return 0; }

push_front

• #include
• #include
• int main ()
• {
• std::deque mydeque (2,100); // two ints with a value of 100
• mydeque.push_front (200);
• mydeque.push_front (300);
• std::cout << "mydeque contains:";
• for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
• std::cout << ' ' << *it;
• std::cout << '\n';
• return 0;
• }
• Output: 300 200 100 100

pop_front

• Удаляет первый элемент в контейнере deque, эффективно уменьшая его размер на единицу, разрушая удаленный элемент.
• #include
• #include
• int main () {
• std::deque mydeque;
• mydeque.push_back (100);
• mydeque.push_back (200);
• mydeque.push_back (300);
• std::cout << "Вырвать элементы из дека:";
• while (!mydeque.empty()) {
• std::cout << ' ' << mydeque.front();
• mydeque.pop_front();
• }
• std::cout << "\nThe final size of mydeque is " << int(mydeque.size()) << '\n';
• return 0; }
• Output: Вырвать элементы из дека : 100 200 300
• The final size of mydeque is 0