Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Контейнеры multimap и multiset
Контейнеры map и set не допускают повторяющихся значений ключей, а multimap (мультиотображение) и multiset (мультимножество) позволяют сохранять ключи с дублирующимися значениями. Например, в телефонном справочнике может понадобиться отдельный список номеров для каждого абонента. В перечне книг одного автора может быть несколько названий, а в нашей программе с одним словом текста сопоставляется несколько позиций. Для использования multimap и multiset нужно включить соответствующий заголовочный файл – map или set: #include < map> multimap< key_type, value_type > multimapName;
// ключ - string, значение - list< string > multimap< string, list< string > > synonyms;
#include < set> multiset< type > multisetName; Для прохода по мультиотображению или мультимножеству можно воспользоваться комбинацией итератора, который возвращает find() (он указывает на первый найденный элемент), и значения, которое возвращает count(). (Это работает, поскольку в данных контейнерах элементы с одинаковыми ключами обязательно являются соседними). Например: #include < map> #include < string>
void code_fragment() { multimap< string, string > authors; string search_item( " Alain de Botton" ); //... int number = authors.count( search_item ); mu1timap< string, string >:: iterator iter;
iter = authors.find( search_item ); for ( int cnt = 0; cnt < number; ++cnt, ++-iter ) do_something( *iter ); //... } Более элегантный способ перебрать все значения с одинаковыми ключами использует специальную функцию-член equal_range(), которая возвращает пару итераторов. Один из них указывает на первое найденное значение, а второй – на следующее за последним найденным. Если последний из найденных элементов является последним в контейнере, второй итератор содержит величину, равную end():
Вставка и удаление элементов в multimap и multiset ничем не отличаются от аналогичных операций с контейнерами map и set. Функция equal_range() доставляет итераторную пару, задающую диапазон удаляемых элементов:
При каждом вызове функции-члена insert() добавляется новый элемент, даже если в контейнере уже был элемент с таким же ключом. Например: typedef multimap< string, string>:: value_type valType; multimap< string, string> authors;
// первый элемент с ключом Barth authors.insert( valType ( string( " Barth, John" ), string( " Sot-Weed Factor" )));
// второй элемент с ключом Barth authors.insert( va1Type( string( " Barth, John" ), string( " Lost in the Funhouse" ))); Контейнер multimap не поддерживает операцию взятия индекса. Поэтому следующее выражение ошибочно: authors[ " Barth, John" ]; // ошибка: multimap Упражнение 6.28 Перепишите программу текстового поиска из раздела 6.14 с использованием multimap для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему? Стек В разделе 4.5 операции инкремента и декремента были проиллюстрированы на примере реализации абстракции стека. В общем случае стек является очень полезным механизмом для сохранения текущего состояния, если в разные моменты выполнения программы одновременно существует несколько состояний, вложенных друг в друга. Поскольку стек – это важная абстракция данных, в стандартной библиотеке С++ предусмотрен класс stack, для использования которого нужно включить заголовочный файл: #include < stack> В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит в том, что доступ к элементу с вершины стека и удаление его осуществляются двумя функциями – top() и pop(). Полный набор операций со стеком приведен в таблице 6.5. Таблица 6.5. Операции со стеком
В нашей программе приводятся примеры использования этих операций:
Объявление stack< int > intStack; определяет intStack как пустой стек, предназначенный для хранения элементов типа int. Стек является надстройкой над некоторым контейнерным типом, поскольку реализуется с помощью того или иного контейнера. По умолчанию это deque, поскольку именно эта структура обеспечивает эффективную вставку и удаление первого элемента, а vector эти операции не поддерживает. Однако мы можем явно указать другой тип контейнера, задав его как второй параметр: stack< int, list< int> > intStack; Элементы, добавляемые в стек, копируются в реализующий его контейнер. Это может приводить к потере эффективности для больших или сложных объектов, особенно если мы только читаем элементы. В таком случае удобнее определить стек указателей на объекты. Например: #include < stack> class NurbSurface { /* mumble */ }; stack< NurbSurface* > surf_Stack; К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом. Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа
Civil & & ( War || Rights )
|
Последнее изменение этой страницы: 2019-04-09; Просмотров: 397; Нарушение авторского права страницы