#include <map> #include <string> #include <utility>

void code fragment() {

multimap< string, string > authors;

...

string search item( Haruki Murakami );

while ( cin && cin >> search item ) switch ( authors.count( searc

( authors.count( search item ))

не

se С break;

найдено case С:

найден 1, обычный find() case 1: {

multimap< string, string >: iterator iter; iter = authors.find( search item );

обработка элемента . . . break;

найдено несколько ... default:

typedef multimap<string,string>::iterator iterator; pair< iterator, iterator > pos;

pos.first - адрес 1-го найденного pos.second - адрес 1-го отличного от найденного

pos = authors.ea1 range( search item ); for (; pos.first != pos.second; pos.first++ ) обработка элемента ...

Вставка и удаление элементов в multimap и multiset ничем не отличаются от аналогичных операций с контейнерами miap и set. Функция equal range() доставляет

#include <multimap> #include <string>

typedef multimap< string, string >::iterator iterator; pair< iterator, iterator > pos; string search item( Kazuo Ishiguro );

authors - multimap<string, string> эквивалентно

authors.erase( search item ); pos = authors.equa1 range( search item );

итераторную пару, задающую диапазон удаляемых элементов:

authors.erase( pos.first, pos.second );

При каждом вызове функции-члена 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 )));

Контейнер miultimiap не поддерживает операцию взятия индекса. Поэтому следующее выражение ошибочно:

authors[ Barth, John ]; ошибка: multimap Упражнение 6.28

Перепишите программу текстового поиска из раздела 6.14 с использованием miultimiap для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему?

6.16. Стек

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

#include <stack>

В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит в том, что доступ к элементу с вершины стека и удаление его осуществляются двумя функциями - top() и pop() . Полный набор операций со стеком приведен в таблице 6.5.

Таблица 6.5. Операции со стеком

#include <stack> #include <iostream> int main() {

const int ia size = 10;

int ia[ia size ]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

заполним стек int ix = 0;

stack< int > intStack; for ( ; ix < ia size; ++ix ) intStack.push( ia[ ix ] );

int error cnt = 0;

if ( intStack.size() != ia size ) {

cerr << ибка! неверн размер IntStack: << intStack.size()

<< \t ожидается: << ia size << endl, ++error cnt;

int value;

while ( intStack.empty() == false )

считаем элемент с вершины value = intStack.top(); if ( value != --ix ) {

cerr << ибка! ожидается << ix

<< получено << value << endl;

++error cnt; }

удалим элемент intStack.pop();

cout << В результате запуска программе! получено << error cnt << ошибок << endl;

В нашей программе приводятся примеры использования этих операций:

Объявление

stack< int > intStack;

определяет intStack как пустой стек, предназначенный для хранения элементов типа int. Стек является надстройкой над некоторым контейнерным типом, поскольку реализуется с помощью того или иного контейнера. По умолчанию это deque, поскольку именно эта структура обеспечивает эффективную вставку и удаление первого элемента, а vector эти операции не поддерживает. Однако мы можем явно указать другой тип контейнера, задав его как второй параметр: