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

Содержание

Слайд 2

Двусторонняя очередь (Deque) deque - вид последовательности, которая, подобно вектору, поддерживает

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

   deque - вид последовательности, которая, подобно вектору, поддерживает итераторы

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

Когда что применять - vectоr - тип последовательности, которая используется по

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

- vectоr - тип последовательности, которая используется по умолчанию.
-

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

deque можно рассматривать как vector , чья внутренняя память разделена на

deque можно рассматривать как vector, чья внутренняя память разделена на части.


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

Рассмотрите возможность предпочтения deque по умолчанию вместо vector, особенно когда содержащийся

Рассмотрите возможность предпочтения deque по умолчанию вместо vector, особенно когда содержащийся

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

Страничная организация дека дает значительные преимущества: 1. deque предлагает операции insert()

Страничная организация дека дает значительные преимущества:
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 Allocator = allocator> class deque { public: // typedefs:

 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_reverse_iterator;
Слайд 8

// размещение/удаление: deque(); deque( size_type n, const T& value = T()

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

// средства доступа: iterator begin(); const_iterator begin() const; iterator end(); const_iterator

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

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

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

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

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

assign присвоить контейнеру данные push_back вставить в конец push_front вставить в

assign присвоить контейнеру данные
push_back вставить в конец
push_front вставить в начало
pop_back удалить последний
pop_front удалить первый
insert вставка
erase стирание

(удаление)
swap обмен
clear очищение контейнера
emplace создает и вставляет
emplace_front создает и вставляет в начало
emplace_back создает и вставляет в конец

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

Слайд 13

insert insert (вставка) в середину двусторонней очереди делает недействительными все итераторы

insert

insert (вставка) в середину двусторонней очереди делает недействительными все итераторы

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

Пример #include #include #include int main () { std::deque mydeque; //

Пример

#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
Слайд 15

std::cout for ( it=mydeque.begin(); it != mydeque.end(); ++it) std::cout std::cout return

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

erase (стирание) в середине двусторонней очереди делает недействительными все итераторы и

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

Пример #include #include int main () { std::deque mydeque; // установить

Пример

#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
Слайд 18

Пример еще #include ‹iostream.h› #include int main() { deque d; d.push_back(4);

Пример еще

#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; }
Слайд 19

push_front #include #include int main () { std::deque mydeque (2,100); //

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
Слайд 20

pop_front Удаляет первый элемент в контейнере deque, эффективно уменьшая его размер

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
Слайд 21

Изменение элементов очереди Функция assign() позволяет заменить все элементы очереди определенным

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

Функция assign() позволяет заменить все элементы очереди определенным набором.

Она имеет следующие формы:
assign( il ): заменяет содержимое контейнера элементами из списка инициализации il .
assign(n, value): заменяет содержимое контейнера n элементами, которые имеют значение value
assign(begin, end): заменяет содержимое контейнера элементами из диапазона, на начало и конец которого указывают итераторы begin и end
std::deque 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 values = { 6, 7, 8, 9, 10, 11 };
auto start = values.begin() + 2; // итератор на третий элемент
auto end = values.end(); // итератор на последний элемент
numbers.assign(start, end);
Слайд 22

swap обменивает значениями две очереди: std::deque deque1 = { 1, 2,

swap

обменивает значениями две очереди:
std::deque deque1 = { 1, 2, 3,

4, 5 };
std::deque deque2 = { 6, 7, 8, 9};
deque1.swap(deque2); // deque1 = { 6, 7, 8, 9};
Слайд 23

Удаление элементов clear(p): удаляет все элементы pop_back(): удаляет последний элемент pop_front():

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

clear(p): удаляет все элементы
pop_back(): удаляет последний элемент
pop_front(): удаляет первый элемент
erase(p):

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

std::deque numbers = { 1, 2, 3, 4, 5 }; numbers.pop_front();

std::deque 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,

Часто бывает полезно обеспечить ограниченные интерфейсы контейнеров. Библиотека 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

   Любая последовательность, поддерживающая операции back, push_back и pop_back, может использоваться для

адаптации stack. В частности, могут использоваться vector, list и deque.
   template
   class stack {
    friend bool operator==(const stack& х,
const stack & y);
    friend bool operator<(const stack& х,
const stack & 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(); }

 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
   bool operator==(const stack & х,
const stack & y) {return х.с == у.с;}
   template
   bool operator<(const stack& х, const stack& y)
{return х.с < у.с;}
   Например, stack > - целочисленный стек, сделанный из vector, а stack > - символьный стек, сделанный из 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 #include #include #include using namespace std; int main( int

Пример

#include
#include
#include
#include
using namespace std;
int main(

int argc, char *argv[ ]) {
setlocale(LC_ALL, "rus");
stack st;
stack > vst( vector({ "строка 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. Поскольку стеки являются

stack::top

Возвращает ссылку на верхний элемент в stack.
Поскольку стеки являются контейнерами, входящими

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

Пример #include // std::cout #include // std::stack int main () {

Пример

#include // std::cout
#include // std::stack
int main () {
std::stack

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 и priority_queue: Здесь определяются шаблонные


Заголовок, определяющий классы адаптера контейнеров queue и priority_queue:
Здесь определяются шаблонные классы:
Очередь

: FIFO (first in, first out — «первым пришёл — первым ушёл») ) queue (class template )
Очередь с приоритетом : Priority queue (class template )
Слайд 35

Очередь (queue) Любая последовательность, поддерживающая операции front, push_back и pop_front, может

Очередь (queue)

   Любая последовательность, поддерживающая операции front, push_back и pop_front, может использоваться

для адаптации queue. В частности, могут использоваться list и deque.
В противоположность стеку очередь – это коллекция данных, функционирующая по принципу FIFO (First In — First Out). Она похожа на трубу, в один конец которой данные втекают, а из другого конца - вытекают.
   template
   class queue {
    friend bool operator== (const queue& х,
const queue& y);
    friend bool operator< (const queue& х,
const queue& 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()

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
   bool operator==(const queue& х, const queue& y)
{return х.с == у.с;}
    template
   bool operator<(const queue& х, const queue& y)
{return х.с < у.с;}
Слайд 37

Пример #include #include #include using namespace std; int main(int argc, char*

Пример

#include
#include
#include
using namespace std;
int main(int argc, char*

argv[ ]) {
setlocale(LC_ALL, "rus");
queue st;
queue > vst( list({ "строка 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 #include #include #include int main () { std::deque mydeck

Пример

#include
#include
#include
#include
int main ()

{
std::deque mydeck (3,100); // deque с 3 элементами
std::list mylist (2,200); // список с 2 элементами
std::queue first; // пустая queue
std::queue second (mydeck); // инициализируется копией deque
// пустая очередь со списком в
std::queue > third; // list - качестве базового контейнера
std::queue > 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
size of fourth: 2
Слайд 39

push и pop push вставляет новый элемент в конце очереди, после

push и pop

push вставляет новый элемент в конце очереди, после

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

Пример #include // std::cin, std::cout #include // std::queue int main ()

Пример

#include // std::cin, std::cout
#include // std::queue
int main () {

std::queue 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 ) Любая последовательность, с итератором произвольного доступа

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

   Любая последовательность, с итератором произвольного доступа и

поддерживающая операции front, push_back и pop_front, может использоваться для адаптера priority_queue. В частности, могут использоваться vector и deque.
   template >
   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

 public:
    priority_queue(const Compare& х = Compare()): c(), comp(х) { }
    template

>
    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 void make_heap (RandomAccessIterator first, RandomAccessIterator last); template void make_heap (RandomAccessIterator

template
void make_heap (RandomAccessIterator first, RandomAccessIterator last);
template

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 #include int main () { std::priority_queue mypq; mypq.push(10); mypq.push(20);

priority_queue::top

#include
#include
int main () {
std::priority_queue 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 #include #include int main () { std::priority_queue mypq; mypq.emplace("orange");

priority_queue::emplace

#include
#include
#include
int main () {
std::priority_queue

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 #include int main () { std::priority_queue foo,bar; foo.push (15);

priority_queue::swap

#include
#include
int main () {
std::priority_queue 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) на 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 и добавим туда код :

Теперь найдём в проекте файл myDLL.cpp и добавим туда код :
#include


#include
using namespace std;
template
std::string toString(T val) {
std::ostringstream oss;
oss << val;
return oss.str();
}
template
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 добавим в

Используем эту библиотеку в другом проекте.
В Visual Studio добавим в решение

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

Слайд 55

Слайд 56

Затем, прописываем путь путь к файлу 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

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

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

Слайд 60

ДЗ Проект 35. Попробовать создать решение (это потребуется для курсовой работы

ДЗ

Проект 35.
Попробовать создать решение (это потребуется для курсовой работы в следующем

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

Похожие презентации

Работа с браузером
Презентация "Чем может «заболеть» компьютер?" - скачать презентации по Информатике
Файлова система. Диски, файли, папки, ярлики
Аттестационная работа. Программа объединения дополнительного образования детей Ctrl+Alt+Delete
Потребление в Интернете: преимущества и вызовы
Задания по информатике. 4 класс
Создание Web-сайта
Своя игра. Компьютер
Презентация "Магистрально-модульный принцип построения компьютера" - скачать презентации по Информатике
Условный оператор
Протокол Totem
Язык рунета
Администрирование информационных систем Понятие групповой политики Использование групповых политик
Лекция №4 Информационные процессы и информационные системы как предмет изучения правовой информатики. Информатизация правот
Проект по деонтологии: проблемный клиент всезнайка, или проблема интернет-форумов
Презентация "Компьютер - это очень просто" - скачать презентации по Информатике
Frequently Used Linux Commands
Рекомендации по развитию и продвижению сайта Центра поддержки общественных инициатив г. Тольятти
Анализ и сравнение подходов к управлению сетями NGN
Презентация "Профессии, в которых необходимы знания по работе с базами данных" - скачать презентации по Информатике
Виды баз данных
Запоминающие устройства: классификация, принцип работы, основные характеристики
Как сделать прогулки ребенка в Интернете более безопасными
Александр Шаповал
Графический исполнитель робот. Ветвящиеся алгоритмы. Команды ветвления
Строки, регулярные выражения, локализация и интернационализация. Лекция 5
CryptoAP. Общее описание. Основные функции. Примеры использования
Управление вводом-выводом
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть