При каждом вызове функции-члена 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 для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему?

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 эти операции не поддерживает. Однако мы можем явно указать другой тип контейнера, задав его как второй параметр:

stack< int, list<int> > intStack;

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

#include <stack>

class NurbSurface { /* mumble */ };

объекты. Например:

stack< NurbSurface* > surf_Stack;

К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.

Стек будет использован в нашей программе текстового поиска в разделе 17.7 для

поддержки сложных запросов типа

Civil && ( War || Rights )

6.17. Очередь и очередь с приоритетами

Абстракция очереди реализует метод доступа FIFO (first in, first out – “первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементы с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет. Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.

Для использования queue и priority_queue необходимо включить заголовочный файл:

#include <queue>

Полный набор операций с контейнерами queue и priority_queue приведен в таблице

6.6.

Таблица 6.6. Операции с queue и priority_queue

Элементы priority_queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции “меньше”, определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объект-функцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)

6.18. Вернемся в классу iStack

Укласса iStack, разработанного нами в разделе 4.15, два недостатка:

∙он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;

∙он имеет фиксированную длину. Это неудобно в двух отношениях: заполненный стек становится бесполезным, а в попытке избежать этого мы окажемся перед необходимостью отвести ему изначально слишком много памяти. Разумным выходом будет разрешить динамический рост стека. Это можно сделать, пользуясь тем, что лежащий в основе стека вектор способен динамически расти.

Напомним определение нашего класса iStack:

#include <vector>

class iStack { public:

iStack( int capacity )

: _stack( capacity ), _top( 0 ) {};

bool pop( int &value ); bool push( int value );

bool full(); bool empty(); void display();

int size();

private:

int _top;

vector< int > _stack;

};

Сначала реализуем динамическое выделение памяти. Тогда вместо использования

индекса при вставке и удалении элемента нам нужно будет применять соответствующие функции-члены. Член _top больше не нужен: функции push_back() и pop_back() автоматически работают в конце массива. Вот модифицированный текст функций pop()

bool iStack::pop( int &top_value )

{

if ( empty() ) return false;

top_value = _stack.back(); _stack.pop_back(); return true;

}

bool iStack::push( int value )

{

if ( full() ) return false;

_stack.push_back( value ); return true;

иpush():

}

Функции-члены empty(), size() и full() также нуждаются в изменении: в этой версии

inline bool iStack::empty(){ return _stack.empty(); } inline bool iStack::size() { return _stack.size(); } inline bool iStack::full() {

они теснее связаны с лежащим в основе стека вектором. return _stack.max_size() == _stack.size(); }

Надо немного изменить функцию-член display(), чтобы _top больше не фигурировал в качестве граничного условия цикла.

void iStack::display()

{

cout << "( " << size() << " )( bot: "; for ( int ix=0; ix < size(); ++ix )

cout << _stack[ ix ] << " "; cout << " stop )\n";

}

Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий от него теперь не требуется. Можно было бы определить пустой конструктор:

inline iStack::iStack() {}

Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет

class iStack { public:

iStack( int capacity = 0 ); // ...

выглядеть объявление конструктора с таким параметром типа int:

};

inline iStack::iStack( int capacity )

{

if ( capacity ) _stack.reserve( capacity );

Что делать с аргументом, если он задан? Используем его для указания емкости вектора:

}

Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе

#include <vector>

template <class elemType> class Stack {

public:

Stack( int capacity=0 ); bool pop( elemType &value ); bool push( elemType value );

bool full(); bool empty(); void display();

int size(); private:

vector< elemType > _stack;

вектор сам является шаблоном. Вот модифицированное объявление: