Лекция 29. Введение в STL (часть 4) Красс Александр Alexander.Krass@gmail.com СПбГУ ИТМО, 2009. - презентация

1 Лекция 29. Введение в STL (часть 4) Красс Александр СПбГУ ИТМО, 2009

2 Темы priority_queue pair Ассоциативные контейнеры set multiset map multimap

3 priority_queue Очередь – последовательный контейнер, позволяющий добавлять элементы в конец и удалять их из начала Очередь с приоритетом – очередь в которой все элементы упорядочены в соответствии с неким приоритетом –Гарантируется что элемент на вершине очереди имеет наивысший приоритет

4 priority_queue (2) Находится в пространстве имен std Для его использования необходимо подключить файл queue Тип T должен или иметь оператор < или необходимо предоставлять предикат сравнения.

5 priority_queue (3) template,class Pred=less > class priority_queue { public: typedef Cont::value_type value_type; // Типы typedef Cont::size_type size_type; explicit priority_queue ( const Pred& pr = Pred() ); // Конструкторы template priority_queue (Iter first, Iter last, const Pred& pr = Pred()); bool empty() const; // Размеры size_type size () const; value_type& top(); // Работа с элементами const value_type& top() const; void push(const value_type& x); void pop(); protected: // Члены класса / реализация Cont c; Pred comp; };

6 priority_queue (4) Контейнер, на базе которого строится priority_queue должен определять следующие типы: 1.typedef... value_type; 2.typedef... size_type; И поддерживать следующие операции: 1. bool empty() const; 2.size_type size() const; 3. const value_type& front() const; 4.value_type& front(); 5. void push_back(const value_type& x); 6. void pop_back (); vector и deque этим требованиям полностью удовлетворяют.

7 priority_queue (5) Пример (красным цветом выделен результат операции top): priority_queue prq; prq.push(10); // 10 prq.push(1); // 10, 1 prq.push(7); // 10, 1, 7 prq.push(20); // 10, 1, 7, 20 prq.push(30); // 10, 1, 7, 20, 30 prq.push(0); // 10, 1, 7, 20, 30, 0 prq.pop(); // 10, 1, 7, 20, 0 prq.pop(); // 10, 1, 7, 0 prq.pop(); // 1, 7, 0 prq.pop(); // 1, 0 prq.pop(); // 0

8 pair Предоставляет обобщенную структуру из двух полей. Находится в пространстве имен std Для его использования вне map, set и пр. необходимо подключить файл utility. Объявление выглядит так: template struct pair { typedef T first_type; typedef U second_type; T first; U second; pair(); pair(const T& x, const U& y); template pair(const pair & pr); }; Есть вспомогательная функция, упрощающая создание экземпляров: template pair make_pair(const T& x,const U& y); Активно используется в классах set, multiset, map, multimap.

9 Ассоциативные контейнеры Основные характеристики: –Контейнеры переменного размера –Доступ к элементу по ключу произвольного типа –Поддерживает удаление и добавление элементов (по ключу) –Элементы упорядочены по ключу в соответствии с заданным критерием сортировки –Не поддерживается вставка элемента в произвольное место

10 Ассоциативные контейнеры (2) Общая структура: –Все АК определяют тип value_type в качестве типа своих элементов –Кроме того, каждый элемент в АК имеет ключ с типов key_type

11 Ассоциативные контейнеры (3) Реализация –АК обычно реализуются в виде сбалансированного бинарного дерева –Пара (Key, Value) сохраняется в дереве в соответствии с порядком сортировки Key Следствие –После добавления элемента в контейнер его ключ изменить нельзя! –АК не имеют изменяемых итераторов, выражение *I = v не поддерживается

12 Ассоциативные контейнеры (4) Классификация: –Простые АК – set, multiset –Составные АК – map, multimap Другая классификация: –Уникальные АК – set, map –Множественные АК – multiset, multimap

13 Ассоциативные контейнеры (5) Простые АК: –Элементы это и есть ключи –Типы value_type и key_type это по сути одно и тоже –Элементы в простых АК не изменяемы. –const_iterator это тоже самое что и просто iterator. Составные АК –Элементы состоят из пары key, value –Value изменяемо, Key нет. –const_iterator и iterator это разные типы

14 Ассоциативные контейнеры (6) Уникальные АК –Каждый элемент хранится в единственном экземпляре Множественные АК –Допускает хранение нескольких элементов с одним ключом

15 set Простой, уникальный АК Реализует понятие множества Находится в пространстве имен std Для его использования достаточно включить файл set Упрощенное определение: template < class Key, class Pred = less, class Alloc = allocator > class set { }; Key – тип элементов, хранящихся в множестве Pred – предикат сравнения элементов. По умолчанию, оператор < Alloc – определяет стратегию распределения памяти

16 set -типы set определяет следующие типы: // Для доступа к элементам typedef Key key_type; typedef Key value_type; // Переопределение предикатов typedef Pred key_compare; typedef Pred value_compare; // Определения итераторов и пр. typedef... allocator_type, size_type, difference_type, reference, const_reference, iterator, const_iterator,... Т.е., set определяет такой же набор типов как и остальные контейнеры.

17 set - конструкторы Set определяет следующие конструкторы: set ( const Pred& comp = Pred(), const Alloc& al = Alloc() ) – конструктор по умолчанию set ( const set& x ) – конструктор копирования template set( Iter first, Iter last, const Pred& comp = Pred(),const A& al = A()) – интервальный конструктор, позволяющий скопировать в множество интервал из любого контейнера Пример: std::list l; // заполнили l std::set s(l.begin(), l.end()); for (std::set ::const_iterator it = s.begin(); it != s.end(); it++) std::cout << *it; // в результате на экран выведутся только уникальные элементы списка l.

18 set - вставка Класс set содержит операцию вставки элемента в множество: pair insert(const value_type& x); Проверяет, существует ли элемент x в множестве. Элемент x равен y если !key_compare()(x,y) &&!key_compare()(y,x). Если не существует, то добавляет его в множество Получает итератор для этого элемента (или добавленного или существующего) Возвращает make_pair если элемент был создан, и make_pair если он уже существовал

19 set – вставка (2) Помимо обычного insert, set поддерживает еще две версии этой функции: –iterator insert(iterator it,const value_type& x) – вставляет элемент x в множество, используя it как подсказку, куда вставлять. Если подсказка не верна, используется обычный алгоритм. –template void insert(Iter first, Iter last) – вставляет все элементы из интервала [first; last)

20 set – вставка (3) Пример:

21 set - удаление set поддерживает операцию удаления элемента по ключу, итератору, а также группу элементов из заданного интервала: –size_type erase ( const Key& key ) – удаляет элемент по ключу. Возвращает кол'ичество удаленных элементов. (Для set это или 0 или 1) –void erase ( iterator it) – удаляет элемент, заданный итератором –void erase ( iterator first,iterator last ) – удаляет диапазон элементов [first; last)

22 set – удаление (2) Пример:

23 set - поиск set поддерживает операцию поиска элемента по ключу. const_iterator find (const Key& key) const – возвращает итератор, соответствующий переданному ключу. Пример:

24 multiset Простой, Множественный АК (несколько элементов multiset могут иметь одно и тоже значение) Находится в пространстве имен std Для его использования достаточно подключить файл set Поддерживает те же операции, что и set –insert возвращает не pair, просто iterator

25 multiset – доп. операции multiset реализует дополнительные операции: lower_bound, upper_bound, equal_range const_iterator lower_bound ( const Key& key ) const – возвращает итератор для первого элемента x, такого что key_compare()(x,key) = false. Если такого элемента нет, возвращает end() const_iterator upper_bound ( const Key& key ) const - – возвращает итератор для первого элемента x, такого что key_compare()(x,key) = true. Если такого элемента нет, возвращает end() pair equal_range(const Key& key) const – возвращает пару итераторов x и y, такую что: 1. x == lower_bound(key) 2. y == upper_bound(key)

26 multiset – доп. операции (2) Пример:

27 map Составной, уникальный АК, хранящий пару элементов pair. Первый элемент пары это ключ поиска, второй это значение Поддерживает эффективные операции удаления, вставки и поиска ПО КЛЮЧУ. При вставке элементов все итераторы остаются валидным. При удалении, все кроме удаляемого. Внутри map хранит свое содержимое в упорядоченном виде. Порядок задается ключом. Ключ каждого элемента обязан быть уникальным.

28 map - пример Пример – библиотечный каталог Каталог позволяет по ID книги получать информацию о том, где она лежит. Местоположение книги задается структурой: struct Location { unsigned Room; unsigned Case; unsigned Shelf; }; Тогда весь каталог можно будет хранить в map: std::map catalogue;

29 map – реализация Как правило, при реализации map используются сбалансированные деревья

30 map - определение map находится в пространстве имен std. Для его использования достаточно подключить файл map. namespace std { template, typename Allocator = allocator > > class map { }; } Key – ключ, уникальный для каждого элемента T – значение, хранящееся вместе с ключом. Pred – предикат сравнения, определенный для Key. По умолчанию, std::less Allocator – локатор для управления памятью

31 map – создание и уничтожение map содержит следующие конструкторы и деструктор: 1. explicit map ( const Pred& comp = Pred() const Allocator& al = Alloc()) – конструктор по умолчанию. 2. map ( const map& x ) – конструктор копирования 3. template map ( Iter first, Iter last, const Pred& comp =Pred(), const Allocator& al = Alloc()) – конструктор, позволяющий заполнить map частью другого map-а или массивом пар pair 4.~map() – деструктор Пример: typedef map Data; pair a[3] = { make_pair( 20,1.5), make_pair(800,0.3), make_pair( 3,0.2) }; Data res1; // empty map Data res2(a,a+3); // map is initialized by array Data res3(res2); // use res2 for initialization

32 map – общие свойства map поддерживает оператор присваивания, методы begin и end, а также оператор []: iterator begin(); const_iterator begin() const; iterator end(); iterator end() const; map & operator= (const map & x); T& operator[] ( const key_type& x );

33 map – общие свойства (2) Пример (доступ через []): map res1, res2; res1[0] = res2[1]; res2[100] = 0.7; res2[101] = res2[100]+0.1; Пример (доступ через итераторы) template void traverse ( RESULTS& res ) { RESULTS::iterator i; for ( i = res.begin(); i != res.end(); i++ ) if ( (*i).first < 20 ) Application((*i).second); }

34 map - вставка map поддерживает вставку как через оператор [], так и через метод insert: pair insert ( const value_type& x ); iterator insert ( iterator position, const value_type& x); template void insert ( Iter first, Iter last ); Пример: map res; res[100] = 0.2; // Здесь элемента с ключом 100 еще нет. res[100] = 0.3; // А здесь он уже есть, поэтому новый не создается res.insert(make_pair(100,0.3)); // и здесь так же

35 map – удаление и поиск map поддерживает операции удаления и поиска по ключу: iterator erase ( iterator it ); iterator erase ( iterator first, iterator last ); size_type erase ( const Key& key ); iterator find ( const key_type& x ); const_iterator find ( const key_type& x)const; Пример: RESULTS res; // заполнили RESULTS::iterator i1 = res.find( 7); // i1 указывает на RESULTS::iterator i2 = res.find(11); // i2 указывает на res.end() RESULTS::iterator i3 = res.find(15); // i3 указывает на res.erase(i1); //удалили элемент res.erase(15); // удалили элемент // Итераторы i1 и i3 стали невалидными!!!

36 map и multimap map и multimap очень похожи: –Один заголовочный файл –Большинство операций совпадает Но есть и различие: –multimap позволяет хранить несколько элементов с одним ключом –Другое поведение операции insert –Оператор[] не используется для вставки. –Поддерживаются операции lower_bound, upper_bound, equal_range. (семантика такая-же, как и у multiset)

37 37 Спасибо за внимание Вопросы?