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

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

[email protected]

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

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

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

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

4.

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

5.

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

6.

Страничная организация дека дает значительные преимущества:
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)

7.

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_reverse_iterator;

8.

// размещение/удаление:
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);

9.

// средства доступа:
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;

10.

// вставка/стирание:
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 <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);

11.

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

12.

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

13. insert

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

14. Пример

#include <iostream>
#include <deque>
#include <vector>
int main () {
std::deque<int> mydeque;
// установить некоторые начальные значения:
for (int i=1; i<6; i++) mydeque.push_back(i); // 1 2 3 4 5
std::deque<int>::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<int> myvector (2,30);
mydeque.insert (it,myvector.begin(),myvector.end()); // 1 20 30 30 20 10 2 3 4 5

15.

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

16. erase

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

17. Пример

#include <iostream>
#include <deque>
int main () {
std::deque<int> 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<int>::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

18. Пример еще

#include ‹iostream.h›
#include <deque>
int main() {
deque<int> 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;
}

19. push_front

#include <iostream>
#include <deque>
int main ()
{
std::deque<int> 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<int>::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}

20. pop_front

Удаляет первый элемент в контейнере deque, эффективно уменьшая его
размер на единицу, разрушая удаленный элемент.
#include <iostream>
#include <deque>
int main () {
std::deque<int> 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

21. Изменение элементов очереди

Функция assign() позволяет заменить все элементы очереди
определенным набором. Она имеет следующие формы:
assign( il ): заменяет содержимое контейнера элементами из списка
инициализации il .
assign(n, value): заменяет содержимое контейнера n элементами,
которые имеют значение value
assign(begin, end): заменяет содержимое контейнера элементами из
диапазона, на начало и конец которого указывают итераторы begin и end
std::deque<int> numbers = { 1, 2, 3, 4, 5 };
numbers.assign({ 21, 22, 23, 24, 25 }); // numbers = { 21, 22, 23, 24, 25 }
numbers.assign(4, 3);
// numbers = {3, 3, 3, 3}
std::deque<int> values = { 6, 7, 8, 9, 10, 11 };
auto start = values.begin() + 2;
auto end = values.end();
numbers.assign(start, end);
// итератор на третий элемент
// итератор на последний элемент

22. swap

обменивает значениями две очереди:
std::deque<int> deque1 = { 1, 2, 3, 4, 5 };
std::deque<int> deque2 = { 6, 7, 8, 9};
deque1.swap(deque2);
// deque1 = { 6, 7, 8, 9};

23. Удаление элементов

clear(p): удаляет все элементы
pop_back(): удаляет последний элемент
pop_front(): удаляет первый элемент
erase(p): удаляет элемент, на который указывает итератор p. Возвращает
итератор на элемент, следующий после удаленного, или на конец
контейнера, если удален последний элемент
erase(begin, end): удаляет элементы из диапазона, на начало и конец
которого указывают итераторы begin и end. Возвращает итератор на
элемент, следующий после последнего удаленного, или на конец
контейнера, если удален последний элемент
При удалении стоит учитывать, что удаление элементов из любой
позиции (за исключением удаления первого и последнего элементов)
делает все итераторы, указатели и ссылки на элементы deque
недействительными.

24.

std::deque<int> numbers = { 1, 2, 3, 4, 5 };
numbers.pop_front();
// numbers = { 2, 3, 4, 5 }
numbers.pop_back();
// numbers = { 2, 3, 4 }
numbers.clear();
// numbers ={ }
numbers = { 1, 2, 3, 4, 5 };
auto iter = numbers.cbegin(); // указатель на первый элемент
numbers.erase( iter );
// удаляем первый элемент
// numbers = { 2, 4, 5, 6 }
numbers = { 1, 2, 3, 4, 5 };
auto begin = numbers.begin(); // указатель на первый элемент
auto end = numbers.end();
// указатель на последний элемент
numbers.erase(++begin, --end); // удаляем со второго элемента до
последнего
//numbers = {1, 5}

25. Адаптеры контейнеров

26. Часто бывает полезно обеспечить ограниченные интерфейсы контейнеров. Библиотека STL предоставляет stack, queue и priority_queue

через адаптеры,
которые могут работать с различными типами последовательностей.
Адаптировать - это значит приспосабливать. То есть приспосабливать
существующую сущность, контейнер, итератор и т.д., в новом контексте или
для частной задачи.
Например, стандартный контейнер двусвязный список std::list имеет такие
методы, как push_back, push_front, pop_back, pop_front, front, back.
Используя лишь подмножество методов, предоставляемых контейнером
std::list, можно смоделировать поведение такой структуры данных, как стек.

27. stack

Любая последовательность, поддерживающая операции back, push_back
и pop_back, может использоваться для адаптации stack. В частности, могут
использоваться vector, list и deque.
template <class Container>
class stack {
friend bool operator==(const stack<Container>& х,
const stack <Container>& y);
friend bool operator<(const stack<Container>& х,
const stack <Container>& y);
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;

28.  protected:     Container c;    public:     bool empty() const { return c.empty(); }     size_type size() const { return

protected:
Container c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size();}
value_type& top() { return c.back(); }
const value_type& top() const {return c.back();}
void push(const value_type& х) { с.push_back(х);}
void pop() {c.pop_back();}
}; // class stack
template <class Container>
bool operator==(const stack <Container>& х,
const stack <Container>& y) {return х.с == у.с;}
template <class Container>
bool operator<(const stack<Container>& х, const stack<Container>& y)
{return х.с < у.с;}
Например, stack <vector<int> > - целочисленный стек, сделанный из vector,
а stack <deque<char> > - символьный стек, сделанный из deque.

29. В структуре данных стек данные организованы по принципу: последний вошел в стек - первый вышел из стека, то есть LIFO (last in,

first out).
Обычно методы контейнера стек получают названия push, pop, top.
Чтобы построить в C++ из списка стек, достаточно использовать методы
либо push_front, pop_front, front, либо push_back, pop_back, back
соответственно для методов стека push, pop, top.
Для этого просто в реализации данных методов стека следует вызывать
соответствующие методы контейнера std::list или другого подходящего
контейнера.
Например, метод стека pop может быть реализован как вызов
соответствующего метода контейнера std::list:
void pop() { c.pop_back(); }
или
void pop() { c.pop_front(); }
Поэтому нет необходимости определять управление данными контейнера
стек. Всю работу по управлению данными возьмет на себя контейнер std::list.
Просто его методы, фактически, переименованы для адаптации к названиям
методов контейнера стек.

30. Т.е. стек реализован не с нуля, он просто является адаптацией класса std::list (или vector или deque) под логику работы стека,

то есть стек - это
адаптер контейнера.
Чтобы было возможно как можно больше последовательных контейнеров
адаптировать под стек, было принято соглашение ограничиться методами
последовательных контейнеров push_back, pop_back, и back, так как эти
методы более широко распространены среди последовательных контейнеров.
Например, контейнер std::vector не имеет методов push_front и pop_front,
поэтому его нельзя было использовать для моделирования методов стека,
используя именно эти методы последовательных контейнеров.
Однако стандартный последовательный контейнер std::forward_list, который
был введен в стандарт C++ позже остальных стандартных последовательных
контейнеров, не имеет методов push_back, pop_back и back. Поэтому адаптер
контейнеров std::stack не может адаптировать этот контейнер для реализации
стека.
Адаптер stack теряет многие присущие базовому контейнеру методы (
например, at(), [ ] и др.), но приобретает свои собственные (push(), pop()).
(по материалу: https://ru.stackoverflow.com/questions/479987/Что-такоеадаптер)

31. Пример

#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
int main( int argc, char *argv[ ]) {
setlocale(LC_ALL, "rus");
stack<string> st;
stack<string, vector<string> > vst( vector<string>({ "строка 1", "строка 2" }) );
vst.push("последняя строка");
while ( ! vst.empty() ) {
cout << vst.top() << " : в стеке строк " << vst.size() << endl;
vst.pop();
}
cout << "стек " << (vst.empty() ? "" : "не ") << "пуст" << endl;
}
Вывод: последняя строка : в стеке строк 3
строка 2 : в стеке строк 2 \n строка 1 : в стеке строк 1

32. stack::top

Возвращает ссылку на верхний элемент в stack.
Поскольку стеки являются контейнерами, входящими последними
первыми, верхний элемент является последним элементом, вставленным в
стек.
Эта функция-член эффективно вызывает элемент back базового объекта
контейнера.

33. Пример

#include <iostream>
// std::cout
#include <stack>
// std::stack
int main () {
std::stack<int> mystack;
mystack.push(10);
mystack.push(20);
mystack.top() -= 5;
std::cout << "mystack.top() is now " << mystack.top() << '\n';
return 0;
}
Output:
mystack.top() is now 15

34. <queue>

<queue>
Заголовок, определяющий классы адаптера контейнеров queue и
priority_queue:
Здесь определяются шаблонные классы:
Очередь : FIFO (first in, first out — «первым пришёл — первым ушёл») )
queue (class template )
Очередь с приоритетом : Priority queue (class template )

35. Очередь (queue)

Любая последовательность, поддерживающая операции front, push_back
и pop_front, может использоваться для адаптации queue. В частности, могут
использоваться list и deque.
В противоположность стеку очередь – это коллекция данных,
функционирующая по принципу FIFO (First In — First Out). Она похожа на
трубу, в один конец которой данные втекают, а из другого конца - вытекают.
template <class Container>
class queue {
friend bool operator== (const queue<Container>& х,
const queue<Container>& y);
friend bool operator< (const queue<Container>& х,
const queue<Container>& y);
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;

36. protected:     Container c;    public:     bool empty() const {return c.empty();}     size_type size() const {return c.size();}

protected:
Container c;
public:
bool empty() const {return c.empty();}
size_type size() const {return c.size();}
value_type& front() {return c.front();}
const value_type& front() const {return c.front();}
value_type& back() {return c.back();}
const value_type& back() const {return c.back();}
void push(const value_type& х) {с.push_back(х);}
void pop() {с.pop_front();}
}; // class queue
template <class Container>
bool operator==(const queue<Container>& х, const queue<Container>& y)
{return х.с == у.с;}
template <class Container>
bool operator<(const queue<Container>& х, const queue<Container>& y)
{return х.с < у.с;}

37. Пример

#include <list>
#include <queue>
#include <string>
using namespace std;
int main(int argc, char* argv[ ]) {
setlocale(LC_ALL, "rus");
queue <string> st;
queue <string, list<string> > vst( list<string>({ "строка 1", "строка 2" }) );
vst.push("последняя строка");
while (!vst.empty()) {
cout << vst.front() << " : в очереди строк " << vst.size() << " ";
vst.pop();
}
cout << "очередь " << (vst.empty() ? "" : "не ") << "пуста" << endl;
}
Вывод: строка 1 : в очереди строк 3 строка 2 : в очереди строк 2 последняя
строка : в очереди строк 1 очередь пуста

38. Пример

#include <iostream>
#include <deque>
#include <list>
#include <queue>
int main () {
std::deque<int> mydeck (3,100);
std::list<int> mylist (2,200);
// deque с 3 элементами
// список с 2 элементами
// пустая queue
// инициализируется копией deque
// пустая очередь со списком в
std::queue<int, std::list<int> > third; // list - качестве базового контейнера
std::queue<int, std::list<int> > fourth (mylist);
std::cout << "size of first: " << first.size() << '\n';
std::cout << "size of second: " << second.size() << '\n';
std::cout << "size of third: " << third.size() << '\n';
std::cout << "size of fourth: " << fourth.size() << '\n';
return 0; }
Output:
size of first: 0
size of second: 3
size of third: 0
std::queue<int> first;
std::queue<int> second (mydeck);

39. push и pop

push вставляет новый элемент в конце очереди, после его текущего
последнего элемента. Содержимое этого нового элемента инициализируется в
val. Эта функция-член эффективно вызывает функцию-член push_back
базового объекта контейнера. В следующем примере push используется для
добавления новых элементов в очередь, которые затем выскакивают в том же
порядке.
pop удаляет следующий элемент в очереди, эффективно уменьшая его
размер на единицу.
Удаленный элемент является "самым старым" элементом в очереди,
значение которого можно получить, вызвав элемент queue::front.
pop вызывает деструктор удаляемого элемента.
Эта функция-член вызывает функцию-член pop_front базового объекта
контейнера.

40. Пример

#include <iostream>
// std::cin, std::cout
#include <queue>
// std::queue
int main () {
std::queue<int> myqueue;
int myint;
std::cout << "Please enter some integers (enter 0 to end):\n";
do {
std::cin >> myint;
myqueue.push (myint);
} while (myint);
std::cout << "myqueue contains: ";
while (!myqueue.empty()) {
std::cout << ' ' << myqueue.front();
myqueue.pop();
}
std::cout << '\n';
return 0;
}

41. Очередь с приоритетами (priority_queue )

Любая последовательность, с итератором произвольного доступа и
поддерживающая операции front, push_back и pop_front, может использоваться
для адаптера priority_queue. В частности, могут использоваться vector и
deque.
template <class Container, class Compare = less<Container::value_type> >
class priority_queue {
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
protected:
Container c;
Compare comp;

42.  public:     priority_queue(const Compare& х = Compare()): c(), comp(х) { }     template <class InputIterator >

public:
priority_queue(const Compare& х = Compare()): c(), comp(х) { }
template <class InputIterator >
priority_queue(InputIterator first, InputIterator last,
const Compare& х = Compare()): c(first, last), comp(x)
{ make_heap( c.begin(), с.end(), comp); }
bool empty() const { return c.empty();}
size_type size() const { return c.size(); }
const value_type& top() const { return c.front();}
void push(const value_type& х) {
c.push_back(х);
push_heap(c.begin(), c.end(), comp);
}
void pop() {
pop_heap(c.begin(), c.end(), comp);
с.рор_bасk();
}
}; // Никакое равенство не полагается

43. template <class RandomAccessIterator> void make_heap (RandomAccessIterator first, RandomAccessIterator last); template <class

template <class RandomAccessIterator>
void make_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void make_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
Сделать пирамиду из диапазона.
Упорядочивает элементы в диапазоне [first,last) таким образом, чтобы они
образовывали пирамиду.
Пирамида - это способ организации элементов диапазона, который позволяет
быстро извлекать элемент с наибольшим значением в любой момент (с помощью
pop_heap), даже неоднократно, позволяя при этом быстро вставлять новые
элементы (с помощью push_heap).
Всегда указывается элемент с наибольшим значением first. Порядок других
элементов зависит от конкретной реализации, но он согласован во всех функциях
этого заголовка, связанных с пирамидой.
Элементы сравниваются с помощью operator<(для первой версии), или comp
(для второго): Элемент с наибольшим значением - это элемент, для которого это
будет возвращено false по сравнению с любым другим элементом в диапазоне.
Стандартный адаптер контейнера priority_queue вызывает make_heap,
push_heap и pop_heap автоматически и поддерживает свойства кучи для
контейнера.

44. Очереди с приоритетом - это тип контейнерных адаптеров, специально разработанных таким образом, чтобы его первый элемент всегда

был
самым большим из содержащихся в нем элементов, в соответствии с
каким-то критерием упорядочивания.
Контекст использования этого адаптера похож на кучу (пирамиду), где
элементы могут быть вставлены в любой момент, и только
максимальный элемент кучи может быть извлечен (тот, который
находится сверху в очереди приоритетов).
Очереди с приоритетом реализуются в виде контейнерных адаптеров,
которые представляют собой классы, использующие инкапсулированный
объект конкретного контейнерного класса в качестве своего базового
контейнера, предоставляющего определенный набор функций-членов для
доступа к своим элементам.

45. Способы реализации очереди с приоритетами

В очереди с приоритетами каждому элементу ставится в соответствие
приоритет (весовой коэффициент).
Очередь с приоритетами может быть реализована одним из двух
способов:
- очередь с приоритетным включением. В этом случае элемент, который
добавляется в очередь, сразу размещается в ней в соответствии с его
приоритетом. При удалении, этот элемент просто отсекается с конца очереди;
- очередь с приоритетным исключением. В этом случае новый элемент
просто добавляется в конец очереди. А вытягивание элемента из очереди
осуществляется по его приоритету, то есть вытягивается элемент с
наивысшим приоритетом.

46. priority_queue::top

#include <iostream>
#include <queue>
int main () {
std::priority_queue<int> mypq;
mypq.push(10);
mypq.push(20);
mypq.push(15);
std::cout << "mypq.top() is now " << mypq.top() << '\n';
return 0;
}
Output:
mypq.top() is now 20

47. priority_queue::emplace

#include <iostream>
#include <queue>
#include <string>
int main () {
std::priority_queue<std::string> mypq;
mypq.emplace("orange");
mypq.emplace("strawberry");
mypq.emplace("apple");
mypq.emplace("pear");
std::cout << "mypq contains:";
while (!mypq.empty()) {
std::cout << ' ' << mypq.top();
mypq.pop();
}
std::cout << '\n';
return 0;
}
Output: mypq contains: strawberry pear orange apple

48. priority_queue::swap

#include <iostream>
#include <queue>
int main () {
std::priority_queue<int> foo,bar;
foo.push (15); foo.push(30); foo.push(10);
bar.push (101); bar.push(202);
foo.swap(bar);
std::cout << "size of foo: " << foo.size() << '\n';
std::cout << "size of bar: " << bar.size() << '\n';
return 0;
}
Output:
size of foo: 2
size of bar: 3

49. Создание динамически связываемой библиотеки (DLL) на C++

Запускаем Visual Studio и создаём проект библиотеки DLL, назовём его
myDLL. Там сразу есть файл myDLL.h, поместим в него следующий код:
#ifdef MYDLL_EXPORTS
#define MYDLL_API __declspec(dllexport)
#else
#define MYDLL_API __declspec(dllimport)
#endif
class MyDLL
{
public:
// a * b
static MYDLL_API string test(int x, int y);
};

50.

51.

52. Теперь найдём в проекте файл myDLL.cpp и добавим туда код : #include <string> #include <sstream> using namespace std; template

Теперь найдём в проекте файл myDLL.cpp и добавим туда код :
#include <string>
#include <sstream>
using namespace std;
template <typename T>
std::string toString(T val) {
std::ostringstream oss;
oss << val;
return oss.str();
}
template<typename T>
T fromString(const std::string& s) {
std::istringstream iss(s);
T res;
iss >> res;
return res;
}
string MyDLL::test(int x, int y) {
return toString (x * y);
}

53. Используем эту библиотеку в другом проекте. В Visual Studio добавим в решение (solution) классическое приложение testMyDLL. Для

использования в приложении функций, созданных в библиотеке DLL,
необходимо сослаться на эту библиотеку.
В свойствах проекта выберите Common Properties->References (добавить
ссылку), добавьте ссылку на myDLL, нажав кнопку «Add New Reference…»
(Добавить ссылку).

54.

55.

56. Затем, прописываем путь путь к файлу myDLL.h из соседнего проекта библиотеки DLL. #include "..\\MyDll\MyDll.h" В функцию

Затем, прописываем путь путь к файлу myDLL.h из соседнего проекта
библиотеки DLL.
#include "..\\MyDll\MyDll.h"
В функцию WndProc, в отработку сообщения WM_PAINT добавляем код:
PAINTSTRUCT ps;
HDC hdc = BeginPaint ( hWnd, &ps);
std::string s= MyDLL::test (32, 45) ;
TextOutA (hdc, 100, 200, s.c_str(), s.size() );
EndPaint(hWnd, &ps);
Смотрим за результатом.
Примечание: чтобы проект запустился, надо назначить его запускаемым
(рис ниже), щелкнув правой клавишей на проекте в окне «Обозреватель
решений»

57.

58. Для разнообразия я добавил в класс еще нестатическую функцию-член: string MYDLL_API str(); И определил ее так: string

MyDLL::str( ) {
return "проверка";
}
А вызвал так:
MyDLL md; // создаем автоматический объект
// рисуем строку
TextOutA(hdc, 100, 300, md.str().c_str(), md.str().size());
Результат показан на следующем рисунке.

59.

60. ДЗ

Проект 35.
Попробовать создать решение (это потребуется для курсовой работы в
следующем семестре), состоящее из 2-х проектов, как я показал на слайдах.
Пусть есть два связанных полиморфно класса. Положить их в DLL, а
затем экспортировать в простом exe-проекте ( Классическое приложение
Windows).
Каждый класс заполнить нужными функциями, заполняя информацией
члены данных своих классов. ( члены-данных в базовом типа string*, в
производном: list<string*>).
В Exe- проекте разместить по одному объекту в глобальном хранилище
типа vector <your_Base*>
Распечатать данные из вектора (при обработке сообщения WM_PAINT)
построчно в окне программы, используя функцию TextOut.

61. КР

Создать базовый (Base) и производный класс полиморфной иерархии
именем своей фамилии и имени.
Создать в базовом классе член-данных типа int* , выделить для него
память и инициализировать ее произвольным числом в конструкторе по
умолчанию.
В производном классе создать член-данных типа float* и положить туда
число пи в конструкторе по умолчанию.
В функции main создать два хранилища типа deque < Base *>.
В первое хранилище положить (создавая на ходу) по 2 объекта базового и
производного типа.
А затем провести глубокое копирование из 1-го хранилища во второе.