С++ для начинающих - Учебное пособие

6. абстрактные контейнерные типы

В этой главе мы продолжим рассмотрение типов данных, начатое в главе 3, представим   дополнительную   информацию   о   классах   vector и   string и познакомимся с другими контейнерными типами, входящими в состав стандартной библиотеки С++. Мы также расскажем об операторах и выражениях, упомянутых в главе 4, сосредоточив внимание на тех операциях, которые поддерживаются объектами контейнерных типов.

Последовательный контейнер содержит упорядоченный набор элементов одного типа. Можно  выделить  два  основных  типа  контейнеров –  вектор  (vector)  и  список (list). (Третий последовательный контейнер – двусторонняя очередь  (deque) – обеспечивает ту же  функциональность,   что  и  vector,  но  особенно  эффективно  реализует  операции вставки   и   удаления   первого   элемента.   deque следует   применять,   например,   при реализации очереди, из которой извлекается только первый элемент. Все сказанное ниже относительно вектора применимо также и к deque.)

Ассоциативный контейнер эффективно реализует операции проверки существования и извлечения  элемента.  Два  основных  ассоциативных  контейнера –  это  отображение (map) и   множество   (set).   map состоит   из   пар   ключ/значение,   причем   ключ используется для поиска элемента, а значение содержит хранимую информацию. Телефонный справочник хорошо иллюстрирует понятие отображения: ключом является фамилия и имя абонента, а значением – его телефонный номер.

Элемент  контейнера  set содержит  только  ключ,  поэтому  set эффективно  реализует операцию проверки его существования. Этот контейнер можно применить, например, при реализации системы текстового поиска для хранения списка так называемых стоп-слов – слов,  не  используемых  при  поиске,  таких,  как  и,  или,  не,  так  и  тому  подобных. Программа  обработки  текста  считывает  каждое  слово  и  проверяет,  есть  ли  оно  в указанном списке. Если нет, то слово добавляется в базу данных.

В  контейнерах  map и  set не  может  быть  дубликатов –  повторяющихся  ключей.  Для поддержки   дубликатов   существуют   контейнеры   multimap и   multiset.   Например, multimap можно  использовать  при  реализации  такого  телефонного  справочника,  в котором содержится несколько номеров одного абонента.

В последующих разделах мы детально рассмотрим контейнерные типы и разработаем небольшую программу текстового поиска.

6.1. Система текстового поиска

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

Если одно или несколько слов запроса найдены, печатается количество их вхождений. По желанию    пользователя    печатаются    предложения,    содержащие    найденные    слова.

 

Например,  если  нужно  найти  все  вхождения  словосочетаний  Civil War и  Civil

Rights, запрос может выглядеть таким образом9:

Civil && ( War || Rights )

Результат запроса:

Civil: 12 вхождений War: 48 вхождений Rights: 1 вхождение

Civil && War: 1 вхождение

Civil && Rights: 1 вхождение

(8) Civility, of course, is not to be confused with

Civil Rights, nor should it lead to Civil War

Здесь (8) представляет собой номер предложения в тексте. Наша система должна печатать фразы,  содержащие  найденные  слова,  в  порядке  возрастания  их  номеров  (т.е. предложение номер 7 будет напечатано раньше предложения номер 9), не повторяя одну и ту же несколько раз.

Наша программа должна уметь:

запросить имя текстового файла, а затем открыть и прочитать этот файл;

организовать внутреннее представление этого файла так, чтобы впоследствии соотнести найденное слово с предложением, в котором оно встретилось, и определить порядковый номер этого слова ;

понимать  определенный  язык  запросов.  В нашем  случае  он  включает следующие операторы:

&& два слова непосредственно следуют одно за другим в строке

|| одно или оба слова встречаются в строке

! слово не встречается в строке () группировка слов в запросе Используя этот язык, можно написать:

Lincoln

чтобы найти все предложения, включающие слово Lincoln, или

9 Замечание.  Для упрощения  программы мы требуем, чтобы каждое слово было отделено пробелом от скобок и логических операторов. Таким образом, запросы вида

(War || Rights)

Civil&&(War||Rights)

не будут поняты нашей системой. Хотя удобство пользователей не должно приноситься в жертву простоте реализации, мы считаем, что в данном случае можно смириться с таким ограничением.

 

! Lincoln

для поиска фраз, не содержащих такого слова, или же

( Abe || Abraham ) && Lincoln

для поиска тех предложений, где есть словосочетания Abe Lincoln или Abraham Lincoln.

Представим две версии нашей системы. В этой главе мы решим проблему чтения и хранения  текстового  файла  в отображении,  где ключом  является слово, а значением – номер строки и позиции в строке. Мы обеспечим поиск по одному слову. (В главе 17 мы реализуем  полную  систему  поиска,  поддерживающую  все указанные  выше операторы языка запросов с помощью класса Query.) .

Возьмем шесть строчек из неопубликованного детского рассказа Стена Липпмана (Stan

Lippman)10:

Рис. 2.

Alice Emma has long flowing red hair. Her Daddy says when the wind blows through her hair, it looks almost alive, like a fiery bird in flight. A beautiful fiery bird, he tells her, magical but untamed. "Daddy, shush, there is no such thing," she tells him, at the same time wanting him to tell her more. Shyly, she asks, "I mean. Daddy, is there?"

После  считывания  текста  его  внутреннее  представление  выглядит  так  (процесс считывания включает ввод очередной строки, разбиение ее на слова, исключение знаков препинания, замену прописных букв строчными, минимальная поддержка работы с суффиксами и исключение таких слов,  как and, a, the):

alice ((0,0)) alive ((1,10)) almost ((1,9)) ask ((5,2))

beautiful ((2,7)) bird ((2,3),(2,9)) blow ((1,3))

daddy ((0,8),(3,3),(5,5))

emma ((0,1))

fiery ((2,2),(2,8))

flight ((2,5))

flowing ((0,4))

hair ((0,6),(1,6))

has ((0,2))

like ((2,0)) long ((0,3)) look ((1,8)) magical ((3,0)) mean ((5,4)) more ((4,12)) red ((0,5))

same ((4,5))

say ((0,9))

she ((4,0),(5,1)) shush ((3,4)) shyly ((5,0))

such ((3,8))

tell ((2,11),(4,1),(4,10))

10 Иллюстрация  Елены Дрискилл (Elena Driskill).

 

there ((3,5),(5,7)) thing ((3,9)) through ((1,4))

time ((4,6)) untamed ((3,2)) wanting ((4,7)) wind ((1,2))

Ниже  приводится  пример  работы  программы,  которая  будет  реализована  в  данном разделе (то, что задает пользователь, выделено курсивом):

please enter file name: alice_emma

enter a word against which to search the text. to quit, enter a single character ==> alice

alice occurs 1 time:

( line 1 ) Alice Emma has long flowing red hair. Her Daddy says enter a word against which to search the text.

to quit, enter a single character ==> daddy

daddy occurs 3 times:

( line 1 ) Alice Emma has long flow-ing red hair. Her Daddy says

( line 4 ) magical but untamed. "Daddy, shush, there is no such thing,"

( line 6 ) Shyly, she asks, "I mean, Daddy, is there?"

enter a word against which to search the text. to quit, enter a single character ==> phoenix

Sorry. There are no entries for phoenix.

enter a word against which to search the text. to quit, enter a single character ==> .

Ok, bye!

Для того чтобы реализация была достаточно простой, необходимо детально рассмотреть стандартные контейнерные типы и тип string, представленный в главе 3.

6.2. Вектор или список?

Первая  задача,  которую  должна  решить  наша  программа, –  это считывание  из файла заранее   неизвестного   количества   слов.   Слова   хранятся   в   объектах   типа   string. Возникает вопрос: в каком контейнере мы будем хранить слова – в последовательном или ассоциативном?

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

Но  сначала   нам  нужно  просто  сохранить   слова  для  предварительной   обработки – исключения знаков препинания, суффиксов и т.п. Для этой цели последовательный контейнер подходит гораздо больше. Что же нам использовать: вектор или список?

Если вы уже писали программы на С или на С++ прежних версий, для вас, скорее всего, решающим фактором является возможность заранее узнать количество элементов. Если это  количество  известно  на  этапе  компиляции,  вы  используете  массив,  в  противном случае – список, выделяя память под очередной его элемент.

Однако  это  правило  неприменимо  к  стандартным  контейнерам:  и  vector,  и  deque

допускают динамическое изменение размера. Выбор одного из этих трех классов должен

 

зависеть от способов, с помощью которых элементы добавляются в контейнер и извлекаются из него.

Вектор представляет собой область памяти, где элементы хранятся друг за другом. Для этого типа произвольный доступ (возможность извлечь, например, элемент 5, затем 15, затем  7 и  т.д.)  можно  реализовать   очень  эффективно,   поскольку  каждый  из  них находится на некотором фиксированном расстоянии от начала. Однако вставка, кроме случая добавления в конец, крайне неэффективна: операция вставки в середину вектора потребует перемещения всего, что следует за вставляемым. Особенно это сказывается на больших  векторах.  (Класс  deque устроен  аналогично,   однако  операции   вставки  и удаления  самого  первого  элемента  работают  в  нем  быстрее;  это  достигается двухуровневым  представлением  контейнера,  при  котором  один  уровень  представляет собой реальное размещение элементов, а второй уровень адресует первый и последний из них.)

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

Вот некоторые критерии для выбора одного из последовательных контейнеров:

если требуется произвольный доступ к элементам, вектор предпочтительнее; если количество элементов известно заранее, также предпочтительнее вектор; если мы должны иметь возможность вставлять и удалять элементы в середину,

предпочтительнее список;

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

Как быть, если нам нужна возможность и произвольного доступа, и произвольного добавления/удаления элементов? Приходится выбирать: тратить время на поиск элемента или на его перемещение в случае вставки/удаления. В общем случае мы должны исходить из того, какую основную задачу решает приложение: поиск или добавление элементов? (Для  выбора  подхода  может  потребоваться  измерение  производительности  для  обоих типов  контейнеров.)  Если  ни один из стандартных  контейнеров  не удовлетворяет  нас, может быть, стоит разработать свою собственную, более сложную, структуру данных.

Какой из контейнеров выбрать, если мы не знаем количества его элементов (он будет динамически  расти)  и  у  нас  нет  необходимости  ни  в  произвольном  доступе,  ни  в добавлении элементов в середину? Что в таком случае более эффективно: список или вектор? (Мы отложим ответ на этот вопрос до следующего раздела.)

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

Внутреннее представление вектора и управление занимаемой им памятью более сложны.

Мы рассмотрим это в следующем разделе.

 

Упражнение 6.1

Что лучше выбрать в следующих примерах: вектор, список или двустороннюю очередь?

Или ни один из контейнеров не является предпочтительным?

1.   Неизвестное заранее количество слов считывается из файла для генерации случайных предложений.

2.   Считывается   известное   количество   слов,   которые   вставляются   в   контейнер   в алфавитном порядке.

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

4.   Считывается неизвестное количество целых чисел. Числа сортируются и печатаются.

6.3. Как растет вектор?

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

Вектор может запрашивать память не под каждый новый элемент. Вместо этого она запрашивается с некоторым запасом, так что после очередного выделения вектор может поместить в себя некоторое количество элементов, не обращаясь за ней снова. (Каков размер этого запаса, зависит от реализации.) На практике такое свойство вектора обеспечивает значительное увеличение его эффективности, особенно для небольших объектов.  Давайте  рассмотрим  некоторые  примеры  из  реализации  стандартной библиотеки С++ от компании Rogue Wave. Однако сначала определим разницу между размером и емкостью контейнера.

Емкость – это максимальное количество элементов,  которое может вместить контейнер без дополнительного выделения памяти. (Емкостью обладают только те контейнеры, в которых элементы хранятся в непрерывной области памяти, – vector, deque и string. Для  контейнера  list это  понятие  не  определено.)  Емкость  может  быть  получена  с помощью    функции    capacity().    Размер –    это    реальное    количество    элементов, хранящихся в данный момент в контейнере. Размер можно получить с помощью функции size(). Например:

 

#include <vector>

#include <iostream>

int main()

{

vector< int > ivec;

cout << "ivec: размер: " << ivec.size()

<< " емкость: " << ivec.capacity() << endl;

for ( int ix = 0; -ix < 24; ++ix ) {

ivec.push_back( ix );

cout << "ivec: размер: " << ivec.size()

<< " емкость: " << ivec.capacity() << endl;

}

}

В реализации Rogue Wave и размер, и емкость ivec сразу после определения равны 0. После  вставки  первого  элемента  размер  становится  равным  1,  а  емкость –  256.  Это значит, что до первого дополнительного выделения памяти в ivec можно вставить 256 элементов.  При  добавлении  256-го  элемента  вектор  должен  увеличиться:  выделить память объемом в два раза больше текущей емкости, скопировать в нее старые элементы и освободить прежнюю память. Обратите внимание: чем больше и сложнее тип данных элементов, тем менее эффективен вектор в сравнении со списком. В таблице 6.1 показана зависимость начальной емкости вектора от используемого типа данных.

Таблица 6.1. Размер и емкость для различных типов данных

 

Тип данных

Размер

в байтах

Емкость             после первой вставки

int double

простой класс #1

string

большой простой класс большой сложный класс

4

8

12

12

8000

8000

256

128

85

85

1

1

 

Итак, в реализации Rogue Wave при первой вставке выделяется точно или примерно 1024 байта. После каждого дополнительного выделения памяти емкость удваивается. Для типа данных, имеющего большой размер, емкость мала, и увеличение памяти с копированием старых элементов происходит часто, вызывая потерю эффективности. (Говоря о сложных классах, мы имеем в виду класс, обладающий копирующим конструктором и операцией присваивания.)  В  таблице  6.2  показано  время  в  секундах,  необходимое  для  вставки десяти миллионов элементов разного типа в список и в вектор. Таблица 6.3 показывает время, требуемое для вставки 10 000 элементов (вставка элементов большего размера оказалась слишком медленной).

Таблица 6.2. Время в секундах для вставки 10 000 000 элементов

 

Тип данных

List

Vector

int

10.38

3.76

 

 

double

10.72

3.95

простой класс

12.31

5.89

string

14.42

11.80

 

Таблица 6.3. Время в секундах для вставки 10 000 элементов

 

Тип данных

List

Vector

большой простой класс

0.36

2.23

большой сложный класс

2.37

6.70

 

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

Вставка   элемента   как   в   список,   так   и   в   вектор,   требует   вызова   копирующего конструктора,   если  он  определен.   (Копирующий  конструктор  инициализирует  один объект значением другого. В разделе 2.2 приводится начальная информация, а в разделе

14.5 о таких конструкторах рассказывается подробно). Это и объясняет различие в поведении  простых  и  сложных  объектов  при  вставке  в  контейнер.  Объекты  простого класса  вставляются  побитовым  копированием  (биты  одного  объекта  пересылаются  в биты другого), а для строк и сложных классов это производится вызовом копирующего конструктора.

Вектор должен вызывать их для каждого элемента при перераспределении памяти. Более того, освобождение памяти требует работы деструкторов для всех элементов (понятие деструктора  вводится в разделе 2.2). Чем чаще происходит перераспределение  памяти, тем больше времени  тратится  на эти дополнительные  вызовы конструкторов  и деструкторов.

Конечно,  одним  из решений  может быть  переход  от вектора  к списку, когда эффективность вектора становится слишком низкой. Другое, более предпочтительное решение состоит в том, чтобы хранить в векторе не объекты сложного класса, а указатели на них. Такая замена позволяет уменьшить затраты времени на 10 000 вставок с 6.70 секунд до 0.82 секунды. Почему? Емкость возросла с 1 до 256, что существенно снизило частоту перераспределения памяти. Кроме того, копирующий конструктор и деструктор не вызываются больше для каждого элемента при копировании прежнего содержимого вектора.

Функция   reserve() позволяет   программисту   явно   задать   емкость   контейнера11.

int main() {

vector< string > svec;

svec.reserve( 32 ); // задает емкость равной 32

// ...

Например:

11 Отметим, что deque не поддерживает  операцию reserve()

 

}

svec получает  емкость  32  при  размере  0.  Однако  эксперименты  показали,  что любое изменение начальной емкости для вектора, у которого она по умолчанию отлична от 1, ведет  к  снижению  производительности.   Так,  для  векторов  типа  string и  double увеличение емкости с помощью reserve() дало худшие показатели. С другой стороны, увеличение емкости для больших сложных типов дает значительный рост производительности, как показано в таблице 6.4.

Таблица 6.4. Время в секундах для вставки 10 000 элементов при различной емкости*

 

Емкость

Время в секундах

1 по умолчанию

4,096

8,192

10,000

670

555

444

222

*Сложный   класс  размером   8000   байт  с конструктором копирования и деструктором

 

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

Упражнение 6.2

Объясните разницу между размером и емкостью контейнера. Почему понятие емкости необходимо для контейнера, содержащего элементы в непрерывной области памяти, и не нужно для списка?

Упражнение 6.3

Почему большие сложные объекты удобнее хранить в контейнере в виде указателей на них, а для коллекции целых чисел применение указателей снижает эффективность?

Упражнение 6.4

Объясните,  какой  из  типов  контейнера –  вектор  или  список –  больше  подходит  для приведенных примеров (во всех случаях происходит вставка неизвестного заранее числа элементов):.

(a) Целые числа

(b) Указатели на большие сложные объекты

(c) Большие сложные объекты

6.4. Как определить последовательный контейнер?

Для того чтобы определить объект контейнерного типа, необходимо сначала включить соответствующий заголовочный файл:

 

#include <vector>

#inclnde <list>

#include <deque>

#include <map>

#include <set>

Определение  контейнера  начинается  именем  его типа,  за  которым  в  угловых  скобках

vector< string > svec;

следует тип данных его элементов12. Например:

list< int >         ilist;

Переменная  svec определяется как вектор, способный содержать элементы типа string,

а ilist – как список с элементами  типа int. Оба контейнера  при таком определении

if ( svec.empty() != true )

пусты. Чтобы убедиться в этом, можно вызвать функцию-член empty():

; // что-то не так

Простейший  метод  вставки  элементов –  использование  функции-члена  push_back(),

string text_word;

while ( cin >> text_word )

которая добавляет элементы в конец контейнера. Например:

svec.push_back( text_word );

Здесь  строки  из  стандартного  ввода  считываются  в  переменную  text_word,  и  затем копия каждой строки добавляется в контейнер svec с помощью push_back().

Список имеет  функцию-член  push_front(),  которая  добавляет  элемент  в его начало.

Пусть есть следующий массив:

int ia[ 4 ] = { 0, 1, 2, 3 };

12 Существующие  на сегодняшний  день реализации  не поддерживают  шаблоны с параметрами    по   умолчанию.    Второй   параметр –   allocator –   инкапсулирует    способы выделения   и  освобождения   памяти.  В  С++  он  имеет  значение  по  умолчанию,   и  его задавать не обязательно.  Стандартная  реализация использует операторы new и delete. Применение распределителя памяти преследует две цели: упростить реализацию контейнеров путем отделения всех деталей, касающихся работы с памятью, и позволить программисту при желании реализовать собственную стратегию выделения памяти. Определения объектов для компилятора, не поддерживающего значения по умолчанию параметров  шаблонов,   выглядят следующим образом:

vector< string, allocator > svec;

list< int, allocator >      ilist;

 

for ( int ix=0; ix<4; ++ix )

Использование push_back()

ilist.push_back( ia[ ix ] );

for ( int ix=0; ix<4; ++ix )

создаст последовательность 0, 1, 2, 3, а push_front()

ilist.push_front( ia[ ix ] );

создаст последовательность 3, 2, 1, 0. 13

Мы  можем  при  создании  явно  указать  размер  массива –  как  константным,  так  и

#include <list>

#include <vector>

#include <string>

extern int get_word_count( string file_name );

const int list_size = 64;

list< int > ilist( list_size );

неконстантным выражением:

vector< string > svec(get_word_count(string("Chimera")));

Каждый элемент контейнера инициализируется значением по умолчанию, соответствующим   типу  данных.  Для  int это  0.  Для  строкового  типа  вызывается конструктор по умолчанию класса string.

list< int > ilist( list_size, -1 );

Мы можем указать начальное значение всех элементов:

vector< string > svec( 24, "pooh" );

Разрешается  не  только  задавать  начальный  размер  контейнера,  но  и  впоследствии изменять его с помощью функции-члена resize(). Например:

svec.resize( 2 * svec.size() );

Размер svec в этом примере удваивается. Каждый новый элемент получает значение по умолчанию. Если мы хотим инициализировать его каким-то другим значением, то оно указывается вторым параметром функции-члена resize():

13 Если функция-член  push_front() используется  часто, следует применять  тип deque,

а не vector: в deque эта операция реализована наиболее эффективно.

 

// каждый новый элемент получает значение "piglet" svec.resize( 2 * svec.size(), "piglet" );

Кстати, какова наиболее вероятная емкость svec при определении, если его начальный размер равен 24? Правильно, 24! В общем случае минимальная емкость вектора равна его текущему размеру. При удвоении размера емкость, как правило, тоже удваивается

vector< string > svec2( svec );

Мы можем инициализировать новый контейнер с помощью существующего. Например:

list< int >         ilist2( ilist ) ;

Каждый контейнер поддерживает полный набор операций сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно. Сопоставляются попарно все элементы контейнера. Если они равны и размеры контейнеров одинаковы, то эти  контейнеры  равны; в противном случае – не равны. Результат операций  “больше” или  “меньше”  определяется  сравнением  первых  двух  неравных  элементов.  Вот  что печатает программа, сравнивающая пять векторов:

ivecl: 1 3 5 7 9 12 ivec2: 0 1 1 2 3 5 8 13 ivec3: 1 3 9

ivec4: 1 3 5 7 ivec5: 2 4

// первый неравный элемент: 1, О

// ivecl больше чем ivec2 ivecl < ivec2 //false ivec2 < ivecl //true

// первый неравный элемент: 5, 9 ivecl < ivec3 //true

// все элементы равны, но ivec4 содержит меньше элементов

// следовательно, ivec4 меньше, чем ivecl ivecl < ivec4 //false

// первый неравный элемент: 1, 2 ivecl < ivec5 //true

ivecl == ivecl //true ivecl == ivec4 //false ivecl != ivec4 //true

ivecl > ivec2 //true ivec3 > ivecl //true ivec5 > ivec2 //true

Существуют  три  ограничения  на тип  элементов  контейнера  (практически  это касается только пользовательских классов). Для должны быть определены:

операция “равно”;

операция    “меньше”    (все   операции    сравнения    контейнеров,    о   которых говорилось выше, используют только эти две операции сравнения);

значение  по  умолчанию  (для  класса  это  означает  наличие  конструктора  по умолчанию).

 

Все  предопределенные  типы  данных,  включая  указатели  и  классы  из  стандартной библиотеки С++ удовлетворяют этим требованиям.

Упражнение 6.5

#include <string>

#include <vector>

#include <iostream>

#int main()

{

vector<string> svec;

svec.reserve( 1024 );

string text_word;

while ( cin >> text_word )

svec.push_back( text_word );

svec.resize( svec.size()+svec.size()/2 );

// ...

Объясните, что делает данная программа:

}

Упражнение 6.6

Может ли емкость контейнера быть меньше его размера? Желательно ли, чтобы емкость была равна размеру: изначально или после вставки элемента? Почему?

Упражнение 6.7

Если программа  из упражнения 6.5 прочитает 256 слов, то какова наиболее вероятная емкость контейнера после изменения размера? А если она считает 512 слов? 1000? 1048?

Упражнение 6.8

Какие из данных классов не могут храниться в векторе:

 

(a) class cl1 {

public:

c11( int=0 );

bool operator==();

bool operator!=();

bool operator<=();

bool operator<();

// ...

};

(b) class c12 {

public:

c12( int=0 );

bool operator!=();

bool operator<=();

// ...

};

(с) class c13 {

public:

int ival;

};

(d) class c14 {

public:

c14( int, int=0 ); bool operator==(); bool operator!=();

// ...

}

6.5. Итераторы

Итератор  предоставляет  обобщенный  способ  перебора  элементов  любого контейнера – как  последовательного,  так  и  ассоциативного.  Пусть  iter является  итератором  для какого-либо контейнера. Тогда

++iter;

перемещает итератор так, что он указывает на следующий элемент контейнера, а

*iter;

разыменовывает итератор, возвращая элемент, на который он указывает.

Все контейнеры имеют функции-члены begin() и end().

begin() возвращает итератор, указывающий на первый элемент контейнера.

end() возвращает   итератор,   указывающий    на   элемент,   следующий   за последним в контейнере.

for ( iter = container. begin();

iter != container.end(); ++iter )

Чтобы перебрать все элементы контейнера, нужно написать:

 

do_something_with_element( *iter );

Объявление итератора выглядит  слишком сложным.  Вот определение пары итераторов

// vector<string> vec;

vector<string>::iterator iter = vec.begin();

вектора типа string:

vector<string>::iterator iter_end = vec.end();

В классе vector для определения  iterator используется typedef. Синтаксис

vector<string>::iterator

ссылается  на  iterator,   определенный  с  помощью   typedef внутри  класса  vector,

содержащего элементы типа string.

for( ; iter != iter_end; ++iter )

Для того чтобы напечатать все элементы вектора, нужно написать:

cout << *iter << ' ';

Здесь значением *iter выражения является, конечно, элемент вектора.

В дополнение к типу iterator в каждом контейнере определен  тип const_iterator,

который    необходим    для    навигации    по   контейнеру,    объявленному    как    const.

#include <vector>

void even_odd( const vector<int> *pvec, vector<int> *pvec_even,

vector<int> *pvec_odd )

{

// const_iterator необходим для навигации по pvec

vector<int>::const_iterator c_iter = pvec->begin();

vector<int>::const_1terator c_iter_end = pvec->end();

for ( ; c_iter != c_iter_end; ++c_iter )

if ( *c_iter \% 2 )

pvec_even->push_back( *c_iter );

else pvec_odd->push_back( *c_iter );

const_iterator позволяет только читать элементы контейнера:

}

Что делать, если мы хотим просмотреть   некоторое подмножество элементов, например взять каждый второй или третий элемент, или хотим начать с середины? Итераторы поддерживают адресную арифметику, а значит, мы можем прибавить некоторое число к итератору:

vector<int>::iterator iter = vec->begin()+vec.size()/2;

iter получает значение адреса элемента из середины вектора, а выражение

 

iter += 2;

сдвигает iter на два элемента.

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

ilist.begin() + 2;

так как для перемещения на два элемента необходимо два раза перейти по адресу, содержащемуся в закрытом члене next. У классов  vector и deque перемещение на два элемента  означает  прибавление  2  к указателю  на  текущий  элемент.  (Адресная арифметика рассматривается в разделе 3.3.)

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

#include <vector>

#include <string>

#include <iostream>

int main()

{

vector<string> svec;

string intext;

while ( cin >> intext )

svec.push_back( intext );

// обработать svec ...

копируемым.) Допустим, есть вектор:

}

Вот  как  можно  определить  новые  векторы,  инициализируя  их  элементами  первого

int main() {

vector<string> svec;

// ...

// инициализация svec2 всеми элементами svec vector<string> svec2( svec.begin(), svec.end() );

// инициализация svec3 первой половиной svec vector<string>::iterator it =

svec.begin() + svec.size()/2;

vector<string> svec3 ( svec.begin(), it );

// ...

вектора:

}

 

Использование специального типа istream_iterator (о нем рассказывается в разделе

#include <vector>

#include <string>

#include <iterator>

int mainQ

{

// привязка istream_iterator к стандартному вводу

istream_iterator<string> infile( cin );

// istream_iterator, отмечающий конец потока

istream_iterator<string> eos;

// инициализация svec элементами, считываемыми из cin;

vector<string> svec( infile, eos );

// ...

12.4.3) упрощает чтение элементов из входного потока в svec:

}

Кроме  итераторов,  для  задания  диапазона  значений,  инициализирующих  контейнер,

можно использовать два указателя на массив встроенного типа. Пусть есть следующий

#include <string>

string words[4] = {

"stately", "plump", "buck", "mulligan"

массив строк:

};

Мы можем инициализировать вектор с помощью указателей на первый элемент массива и на элемент, следующий за последним:

vector< string > vwords( words, words+4 );

Второй указатель служит “стражем”: элемент, на который он указывает, не копируется.

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

Аналогичным образом можно инициализировать список целых элементов:

list< int > ilist( ia, ia+6 );

В разделе 12.4 мы снова обратимся к итераторам и опишем их более детально. Сейчас информации достаточно для того, чтобы использовать итераторы в нашей системе текстового  поиска.  Но  прежде  чем  вернуться  к  ней,  рассмотрим  некоторые дополнительные операции, поддерживаемые контейнерами.

Упражнение 6.9

Какие ошибки допущены при использовании итераторов:

 

const vector< int > ivec; vector< string >       svec; list< int >            ilist;

(a) vector<int>::iterator it = ivec.begin();

(b) list<int>::iterator    it = ilist.begin()+2; (c) vector<string>::iterator it = &svec[0];

(d) for ( vector<string>::iterator

it = svec.begin(); it != 0; ++it )

// ...

Упражнение 6.10

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

string sa[6] = {

"Fort Sumter", "Manassas", "Perryville", "Vicksburg",

"Meridian", "Chancellorsvine" };

(a) vector<string> svec( sa, &sa[6] ); (b) list<int> ilist( ia+4, ia+6 );

(c) list<int> ilist2( ilist.begin(), ilist.begin()+2 ); (d) vector<int> ivec( &ia[0], ia+8 );

(e) list<string> slist( sa+6, sa );

Найдите ошибки в использовании итераторов:

(f) vector<string> svec2( sa, sa+6 );

6.6. Операции с последовательными контейнерами

Функция-член   push_back() позволяет   добавить   единственный   элемент   в   конец контейнера. Но как вставить элемент в произвольную позицию? А целую последовательность элементов? Для этих случаев существуют более общие операции.

vector< string > svec; list< string > slist; string spouse( "Beth" );

slist.insert( slist.begin(), spouse );

Например, для вставки элемента в начало контейнера можно использовать:

svec.insert( svec.begin(), spouse );

Первый параметр функции-члена  insert() (итератор, адресующий некоторый элемент контейнера)  задает позицию,  а второй – вставляемое перед этой позицией значение. В примере  выше  элемент  добавляется  в  начало  контейнера.  А  так  можно  реализовать вставку в произвольную позицию:

 

string son( "Danny" );

list<string>::iterator iter;

iter = find( slist.begin(), slist.end(), son );

slist.insert( iter, spouse );

Здесь find() возвращает  позицию  элемента  в контейнере,  если элемент  найден, либо итератор  end(),  если  ничего  не  найдено.  (Мы  вернемся  к  функции  find() в  конце следующего  раздела.)  Как  можно  догадаться,  push_back() эквивалентен  следующей

// эквивалентный вызов: slist.push_back( value );

записи:

slist.insert( slist.end(), value );

Вторая   форма   функции-члена   insert() позволяет   вставить   указанное   количество одинаковых  элементов,  начиная  с  определенной  позиции.  Например,  если  мы  хотим

vector<string> svec;

string anna( "Anna" );

добавить десять элементов Anna в начало вектора, то должны написать:

svec.insert( svec.begin(), 10, anna );

insert() имеет   и   третью   форму,   помогающую   вставить   в   контейнер   несколько элементов. Допустим, имеется следующий массив:

string sarray[4] = { "quasi", "simba", "frollo", "scar" };

Мы  можем  добавить  все его элементы  или  только  некоторый  диапазон  в наш вектор

svec.insert( svec.begin(), sarray, sarray+4 );

svec.insert( svec.begin() + svec.size()/2,

 

 

строк:

sarray+2, sarray+4 );

 

 

// вставляем элементы svec

// в середину svec_two

svec_two.insert( svec_two.begin() + svec_two.size()/2,

Такой диапазон отмечается и с помощью пары итераторов

svec.begin(), svec.end() );

 

list< string > slist;

// ...

// вставляем элементы svec

// перед элементом, содержащим stringVal

list< string >::iterator iter =

find( slist.begin(), slist.end(), stringVal );

или любого контейнера, содержащего строки:14

slist.insert( iter, svec.begin(), svec.end() );

6.6.1. Удаление

В  общем  случае  удаление  осуществляется  двумя  формами  функции-члена  erase(). Первая  форма  удаляет  единственный  элемент,  вторая –  диапазон,  отмеченный  парой итераторов. Для последнего элемента можно воспользоваться функцией-членом pop_back().

При вызове erase() параметром является итератор, указывающий на нужный элемент.

В следующем  фрагменте кода мы воспользуемся  обобщенным  алгоритмом  find() для

string searchValue( "Quasimodo" );

list< string >::iterator iter =

find( slist.begin(), slist.end(), searchValue );

if ( iter != slist.end() )

нахождения элемента и, если он найден, передадим его адрес функции-члену erase().

slist.erase( iter );

Для  удаления  всех  элементов  контейнера  или  некоторого  диапазона  можно  написать

// удаляем все элементы контейнера

slist.erase( slist.begin(), slist.end() );

// удаляем элементы, помеченные итераторами

list< string >::iterator first, last;

first = find( slist. begin(), slist.end(), vail );

last = find( slist.begin(), slist.end(), va12 );

// ... проверка first и last

следующее:

slist.erase( first, last );

14   Последняя   форма   insert() требует,   чтобы   компилятор   работал   с   шаблонами функций-членов. Если ваш компилятор еще не поддерживает это свойство стандарта С++, то оба контейнера должны быть одного типа, например два списка или два вектора, содержащих элементы одного типа.

 

Парной по отношению к push_back() является функция-член pop_back(), удаляющая

vector< string >::iterator iter = buffer.begin();

for ( ; iter != buffer.end(), iter++ )

{

slist.push_back( *iter );

if ( ! do_something( slist ))

slist.pop_back();

из контейнера последний элемент, не возвращая его значения:

}

6.6.2. Присваивание и обмен

Что происходит, если мы присваиваем один контейнер другому? Оператор присваивания копирует элементы из контейнера, стоящего справа, в контейнер, стоящий слева от знака

// svecl содержит 10 элементов

// svec2 содержит 24 элемента

// после присваивания оба содержат по 24 элемента

равенства. А если эти контейнеры имеют разный размер? Например:

svecl = svec2;

Контейнер-адресат (svec1) теперь содержит столько же элементов, сколько контейнер- источник (svec2). 10 элементов, изначально содержавшихся в svec1, удаляются (для каждого из них вызывается деструктор класса string).

Функция  обмена  swap() может  рассматриваться  как  дополнение  к  операции присваивания. Когда мы пишем:

svecl.swap( svec2 );

svec1 после вызова функции содержит 24 элемента, которые он получил бы в результате присваивания:

svecl = svec2;

но зато теперь svec2 получает 10 элементов, ранее находившихся в svec1. Контейнеры

“обмениваются” своим содержимым.

6.6.3. Обобщенные алгоритмы

Операции, описанные в предыдущих разделах, составляют набор, поддерживаемый непосредственно контейнерами vector и deque. Согласитесь, что это весьма небогатый интерфейс  и  ему явно  не хватает  базовых  операций  find(),  sort(),  merge() и  т.д. Планировалось вынести общие для всех контейнеров операции в набор обобщенных алгоритмов,   которые  могут  применяться   ко  всем  контейнерным  типам,  а  также  к массивам встроенных типов. (Обобщенные алгоритмы описываются в главе 12 и в Приложении.)   Эти   алгоритмы   связываются   с   определенным   типом   контейнера   с

 

помощью передачи им в качестве параметров пары соответствующих итераторов. Вот как

#include <list>

#include <vector>

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

vector<string> svec;

list<double> dtist;

// соответствующий заголовочный файл

#include <algorithm>

vector<string>::iterator viter;

list<double>::iterator liter;

#int *pia;

// find() возвращает итератор на найденный элемент

// для массива возвращается указатель ...

pia =    find( &ia[0], &ia[6], some_int_value );

liter = find( dlist.begin(), dlist.end(), some_double_value );

выглядят вызовы алгоритма find() для списка, вектора и массива разных типов:

viter = find( svec.begin(), svec.end(), some_string_value );

Контейнер list поддерживает дополнительные операции, такие, как sort() и merge(), поскольку  в  нем  не  реализован  произвольный  доступ  к  элементам.  (Эти  операции описаны в разделе 12.6.)

Теперь вернемся к нашей поисковой системе.

Упражнение 6.11

int ia[] = { 1, 5, 34 };

int ia2[] = { 1, 2, 3 };

int ia3[] = { 6, 13, 21, 29, 38, 55, 67, 89 };

Напишите программу, в которой определены следующие объекты:

vector<int> ivec;

Используя  различные  операции   вставки  и  подходящие  значения  ia, ia2 и  ia3,

модифицируйте вектор ivec так, чтобы он содержал последовательность:

{  0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 }

Упражнение 6.12

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };

Напишите программу, определяющую данные объекты:

list<int> ilist( ia, ia+11 );

Используя функцию-член erase() с одним параметром, удалите из ilist все нечетные элементы.

 

6.7. Читаем текстовый файл

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

Как  получить  одну  строку  текста?  Стандартная  библиотека  предоставляет  для  этого

istream&

функцию getline():

getline( istream &is, string str, char delimiter );

getline()берет  из входного потока все символы,  включая пробелы,  и помещает их в объект типа string, до тех пор пока не встретится символ delimiter, не будет достигнут конец файла или количество полученных символов не станет равным величине, возвращаемой функцией-членом max_size()класса string.

Мы будем помещать каждую такую строку в вектор.

Мы вынесли код, читающий файл, в функцию, названную retrieve_text(). В объекте типа pair дополнительно сохраняется размер и номер самой длинной строки. (Полный текст программы приводится в разделе 6.14.)

Вот реализация функции ввода файла:15

15        Программа   компилировалась        компилятором,          не    поддерживающим         значений параметров по умолчанию шаблонов. Поэтому нам пришлось явно указать аллокатор:

vector<string,allocator> *lines_of_text;

Для  компилятора,  полностью  соответствующего  стандарту  С++,  достаточно отметить тип элементов:

vector<string> *lines_of_text;

 

// возвращаемое значение - указатель на строковый вектор

vector<string,allocator>*

retrieve_text()

{

string file_name;

cout << "please enter file name: ";

cin >> file_name;

// откроем файл для ввода ...

ifstream 1nfile( file_name.c_str(), ios::in );

if ( ! infile ) {

cerr << "oops! unable to open file "

<< file_name << " -- bailing out! ";

exit( -1 );

}

else cout << ' ';

vector<string, allocator> *1ines_of_text =

new vector<string, allocator>;

string textime;

typedef pair<string::size_type, int> stats;

stats maxline;

int        linenum = 0;

while ( getline( infile, textline, ' ' )) {

cout << "line read: " << textline << ' ';

if ( maxline.first < textline.size() ) { maxline.first = textline.size() ; maxline.second = linenum;

}

1ines_of_text->push_back( textline );

linenum++;

}

return lines_of_text;

}

Вот как выглядит вывод программы (размер страницы книги недостаточен, чтобы расположить напечатанные строки во всю длину, поэтому мы сделали в тексте отступы, показывающие, где реально заканчивалась строка):

please enter file name: a1ice_emma

line read: Alice Emma has long flowing red hair. Her Daddy says line read: when the wind blows through her hair, it looks

almost alive,

line read: like a fiery bird in flight. A beautiful fiery bird,

he tells her,

line read: magical but untamed. "Daddy, shush, there is no such

thing, "

line read: she tells him, at the same time wanting him to tell

her more.

line read: Shyly, she asks, "I mean. Daddy, is there?"

number of lines: 6 maximum length: 66

longest line: like a fiery bird in flight. A beautiful fiery bird, he tells her,

 

После того как все строки текста сохранены, нужно разбить их на слова. Сначала мы отбросим знаки препинания. Например, возьмем строку из части “Anna Livia Plurrabelle” романа “Finnegans Wake”.

"For every tale there's a telling, and that's the he and she of it."

В приведенном фрагменте есть следующие знаки препинания:

"For there's telling, that's it."

А хотелось бы получить:

For there telling that

it

Можно возразить, что

there's

должно превратиться в

there is

но   мы-то   движемся   в   другом   направлении:   следующий   шаг –   это   отбрасывание семантически  нейтральных  слов,  таких,  как is,  that, and,  it и т.д. Так что для данной строчки  из  “Finnegans  Wake”  только  два  слова  являются  значимыми:  tale и  telling,  и только по этим словам будет выполняться поиск. (Мы реализуем набор стоп-слов с помощью контейнерного типа set, который подробно рассматривается в следующем разделе.)

После удаления знаков препинания нам необходимо превратить все прописные буквы в строчные, чтобы избежать проблем с поиском в таких, например, строках:

Home is where the heart is.

A home is where they have to let you in.

Несомненно, запрос слова home должен найти обе строки.

Мы должны также обеспечить минимальную поддержку учета словоформ: отбрасывать окончания слов, чтобы слова dog и dogs, love, loving и loved рассматривались системой как одинаковые.

 

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

6.8. Выделяем слова в строке

Нашей первой задачей является разбиение строки на слова. Мы будем вычленять слова,

находя разделяющие их пробелы с помощью функции find(). Например, в строке

Alice Emma has long flowing red hair.

насчитывается шесть пробелов, следовательно, эта строка содержит семь слов.

Класс string имеет несколько функций поиска. find() – наиболее простая из них. Она ищет  образец,  заданный  как  параметр,  и  возвращает  позицию  его первого  символа  в строке, если он найден, или специальное значение string::npos в противном случае.

#include <string>

#include <iostream>

int main() {

string name( "AnnaBelle" );

int pos = name.find( "Anna" );

if ( pos == string::npos )

cout << "Anna не найдено! ";

else cout << "Anna найдено в позиции: " << pos << endl;

Например:

}

Хотя позиция подстроки почти всегда имеет тип int, более правильное и переносимое объявление типа результата, возвращаемого find(), таково:

string::size_type

Например:

string::size_type pos = name.find( "Anna" );

Функция  find() делает  не  совсем  то,  что  нам  надо.  Требуемая  функциональность обеспечивается функцией find_first_of(), которая возвращает позицию первого символа,  соответствующего  одному  из  заданных  в  строке-параметре.  Вот  как  найти первый символ, являющийся цифрой:

 

#include <string>

#include <iostream>

int main() {

string numerics( "0123456789" );

string name( "r2d2" );

string:: size_type pos = name.find_first_of( numerics );

cout << "найдена цифра в позиции: "

<< pos             << " элемент равен "

<< name[pos] << endl;

}

В этом примере pos получает значение 1 (напоминаем, что символы строки нумеруются с

0).

Но нам нужно найти все вхождения символа, а не только первое. Такая возможность реализуется  передачей  функции  find_first_of() второго  параметра,  указывающего позицию, с которой начать поиск. Изменим предыдущий пример. Можете ли вы сказать,

#include <string>

#include <iostream>

int main() {

string numerics( "0123456789" );

string name( "r2d2" );

string::size_type pos = 0;

// где-то здесь ошибка!

while (( pos = name.find_first_of( numerics, pos ))

!= string::npos )

cout << "найдена цифра в позиции: "

<< pos             << " элемент равен "

<< name[pos] << endl;

что в нем все еще не вполне удовлетворительно?

}

В начале цикла  pos равно 0, поэтому поиск идет с начала строки. Первое вхождение обнаружено в позиции 1. Поскольку найденное значение не совпадает с string::npos, выполнение  цикла  продолжается.  Для  второго  вызова  find_first_of()значение  pos равно 1. Поиск начнется с 1-й позиции. Вот ошибка! Функция find_first_of() снова найдет цифру в первой позиции, и снова, и снова... Получился бесконечный цикл. Нам необходимо увеличивать pos на 1 в конце каждой итерации:

 

// исправленная версия цикла

while (( pos = name.find_first_of( numerics, pos ))

!= string::npos )

{

cout << "найдена цифра в позиции: "

<< pos             << " элемент равен "

<< name[pos] << endl;

// сдвинуться на 1 символ

++pos;

}

Чтобы найти все пустые символы (к которым, помимо пробела, относятся символы табуляции и перевода строки), нужно заменить строку numerics в этом примере строкой, содержащей  все эти  символы.  Если  же мы  уверены,  что используется  только  символ

// фрагмент программы

while (( pos = textline.find_first_of( ' ', pos ))

!= string::npos )

пробела и никаких других, то можем явно задать его в качестве параметра функции:

// ...

// фрагмент программы

// pos: позиция на 1 большая конца слова

// prev_pos: позиция начала слова

string::size_type pos = 0, prev_pos = 0;

while (( pos = textline.find_first_of( ' ', pos ))

!= string::npos )

{

// ...

// запомнить позицию начала слова

prev_pos = ++pos;

Чтобы узнать длину слова, введем еще одну переменную:

}

На  каждой  итерации  prev_pos указывает  позицию  начала  слова,  а  pos –  позицию следующего символа после его конца. Соответственно, длина слова равна:

pos - prev_pos; // длина слова

После того как мы выделили слово, необходимо поместить его в строковый вектор. Это можно сделать, копируя в цикле символы из textline с позиции prev_pos до pos -1. Функция substr() сделает это за нас:

 

// фрагмент программы

vector<string> words;

while (( pos = textline.find_first_of( ' ', pos ))

!= string::npos )

{

words.push_back( textline.substr(

prev_pos, pos-prev_pos));

prev_pos = ++pos;

}

Функция substr() возвращает копию подстроки. Первый ее аргумент обозначает первую позицию, второй – длину подстроки. (Второй аргумент можно опустить, тогда подстрока включит в себя остаток исходной строки, начиная с указанной позиции.)

В нашей реализации допущена ошибка: последнее слово не будет помещено в контейнер.

Почему? Возьмем строку:

seaspawn and seawrack

После каждого из первых двух слов поставлен пробел. Два вызова функции find_first_of() вернут  позиции  этих  пробелов.  Третий  же  вызов  вернет string::npos, и цикл закончится. Таким образом, последнее слово останется необработанным.

Вот  полный  текст  функции,  названной  нами  separate_words().  Помимо  сохранения слов в векторе строк, она вычисляет координаты каждого слова – номер строки и колонки (нам эта информация потребуется впоследствии).

 

typedef pair<short,short> location; typedef vector<location>  loc; typedef vector<string>             text; typedef pair<text* ,loc*> text_loc;

text_loc*

separate_words( const vector<string> *text_file )

{

// words: содержит набор слов

// locations: содержит информацию о строке и позиции

// каждого слова

vector<string> *words = new vector<string>;

vector<location> * locations = new vector<location>;

short line_pos = 0; // текущий номер строки

// iterate through each line of text

for ( ; line_pos < text_file->size(); ++line_pos )

// textline: обрабатываемая строка

// word_pos: позиция в строке

short word_pos = 0;

string textline = (*text_file) [ line_pos ];

string::size_type pos = 0, prev_pos = 0;

while (( pos = textline.find_first_of( ' ', pos ))

!= string::npos )

{

// сохраним слово

words->push_back(

textline.substr( prev_pos, pos - prev_pos ));

// сохраним информацию о его строке и позиции

locations->push_back(

make_pair( line_pos, word_pos ));

// сместим позицию для следующей итерации

++word_pos; prev_pos = ++pos;

}

// обработаем последнее слово

words->push_back(

textline.substr( prev_pos, pos - prev_pos ));

locations->push_back(

make_pair( line_pos, word_pos ));

}

return new text_loc( words, locations );

}

int main()

{

vector<string> *text_file = retrieve_text();

text_loc *text_locations = separate_words( text_file );

// ...

Теперь функция main()выглядит следующим образом:

}

 

Вот часть распечатки, выданной тестовой версией separate_words():

textline: Alice Emma has long flowing red hair. Her Daddy says

eol: 52 pos: 5 line: 0 word: 0 substring: Alice eol: 52 pos: 10 line: 0 word: 1 substring: Emma eol: 52 pos: 14 line: 0 word: 2 substring: has eol: 52 pos: 19 line: 0 word: 3 substring: long

eol: 52 pos: 27 line: 0 word: 4 substring: flowing

eol: 52 pos: 31 line: 0 word: 5 substring: red

eol: 52 pos: 37 line: 0 word: 6 substring: hair.

eol: 52 pos: 41 line: 0 word: 7 substring: Her

eol: 52 pos: 47 line: 0 word: 8 substring: Daddy

last word on line substring: says

...

textline: magical but untamed. "Daddy, shush, there is no such thing,"

eol: 60 pos: 7 line: 3 word: 0 substring: magical eol: 60 pos: 11 line: 3 word: 1 substring: but

eol: 60 pos: 20 line: 3 word: 2 substring: untamed eol: 60 pos: 28 line: 3 word: 3 substring: "Daddy, eol: 60 pos: 35 line: 3 word: 4 substring: shush, eol: 60 pos: 41 line: 3 word: 5 substring: there eol: 60 pos: 44 line: 3 word: 6 substring: is

eol: 60 pos: 47 line: 3 word: 7 substring: no

eol: 60 pos: 52 line: 3 word: 8 substring: such

last word on line substring: thing,":

...

textline: Shy1y, she asks, "I mean, Daddy: is there?" eol: 43 pos: 6 line: 5 word: 0 substring: Shyly,

eol: 43 pos: 10 line: 5 word: 1 substring: she

eol: 43 pos: 16 line: 5 word: 2 substring: asks,

eol: 43 pos: 19 line: 5 word: 3 substring: "I

eol: 43 pos: 25 line: 5 word: 4 substring: mean, eol: 43 pos: 32 line: 5 word: 5 substring: Daddy, eol: 43 pos: 35 line: 5 word: 6 substring: is

last word on line substring: there?":

Прежде    чем    продолжить    реализацию    поисковой    системы,    вкратце   рассмотрим оставшиеся   функции-члены   класса  string,  предназначенные  для  поиска.  Функция

string river( "Mississippi" );

string::size_type first_pos = river.find( "is" );

rfind() ищет последнее, т.е. самое правое, вхождение указанной подстроки:

string::size_type 1ast_pos = river.rfind( "is" );

find() вернет 1, указывая позицию первого вхождения подстроки "is", а rfind() – 4

(позиция последнего вхождения "is").

find_first_not_of() ищет первый символ, не содержащийся в строке, переданной как параметр. Например, чтобы найти первый символ, не являющийся цифрой, можно написать:

 

string elems( "0123456789" );

string dept_code( "03714p3" );

// возвращается позиция символа 'p'

string::size_type pos = dept_code.find_first_not_of(elems) ;

find_last_of() ищет  последнее  вхождение  одного  из  указанных  символов. find_last_not_of() – последний символ, не совпадающий ни с одним из заданных. Все эти  функции  имеют второй  необязательный  параметр – позицию в исходной  строке, с которой начинается поиск.

Упражнение 6.13

Напишите программу, которая ищет в строке

"ab2c3d7R4E6"

цифры,           а          затем   буквы,            используя       сначала           find_first_of(),            а          потом

find_first_not_of().

Упражнение 6.14

Напишите программу,  которая  подсчитывает  все слова  и определяет  самое длинное и

string linel = "We were her pride of 10 she named us --";

string line2 = "Benjamin, Phoenix, the Prodigal"

string line3 = "and perspicacious pacific Suzanne";

самое короткое из них в строке sentence:

string sentence = linel + line2 + line3;

Если несколько слов имеют длину, равную максимальной или минимальной, учтите их все.

6.9. Обрабатываем знаки препинания

После того как мы разбили каждую строку на слова, необходимо избавиться от знаков препинания. Пока из строки

magical but untamed. "Daddy, shush, there is no such thing,"

у нас получился такой набор слов:

magical but untamed. "Daddy, shush, there

is no

 

such thing,"

Как  нам  теперь  удалить  ненужные знаки  препинания?  Для  начала  определим  строку,

содержащую все символы, которые мы хотим удалить:

string filt_elems( "\",.;:!?)(\/" );

(Обратная косая черта указывает на то, что следующий за ней символ должен в данном контексте восприниматься буквально, а не как специальная величина. Так, \" обозначает символ двойной кавычки, а не конец строки, а \ – символ обратной косой черты.)

Теперь можно применить функцию-член find_first_of() для поиска всех вхождений

while (( pos = word.find_first_of( filt_elems, pos ))

нежелательных символов:

!= string::npos )

Найденный символ удаляется с помощью функции-члена erase():

word.erase(pos,1);

Первый аргумент этой функции означает позицию подстроки, а второй – ее длину. Мы удаляем один символ, находящийся в позиции pos. Второй аргумент является необязательным; если его опустить, будут удалены все символы от pos до конца строки.

Вот  полный  текст  функции  filter_text().  Она  имеет  два  параметра:  указатель  на

void

filter_text( vector<string> *words, string filter )

{

vector<string>::iterator iter = words->begin();

vector<string>::iterator iter_end = words->end();

// Если filter не задан, зададим его сами

if ( ! filter.size() )

filter.insert( 0, "\".," );

while ( iter != iter_end ) {

string::size_type pos = 0;

// удалим каждый найденный элемент

while (( pos = (*iter).find_first_of( filter, pos ))

!= string::npos ) (*iter).erase(pos,1);

iter++;

}

вектор строк, содержащий текст, и строку с символами, которые нужно убрать.

}

Почему мы не увеличиваем значение pos на каждой итерации? Что было бы, если бы мы написали:

 

while (( pos = (*iter).find_first_of( filter, pos ))

!= string::npos )

{

(*iter).erase(pos,1);

++ pos; // неправильно...

}

Возьмем строку

thing,"

На первой итерации pos получит значение 5 , т.е. позиции, в которой находится запятая.

После удаления запятой строка примет вид

thing"

Теперь  в  5-й  позиции  стоит  двойная  кавычка.  Если  мы  увеличим  значение  pos,  то пропустим этот символ.

string filt_elems( "\",.;:!?)(\/" );

Так мы будем вызывать функцию filter_text():

filter_text( text_locations->first, filt_elems );

А вот часть распечатки, сделанной тестовой версией filter_text():

filter_text: untamed. found! : pos: 7. after: untamed

filter_text: "Daddy, found! : pos: 0. after: Daddy,

found! : pos: 5. after: Daddy

filter_text: thing," found! : pos: 5. after: thing"

found! : pos: 5.

after: thing

filter_text: "I found! : pos: 0. after: I

filter_text: Daddy, found! : pos: 5. after: Daddy

filter_text: there?" found! : pos: 5. after: there"

found! : pos: 5. after: there

 

Упражнение 6.15

Напишите программу, которая удаляет все символы, кроме STL из строки:

"/.+(STL).$1/"

используя сначала erase(pos,count), а затем erase(iter,iter).

Упражнение 6.16

string sentence( "kind of" );

string s1 ( "whistle" )

Напишите программу, которая с помощью разных функций вставки из строк

string s2 ( "pixie" )

составит предложение

"A whistling-dixie kind of walk"

6.10. Приводим слова к стандартной форме

Одной из проблем при разработке текстовых поисковых систем является необходимость распознавать  слова в различных словоформах,  такие, как cry, cries и cried, baby и babies, и, что гораздо проще, написанные заглавными и строчными буквами, например home и Home. Первая задача, распознавание словоформ, слишком сложна,  поэтому мы приведем здесь ее заведомо неполное решение. Сначала заменим все прописные буквы

void

strip_caps( vector<string,allocator> *words )

{

vector<string,allocator>::iterator iter=words->begin() ;

vector<string,allocator>::iterator iter_end=words->end() ;

string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );

while ( iter != iter_end ) {

string::size_type pos = 0;

while (( pos = (*iter).find_first_of( caps, pos ))

!= string::npos )

(*iter)[ pos ] = to1ower( (*iter)[pos] );

++iter;

}

строчными:

}

Функция

to1ower( (*iter)[pos] );

 

входит в стандартную библиотеку С. Она заменяет прописную букву соответствующей ей строчной. Для использования tolower() необходимо включить заголовочный файл:

#include <ctype.h>

(В  этом  файле  объявлены   и  другие  функции,  такие,   как  isalpha(),  isdigit(), ispunct(), isspace(), toupper(). Полное описание этих функций см. [PLAUGER92]. Стандартная библиотека С++ включает класс ctype, который инкапсулирует всю функциональность стандартной библиотеки Си, а также набор функций, не являющихся членами, например toupper(), tolower() и т.д. Для их использования нужно включить заголовочный файл

#include <locale>

Однако   наша   реализация   компилятора   еще  не  поддерживала   класс  ctype,  и  нам пришлось использовать стандартную библиотеку Си.)

Проблема словоформ слишком сложна для того, чтобы пытаться решить ее в общем виде. Но даже самый примитивный вариант способен значительно улучшить работу нашей поисковой системы. Все, что мы сделаем в данном направлении, – удалим букву 's' на

void suffix_text( vector<string,allocator> *words )

{

vector<string,allocator>::iterator iter = words->begin(), iter_end = words->end();

while ( iter != iter_end ) {

// оставим слова короче трех букв как есть

if ( (*iter).size() <= 3 )

{ ++iter; continue; }

if ( (*iter)[ (*iter).size()-1 ] == 's' )

suffix_s( *iter );

// здесь мы могли бы обработать суффиксы

// ed, ing, 1y

++iter;

}

концах слов:

}

Слова из трех и менее букв мы пропускаем. Это позволяет оставить без изменения, например,  has,  its,  is и  т.д.,  однако  слова  tv и tvs мы  не сможем  распознать  как одинаковые.

string::size_type pos() = word.size()-3;

string ies( "ies" );

if ( ! word.compare( pos3, 3, ies )) {

word.replace( pos3, 3, 1, 'у' );

return;

Если слово кончается на "ies", как babies и cries, необходимо заменить "ies" на "y":

 

}

compare() возвращает  0,  если  две строки  равны. Первый  аргумент,  pos3,  обозначает начальную позицию, второй – длину сравниваемой подстроки (в нашем случае 3). Третий аргумент,  ies, –  строка-эталон.  (На самом  деле существует  шесть вариантов  функции compare(). Остальные мы покажем в следующем разделе.)

replace() заменяет  подстроку  набором   символов.  В  данном  случае  мы  заменяем подстроку  "ies" длиной  в  3  символа  единичным  символом  'y'.  (Имеется  десять перегруженных вариантов функции replace(). В следующем разделе мы коснемся остальных вариантов.)

Если  слово  заканчивается  на  "ses",  как  promises или  purposes,  нужно  удалить

string ses( "ses" );

if ( ! word.compare( pos3, 3, ses )) {

word.erase( pos3+l, 2 );

return;

суффикс "es"16:

}

Если слово кончается на "ous", как oblivious, fulvous, cretaceous, или на "is", как genesis, mimesis, hepatitis, мы не будем изменять его. (Наша система несовершенна. Например,  в  слове  kiwis надо  убрать  последнее  's'.)  Пропустим  и  слова, оканчивающиеся на "ius" (genius) или на "ss" (hiss, lateness, less). Нам поможет

string::size_type spos = 0;

string::size_type pos3 = word.size()-3;

// "ous", "ss", "is", "ius" string suffixes( "oussisius" );

if ( ! word.compare( pos3, 3, suffixes, spos, 3 ) ||       // ous

! word.compare( pos3, 3, suffixes, spos+6, 3 ) ||        // ius

! word.compare( pos3+l, 2, suffixes, spos+2, 2 ) || // ss

! word.compare( pos3+l, 2, suffixes, spos+4, 2 ) ) // is

вторая форма функции compare():

return;

// удалим последнее 's'

В противном случае удалим последнее 's':

word.erase( pos3+2 );

16 Конечно, в английском языке существуют исключения из правил. Наш эвристический алгоритм превратит crises (множ. число от crisis – прим. перев.) в cris. Ошибочка!

 

Имена  собственные,  например  Pythagoras,  Brahms,  Burne-Jones,  не  подпадают  под общие правила. Этот случай мы оставим как упражнение для читателя, когда будем рассказывать об ассоциативных контейнерах.

Но прежде чем перейти к ним, рассмотрим оставшиеся строковые операции.

Упражнение 6.17

Наша программа не умеет обрабатывать суффиксы ed (surprised), ly (surprisingly) и

ing (surprisingly). Реализуйте одну из функций для этого случая:

(a) suffix_ed() (b) suffix_ly() (c) suffix_ing()

6.11. Дополнительные операции со строками

Вторая форма функции-члена erase() принимает в качестве параметров два итератора,

ограничивающих удаляемую подстроку. Например, превратим

string name( "AnnaLiviaPlurabelle" );

typedef string::size_type size_type;

size_type startPos = name.find( 'L' )

size_type endPos        = name.find_1ast_of( 'b' );

name.erase( name.begin()+startPos,

в строку "Annabelle":

name.begin()+endPos );

Символ, на который указывает второй итератор, не входит в удаляемую подстроку.

Для третьей формы параметром является только один итератор; эта форма удаляет все символы, начиная с указанной позиции до конца строки. Например:

name.erase( name. begin()+4 );

оставляет строку "Anna".

Функция-член insert() позволяет вставить в заданную позицию строки другую строку или символ. Общая форма выглядит так:

string_object.insert( position, new_string );

position обозначает позицию, перед которой производится вставка. new_string может

string string_object( "Missisippi" );

string::size_type pos = string_object.find( "isi" );

быть объектом класса string, C-строкой или символом:

string_object.insert( pos+1, 's' );

 

string new_string ( "AnnaBelle Lee" );

string_object += ' '; // добавим пробел

// найдем начальную и конечную позицию в new_string pos = new_string.find( 'B' );

string::size_type posEnd = new_string.find( ' ' );

string_object.insert(

string_object.size(), // позиция вставки

new_string, pos,          // начало подстроки в new_string

posEnd            // конец подстроки new_string

Можно выделить для вставки подстроку из new_string:

)

string_object получает значение "Mississippi Belle". Если мы хотим вставить все символы new_string, начиная с pos, последний параметр нужно опустить.

string sl( "Mississippi" );

Пусть есть две строки:

string s2( "Annabelle" );

Как получить третью строку со значением "Miss Anna"?

string s3;

// скопируем первые 4 символа s1

Можно использовать функции-члены assign() и append():

s3.assign ( s1, 4 );

// добавим пробел

s3 теперь содержит значение "Miss".

s3 += ' ';

// добавим 4 первых символа s2

Теперь s3 содержит "Miss ".

s3.append(s2,4);

s3 получила значение "Miss Anna". То же самое можно сделать короче:

s3.assign(s1,4).append(' ').append(s2,4);

 

Другая   форма   функции-члена   assign() имеет   три   параметра:   второй   обозначает позицию начала, а третий – длину. Позиции нумеруются с 0. Вот как, скажем, извлечь

string beauty;

// присвоим beauty значение "belle"

"belle" из "Annabelle":

beauty.assign( s2, 4, 5 );

// присвоим beauty значение "belle"

Вместо этих параметров мы можем использовать пару итераторов:

beauty.assign( s2, s2.begin()+4, s2.end() );

В  следующем  примере  две  строки  содержат  названия  текущего  проекта  и  проекта,

находящегося   в   отложенном   состоянии.   Они   должны   периодически   обмениваться

string current_project( "C++ Primer, 3rd Edition" );

значениями, поскольку работа идет то над одним, то над другим. Например:

string pending_project( "Fantasia 2000, Firebird segment" );

Функция-член swap() позволяет обменять значения двух строк с помощью вызова

current_project.swap( pending_project );

Для строки

string first_novel( "V" );

операция взятия индекса

char ch = first_novel[ 1 ];

возвратит неопределенное значение: длина строки first_novel равна 1, и единственное правильное  значение  индекса  –  0.  Такая  операция  взятия  индекса  не  обеспечивает проверку правильности параметра, но мы всегда можем сделать это сами с помощью функции-члена size():

 

int

elem_count( const string &word, char elem )

{

int occurs = 0;

// не надо больше проверять ix

for ( int ix=0; ix < word.size(); ++-ix )

if ( word[ ix ] == elem )

++occurs;

return occurs;

}

void

mumble( const string &st, int index )

{

// возможна ошибка

char ch = st[ index ];

// ...

Там, где это невозможно или нежелательно, например:

}

следует воспользоваться  функцией  at(),  которая делает то же, что и операция взятия индекса,  но с проверкой.  Если  индекс  выходит  за границу,  возбуждается  исключение

void

mumble( const string &st, int index )

{

try {

char ch = st.at( index );

// ...

}

catch ( std::out_of_range ){...}

// ...

out_of_range:

}

string cobol_program_crash( "abend" );

Строки можно сравнивать лексикографически. Например:

string cplus_program_crash( "abort" );

Строка  cobol_program_crash лексикографически  меньше, чем cplus_program_crash: сопоставление производится по первому отличающемуся символу, а буква e в латинском алфавите идет раньше, чем o. Операция сравнения выполняется функцией-членом compare(). Вызов

sl.compare( s2 );

 

возвращает одно из трех значений:

если s1 больше, чем s2, то положительное; если s1 меньше, чем s2, то отрицательное; если s1 равно s2, то 0.

Например,

cobol_program_crash.compare( cplus_program_crash );

вернет отрицательное значение, а

cplus_program_crash.compare( cobol_program_crash );

положительное. Перегруженные операции сравнения (<, >, !=, ==, <=, >=) являются более компактной записью функции compare().

Шесть  вариантов  функции-члена  compare() позволяют  выделить  сравниваемые подстроки в одном или обоих операндах. (Примеры вызовов приводились в предыдущем разделе.)

Функция-член replace() дает десять способов заменить одну подстроку на другую (их длины   не  обязаны   совпадать).   В  двух  основных   формах  replace() первые  два аргумента задают заменяемую подстроку: в первом варианте в виде начальной позиции и длины, во втором – в виде пары итераторов на ее начало и конец. Вот пример первого

string sentence(

"An ADT provides both interface and implementation." );

string::size_type position = sentence.find_1ast_of( 'A' );

string::size_type length = 3;

// заменяем ADT на Abstract Data Type

варианта:

sentence.repiace( position, length, "Abstract Data Type" );

position представляет   собой   начальную   позицию,   а   length –  длину  заменяемой подстроки.   Третий   аргумент   является   подставляемой   строкой.   Его   можно   задать

string new_str( "Abstract Data Type" );

несколькими способами. Допустим, как объект string:

sentence.replace( position, length, new_str );

Следующий пример иллюстрирует выделение подстроки в new_str:

 

#include <string>

typedef string::size_type size_type;

// найдем позицию трех букв

size_type posA = new_str.find( 'A' ); size_type posD = new_str.find( 'D' ); size_type posT = new_str.find( 'T' );

// нашли: заменим T на "Type"

sentence.replace( position+2, 1, new_str, posT, 4 );

// нашли: заменим D на "Data "

sentence.replace( position+1, 1, new_str, posD, 5 );

// нашли: заменим A на "Abstract " sentence.replace( position, 1, new_str, posA, 9 );

Еще один вариант позволяет заменить подстроку на один символ, повторенный заданное

string hmm( "Some celebrate Java as the successor to C++." );

string:: size_type position = hmm.find( 'J' );

// заменим Java на xxxx

количество раз:

hmm.repiace( position, 4, 'x', 4 );

В данном примере используется указатель на символьный массив и длина вставляемой

const char *lang = "EiffelAda95JavaModula3";

int index[] = { 0, 6, 11, 15, 22 };

string ahhem(

"C++ is the language for today's power programmers." );

подстроки:

ahhem.replace(0, 3, lang+index[1], index[2]-index[1]);

string sentence(

"An ADT provides both interface and implementation." );

// указывает на 'A' в ADT

string: iterator start = sentence. begin()+3;

// заменяем ADT на Abstract Data Type

А здесь мы используем пару итераторов:

sentence.repiace( start, start+3, "Abstract Data Type" );

Оставшиеся четыре варианта допускают  задание заменяющей строки как объекта типа

string, символа, повторяющегося N раз, пары итераторов и C-строки.

Вот  и  все,  что  мы  хотели  сказать  об  операциях  со  строками.  Для  более  полной информации обращайтесь к определению стандарта С++ [ISO-C++97].

 

Упражнение 6.18

Напишите  программу,  которая  с  помощью  функций-членов  assign() и  append() из

string quote1( "When lilacs last in the dooryard bloom'd" );

строк

string quote2( "The child "is father of the man" );

составит предложение

"The child is in the dooryard"

Упражнение 6.19

string generate_salutation( string generic1, string lastname, string generic2,

string::size_type pos,

 

Напишите функцию:

 

int length );

 

 

которая в строке

string generic1( "Dear Ms Daisy:" );

заменяет Daisy и Ms (миссис). Вместо Daisy подставляется параметр lastname, а вместо

Ms подстрока

string generic2( "MrsMsMissPeople" );

длины length, начинающаяся с pos.

string lastName( "AnnaP" );

string greetings =

Например, вызов

generate_salutation( generici, lastName, generic2, 5, 4 );

вернет строку:

Dear Miss AnnaP:

 

6.12. Строим отображение позиций слов

В этом разделе мы построим отображение (map), позволяющее для каждого уникального слова   текста   сохранить   номера   строк   и   колонок,   в   которых   оно  встречается.   (В следующем   разделе   мы   изучим   ассоциативный   контейнер   set.)   В   общем   случае контейнер  set полезен,  если мы хотим знать, содержится  ли определенный  элемент в некотором множестве, а map позволяет связать с каждым из них какую-либо величину.

В  map хранятся   пары   ключ/значение.   Ключ   играет   роль   индекса   для   доступа   к ассоциированному с ним значению. В нашей программе каждое уникальное слово текста будет  служить  ключом,  а  значением  станет  вектор,  содержащий  пары  (номер  строки,

string query( "pickle" );

vector< location > *locat;

// возвращается location<vector>*, ассоциированный с "pickle"

номер колонки). Для доступа применяется оператор взятия индекса. Например:

locat = text_map[ query ];

Ключом здесь является строка, а значение имеет тип location<vector>*.

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

#include <map>

Какие  основные  действия  производятся  над  ассоциативными  контейнерами?  Их заполняют элементами или проверяют на наличие определенного элемента. В следующем подразделе мы покажем, как определить пару ключ/значение и как поместить такие пары в  контейнер.  Далее  мы  расскажем,  как  сформулировать  запрос  на  поиск  элемента  и извлечь значение, если элемент существует.

6.12.1. Определение объекта map и заполнение его элементами

Чтобы определить объект класса map, мы должны указать, как минимум, типы ключа и значения. Например:

map<string,int> word_count;

Здесь задается объект word_count типа map, для которого ключом служит объект типа

class employee;

string, а ассоциированным с ним значением – объект типа int. Аналогично

map<int,employee*> personnel;

определяет personnel как отображение ключа типа int (уникальный номер служащего)

на указатель, адресующий объект класса employee.

 

typedef pair<short,short> location;

typedef vector<location> loc;

Для нашей поисковой системы полезно такое отображение:

map<string,loc*> text_map;

Поскольку имевшийся в нашем распоряжении компилятор не поддерживал аргументы по умолчанию   для   параметров   шаблона,   нам   пришлось   написать   более   развернутое

map<string,loc*,         // ключ, значение

less<string>,  // оператор сравнения

allocator>        // распределитель памяти по умолчанию

определение:

text_map;

По   умолчанию   сортировка   ассоциативных   контейнеров   производится   с   помощью операции “меньше”. Однако можно указать и другой оператор сравнения (см. раздел 12.3 об объектах-функциях).

После    того    как    отображение    определено,    необходимо    заполнить    его    парами

#include <map>

#include <string>

map<string,int> word_count;

word_count[ string("Anna") ] = 1; word_count[ string("Danny") ] = 1; word_count[ string("Beth") ] = 1;

ключ/значение. Интуитивно хочется написать примерно так:

// и так далее ...

Когда мы пишем:

word_count[ string("Anna") ] = 1;

на самом деле происходит следующее:

1.   Безымянный временный объект типа string инициализируется значением "Anna" и передается оператору взятия индекса, определенному в классе map.

2.   Производится  поиск  элемента  с  ключом  "Anna" в  массиве  word_count.  Такого элемента нет.

3.   В word_count вставляется новая пара ключ/значение. Ключом является, естественно,

строка "Anna". Значением – 0, а не 1.

4.   После этого значению присваивается величина 1.

 

Если  элемент  отображения  вставляется  в  отображение  с  помощью  операции  взятия индекса, то значением этого элемента становится значение по умолчанию для его типа данных. Для встроенных арифметических типов – 0.

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

// предпочтительный метод вставки одного элемента

word_count.insert(

map<string,i nt>::

value_type( string("Anna"), 1 )

Для вставки одного элемента предпочтительнее использовать следующий метод:

);

В контейнере map определен тип value_type для представления хранимых в нем пар

map< string,int >::

ключ/значение. Строки

value_type( string("Anna"), 1 )

создают объект pair, который затем непосредственно вставляется в map. Для удобства чтения можно использовать typedef:

typedef map<string,int>::value_type valType;

Теперь операция вставки выглядит проще:

word_count.insert( valType( string("Anna"), 1 ));

Чтобы вставить элементы из некоторого диапазона, можно использовать метод insert(),

map< string, int > word_count;

// ... заполнить

map< string,int > word_count_two;

// скопируем все пары ключ/значение

принимающий в качестве параметров два итератора. Например:

word_count_two.insert(word_count.begin(),word_count.end());

Мы  могли  бы  сделать  то  же  самое,  просто  проинициализировав  одно  отображение другим:

 

// инициализируем копией всех пар ключ/значение

map< string, int > word_count_two( word_count );

Посмотрим, как можно построить отображение для хранения нашего текста. Функция separate_words(),   описанная   в   разделе   6.8,   создает   два   объекта:   вектор   строк, хранящий все слова текста, и вектор позиций, хранящий пары (номер строки, номер колонки)  для  каждого  слова.  Таким  образом,  первый  объект  дает  нам  множество значений ключей нашего отображения, а второй – множество ассоциированных  с ними значений.

separate_words() возвращает  эти  два  вектора  как  объект  типа  pair,  содержащий указатели   на   них.   Сделаем   эту   пару   аргументом   функции   build_word_map(),   в

// typedef для удобства чтения

typedef pair< short,short > location;

typedef vector< location >     loc;

typedef vector< string >         text;

typedef pair< text*,loc* >      text_loc;

extern map< string, loc* >*

результате которой будет получено соответствие между словами и позициями:

build_word_map( const text_loc *text_locations );

Сначала   выделим  память  для  пустого  объекта  map и  получим  из  аргумента-пары

map<string,loc*> *word_map = new map< string, loc* >;

vector<string>             *text_words = text_locations->first;

указатели на векторы:

vector<location> *text_locs = text_locations->second;

Теперь нам надо синхронно обойти оба вектора, учитывая два случая:

слово встретилось впервые. Нужно поместить в map новую пару ключ/значение;

слово  встречается  повторно.  Нам  нужно  обновить  вектор  позиций,  добавив дополнительную пару (номер строки, номер колонки).

Вот текст функции:

 

register int elem_cnt = text_words->size();

for ( int ix=0; ix < elem_cnt; ++ix )

{

string textword = ( *text_words )[ ix ];

// игнорируем слова короче трех букв

// или присутствующие в списке стоп-слов

if ( textword.size() < 3 ||

exclusion_set.count( textword ))

continue;

// определяем, занесено ли слово в отображение

// если count() возвращает 0 - нет: добавим его

if ( ! word_map->count((*text_words)[-ix] ))

{

loc *ploc = new vector<location>;

ploc->push_back( (*text_locs) [ix] );

word_map->insert(value_type((*text_words)[ix],ploc));

}

else

// добавим дополнительные координаты

(*word_map)[(*text_words)[ix]]->

push_back((*text_locs)[ix]);

}

(*word_map)[(*text_words)[ix]]->

Синтаксически сложное выражение

push_back((*text_locs)[ix]);

// возьмем слово, которое надо обновить

string word = (*text_words) [ix];

// возьмем значение из вектора позиций

vector<location> *ploc = (*word_map) [ word ];

// возьмем позицию - пару координат

loc = (*text_locs)[ix];

// вставим новую позицию

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

ploc->push_back(loc);

Выражение все еще остается сложным, так как наши векторы представлены указателями.

Поэтому вместо употребления оператора взятия индекса:

string word = text_words[ix]; // ошибка

мы вынуждены сначала разыменовать указатель на вектор:

string word = (*text_words) [ix]; // правильно

 

В конце концов build_word_map() возвращает построенное отображение:

return word_map;

int main()

{

// считываем файл и выделяем слова

vector<string, allocator> *text_file = retrieve_text();

text_loc *text_locations = separate_words( text_file );

// обработаем слова

// ...

// построим отображение слов на векторы позиций

map<string,lос*,less<string>,allocator>

*text_map = build_word_map( text_locatons );

// ...

Вот как выглядит вызов этой функции из main():

}

6.12.2. Поиск и извлечение элемента отображения

Оператор    взятия   индекса   является    простейшим    способом    извлечения   элемента.

// map<string,int> word_count;

Например:

int count = word_count[ "wrinkles" ];

Однако  этот  способ  работает  так,  как надо,  только  при  условии,  что запрашиваемый ключ действительно содержится в отображении. Иначе оператор взятия индекса поместит в отображение элемент с таким ключом. В данном случае в word_count занесется пара

string( "wrinkles" ), 0

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

count(keyValue): функция-член count() возвращает количество элементов с данным  ключом.  (Для  отображения  оно  равно  только  0 или  1).  Если  count()

int count = 0;

if ( word_count.count( "wrinkles" ))

вернула 1, мы можем смело использовать индексацию:

count = word_count[ "wrinkles" ];

 

find(keyValue): функция-член find() возвращает итератор, указывающий на

int count = 0;

map<string,int>::iterator it = word_count.find( "wrinkles" );

if ( it != word_count.end() )

элемент, если ключ найден, и итератор end() в противном случае. Например:

count = (*it).second;

Значением  итератора  является  указатель  на  объект  pair,  в  котором  first содержит ключ, а second – значение. (Мы вернемся к этому в следующем подразделе.)

6.12.3. Навигация по элементам отображения

После того как мы построили отображение, хотелось бы распечатать его содержимое. Мы можем  сделать   это,  используя  итератор,   начальное  и  конечное  значение  которого получают   с   помощью   функций-членов    begin() и   end().   Вот   текст   функции

void

display_map_text( map<string,loc*> *text_map )

{

typedef map<string,loc*> tmap;

tmap::iterator iter = text_map->begin(),

iter_end = text_map->end();

while ( iter != iter_end )

{

cout << "word: " << (*iter).first << " (";

int loc_cnt = 0;

loc *text_locs = (*iter).second;

loc::iterator liter = text_locs->begin(),

liter_end = text_locs->end();

while (liter != liter_end ) {

if ( loc_cnt )

cout << ',';

else ++loc_cnt;

cout << '(' << (*liter).first

<< ',' << (*liter).second << ')';

++liter;

}

cout << ") ";

++iter;

}

cout << endl;

display_map_text():

}

Если наше отображение не содержит элементов, данная функция не нужна. Проверить,

пусто ли оно, можно с помощью функции-члена size():

 

if ( text_map->size() )

display_map_text( text_map );

Но  более  простым  способом,  без  подсчета  элементов,   будет  вызов  функции-члена

if ( ! text_map->empty() )

empty():

display_map_text( text_map );

6.12.4. Словарь

Вот  небольшая  программа,  иллюстрирующая  построение  отображения,  поиск  в нем и обход элементов. Здесь используются два отображения. Первое, необходимое для преобразования  слов,  содержит  два  элемента  типа  string.  Ключом  является  слово, которое нуждается в специальной обработке, а значением – слово, заменяющее ключ. Для простоты  мы  задали  пары  ключ/значение  непосредственно  в  тексте  программы  (вы можете модифицировать программу так, чтобы она читала их из стандартного ввода или из файла). Второе отображение используется для подсчета произведенных замен. Текст программы выглядит следующим образом:

#include

#include <vector>

#include <iostream>

С++#iдnлcяluнdачeи<нsаtюrщinиgх>

int main()

{

296

 

map< string, string > trans_map;

typedef map< string, string >::value_type valType;

// первое упрощение:

// жестко заданный словарь

trans_map.insert( va1Type( "gratz", "grateful" ));

trans_map.insert( va1Type( "'em", trans_map.insert( va1Type( "cuz", trans_map.insert( va1Type( "nah", trans_map.insert( va1Type( "sez", trans_map.insert( va1Type( "tanx", trans_map.insert( va1Type( "wuz", trans_map.insert( va1Type( "pos",

"them" "because" "no" "says" "thanks" "was" "suppose"

));

));

));

));

));

));

));

// напечатаем словарь

map< string,string >::iterator it;

 

 

cout << "Наш словарь подстановок: ";

for ( it = trans_map.begin();

it != trans_map.end(); ++it )

cout << "ключ: "         << (*it).first << " "

<< "значение: " << ("it).second << " ";

cout << " ";

// второе упрощение: жестко заданный текст

string textarray[14]={ "nah", "I", "sez", "tanx",

"cuz", "I", "wuz", "pos", "to", "not",

"cuz", "I", "wuz", "gratz" };

vector< string > text( textarray, textarray+14 );

vector< string >::iterator iter;

// напечатаем текст

cout << "Исходный вектор строк: ";

int cnt = 1;

for ( iter = text-begin(); iter != text.end();

++iter,++cnt )

cout << *iter << ( cnt \% 8 ? " " : " " );

cout << " ";

// map для сбора статистики

map< string,int > stats;

typedef map< string,int >::value_type statsValType;

// здесь происходит реальная работа

for ( iter=text.begin(); iter != text.end(); ++iter )

if (( it = trans_map.find( *iter ))

!= trans_map.end() )

{

if ( stats.count( *iter ))

stats [ *iter ] += 1;

else stats.insert( statsVa1Type( *iter, 1 ));

*iter = (*it).second;

}

// напечатаем преобразованный текст

cout << "Преобразованный вектор строк: ";

cnt = 1;

for ( iter = text.begin(); iter != text.end();

++iter, ++cnt )

cout << *iter << ( cnt \% 8 ? " " : " " );

cout << " ";

// напечатаем статистику

cout << "И напоследок статистика: ";

map<string,int,less<string>,allocator>::iterator siter;

for (siter=stats.begin(); siter!=stats.end(); ++siter)

cout << (*siter).first    << " "

 

}

Вот результат работы программы:

Наш словарь подстановок:

key: 'em           value: them key: cuz   value: because key: gratz        value: grateful key: nah           value: no

key: pos           value: suppose key: sez           value: says key: tanx   value: thanks key: wuz            value: was

Исходный вектор строк:

nah I sez tanx cuz I wuz pos

to not cuz I wuz gratz

Преобразованный вектор строк:

no I says thanks because I was suppose to not because I was grateful

И напоследок статистика:

cuz было заменено 2 раз(а) gratz было заменено 1 раз(а) nah было заменено 1 раз(а) pos было заменено 1 раз(а) sez было заменено 1 раз(а) tanx было заменено 1 раз(а) wuz было заменено 2 раз(а)

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

Существуют три формы функции-члена erase() для удаления элементов отображения. Для единственного элемента используется erase() с ключом или итератором в качестве аргумента,  а  для  последовательности  эта  функция  вызывается  с  двумя  итераторами.

string removal_word;

cout << "введите удаляемое слово: ";

cin >> removal_word;

if ( text_map->erase( remova1_word ))

cout << "ok: " << remova1_word << " удалено ";

Например, мы могли бы позволить удалять элементы из text_map таким образом:

else cout << "увы: " << remova1_word << " не найдено! ";

Альтернативой является проверка: действительно ли слово содержится в text_map?

 

map<string,loc*>::iterator where;

where = text_map.find( remova1_word );

if ( where == text_map->end() )

cout << "увы: " << remova1_word << " не найдено! ";

else {

text_map->erase( where );

cout << "ok: " << remova1_word << " удалено! ";

}

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

6.15.

Упражнение 6.20

Определите отображение, где ключом является фамилия, а значением – вектор с именами детей. Поместите туда как минимум шесть элементов. Реализуйте возможность делать запрос по фамилии, добавлять имена и распечатывать содержимое.

Упражнение 6.21

Измените программу из предыдущего упражнения так, чтобы вместе с именем ребенка записывалась дата его рождения: пусть вектор-значение хранит пары строк – имя и дата.

Упражнение 6.22

Приведите хотя бы три примера, в которых нужно использовать отображение. Напишите определение объекта map для каждого примера и укажите наиболее вероятный способ вставки и извлечения элементов.

6.13. Построение набора стоп-слов

Отображение состоит из пар ключ/значение. Множество (set), напротив, содержит неупорядоченную совокупность ключей. Например, бизнесмен может составить “черный список”  bad_checks,  содержащий  имена  лиц,  в  течение  последних  двух  лет присылавших  фальшивые  чеки.  Множество  полезно тогда,  когда  нужно узнать, содержится ли определенное значение в списке. Скажем, наш бизнесмен, принимая чек от кого-либо, может проверить, есть ли его имя в bad_checks.

Для   нашей   поисковой   системы   мы   построим   набор   стоп-слов –   слов,   имеющих семантически нейтральное значение (артикли, союзы, предлоги), таких, как the, and, into, with, but и т.д. (это улучшает качество системы, однако мы уже не сможем найти первое предложение  из  знаменитого  монолога  Гамлета:  “To  be  or  not  to  be?”).  Прежде  чем добавлять слово к word_map, проверим, не содержится ли оно в списке стоп-слов. Если содержится, проигнорируем его.

6.13.1. Определение объекта set и заполнение его элементами

Перед использованием класса set необходимо включить соответствующий заголовочный файл:

 

#include <set>

Вот определение нашего множества стоп-слов:

set<string> exclusion_set;

exclusion_set.insert( "the" );

Отдельные элементы могут добавляться туда с помощью операции insert(). Например:

exclusion_set.insert( "and" );

Передавая  insert() пару  итераторов,  можно  добавить  целый  диапазон  элементов.

Скажем, наша поисковая система позволяет указать файл со стоп-словами. Если такой

typedef set< string >::difference_type diff_type;

set< string > exclusion_set;

ifstream infile( "exclusion_set" );

if ( ! infile )

{

static string default_excluded_words[25] = {

"the","and","but","that","then","are","been", "can"."can't","cannot","could","did","for", "had","have","him","his","her","its","into", "were","which","when","with","would"

};

cerr << "предупреждение! невозможно открыть файл стоп-слов! -- "

<< "используется стандартный набор слов ";

copy( default_excluded_words, default_excluded_words+25, inserter( exclusion_set, exclusion_set.begin() ));

}

else {

istream_iterator<string,diff_type> input_set(infile),eos;

copy( input_set, eos, inserter( exclusion_set,

exclusion_set.begin() ));

файл не задан, берется некоторый набор слов по умолчанию:

}

В   этом   фрагменте   кода   встречаются   два   элемента,   которые   мы   до  сих   пор   не рассматривали:  тип  difference_type и  класс  inserter.  difference_type – это тип результата вычитания двух итераторов для нашего множества строк. Он передается в качестве одного из параметров шаблона istream_iterator.

copy() –один   из   обобщенных   алгоритмов.   (Мы   рассмотрим   их   в   главе   12   и   в Приложении.)   Первые   два   параметра –   пара   итераторов   или   указателей –   задают диапазон. Третий параметр является либо итератором, либо указателем на начало контейнера, в который элементы копируются.

Проблема с этой функцией вызвана ограничением, вытекающим из ее реализации: количество копируемых элементов не может превосходить числа элементов в контейнере- адресате.  Дело  в  том,  что  copy() не  вставляет  элементы,  она  только  присваивает

 

каждому элементу новое значение. Однако ассоциативные контейнеры не позволяют явно задать размер. Чтобы скопировать элементы в наше множество, мы должны заставить copy() вставлять  элементы.  Именно  для  этого  служит  класс  inserter (детально  он рассматривается в разделе 12.4).

6.13.2. Поиск элемента

Две операции, позволяющие отыскать в наборе определенное значение, – это find() и  count().  find() возвращает  итератор,  указывающий  на  найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при   наличии   элемента   и   0 в   противном   случае.   Добавим   проверку   на

if ( exclusion_set.count( textword ))

continue;

существование в функцию build_word_map():

// добавим отсутствующее слово

6.13.3. Навигация по множеству

Для проверки наших кодов реализуем небольшую функцию, выполняющую поиск по одному  слову  (поддержка  языка  запросов  будет  добавлена  в  главе  17).  Если  слово найдено, мы будем показывать каждую строку, в которой оно содержится. Слово может повторяться в строке, например:

tomorrow and tomorrow and tomorrow

однако такая строка будет представлена только один раз.

Одним   из   способов   не  учитывать   повторное   вхождение  слова   в   строку   является

// получим указатель на вектор позиций

loc ploc = (*text_map)[ query_text ];

// переберем все позиции

// вставим все номера строк в множество set< short > occurrence_lines; loc::iterator liter = ploc->begin(),

liter_end = ploc->end();

while ( liter != liter_end ) {

occurrence_lines.insert( occurrence_lines.end(), (*liter).first );

++liter;

использование множества, как показано в следующем фрагменте кода:

}

 

Контейнер set не допускает дублирования ключей. Поэтому можно гарантировать, что

occurrence_lines не содержит  повторений. Теперь нам достаточно  перебрать  данное

register int size = occurrence_lines.size();

cout << " " << query_text

<< " встречается " << size

<< " раз(а):")

<< " ";

set< short >::iterator it=occurrence_lines.begin();

for ( ; it != occurrence_lines.end(); ++it ) {

int line = -it;

cout << " ( строка "

<< line + 1 << " ) "

<< (*text_file)[line] << endl;

множество, чтобы показать все номера строк, где встретилось данное слово:

}

(Полная реализация query_text() представлена в следующем разделе.)

Класс set поддерживает операции size(), empty() и erase() точно таким же образом, как и класс map, описанный выше. Кроме того, обобщенные алгоритмы предоставляют набор специфических  функций  для множеств, например set_union() (объединение) и set_difference() (разность).  (Они  использованы  при  реализации  языка  запросов  в главе 17.)

Упражнение 6.23

Добавьте  в  программу  множество  слов,  в  которых  заключающее  's' не подчиняется общим правилам и не должно удаляться. Примерами таких слов могут быть Pythagoras, Brahms и  Burne_Jones.  Включите  в  функцию  suffix_s() из  раздела  6.10  проверку этого набора.

Упражнение 6.24

Определите вектор, содержащий названия книг, которые вы собираетесь прочесть в ближайшие шесть виртуальных месяцев, и множество, включающее названия уже прочитанных произведений. Напишите программу, которая выбирает для вас книгу из вектора  при  условии,  что  вы  ее  еще  не  прочитали.  Выбранное  название  программа должна заносить в множество прочитанных. Однако вы могли отложить книгу; следовательно, нужно обеспечить возможность удалять ее название из множества прочитанных. По окончании шести виртуальных месяцев распечатайте список прочитанного и непрочитанного.

6.14. Окончательная программа

Ниже представлен полный текст программы, разработанной в этой главе, с двумя модификациями:   мы   инкапсулировали   все  структуры   данных   и  функции   в  класс TextQuery (в последующих главах мы обсудим подобное использование классов), кроме того,  текст  был  изменен,  так  как  наш  компилятор  поддерживал  стандарт  С++  не полностью.

C++ !J:IT5I Ha'IHHmom:nx

HarrpHMep, 6H6JIHOTeKa  iostream He  COOTBeTCTBOBaJia TeK)Illl:eMy  CTaH)J;apTy. llla6JIOHhi He IIOMepJKHBarrn  3Ha'!eHH5I aprYMeHTOB no YMOIT'IaHHIO.   Bo3MO:>KHO, BaM rrpn)J;eTc5I H3MeHHTh KOe-'ITO B:HOH rrporpaMMe, 'IT06hiOHa KOMIIlllillpOBaJiaCh B BaiiieH CllCTeMe.

302

// стандартные заголовочные файлы С++

#include <algorithm>

#include <string>

С++#iдnлcяluнdачeи<нvаeюcщtoиrх>

#include <utility>

#include <map>

#include <set>

// заголовочный файл iostream, не отвечающий стандарту

#include <fstream.h>

// заголовочные файлы С

#include <stddef.h>

#include <ctype.h>

// typedef для удобства чтения

typedef pair<short,short>       location; typedef vector<location,allocator>  loc; typedef vector<string,allocator>             text; typedef pair<text*,loc*>            text_loc;

class TextQuery {

public:

TextQuery() { memset( this, 0, sizeof( TextQuery )); }

static void

filter_elements( string felems ) { filt_elems = felems; }

void query_text();

void display_map_text();

void display_text_locations();

void doit() { retrieve_text(); separate_words(); filter_text(); suffix_text();

strip_caps();

build_word_map();

303

 

}

private:

void retrieve_text();

void separate_words(): void filter_text(); void strip_caps();

void suffix_textQ;

void suffix_s( string& );

void build_word_map();

private:

vector<string,allocator>          *lines_of_text;

text_loc           *text_locations;

map< string,loc*,

less<string>,allocator>            *word_map;

static string      filt_elems;

};

string TextQuery::filt_elems( "\", •;: !?)(V" );

int main()

{

TextQuery tq; tq.doit(); tq.query_text(); tq.display_map_text();

}

void TextQuery:: retrieve_text()

{

string file_name;

cout << "please enter file name: ";

cin >> file_name;

ifstream infile( file_name.c_str(), ios::in );

 

}

Упражнение 6.25

Объясните,  почему нам потребовался  специальный  класс  inserter для заполнения

set<string> exclusion_set;

ifstream           infile( "exclusion_set" );

copy( default_excluded_words, default_excluded_words+25,

набора стоп-слов (это упоминается в разделе 6.13.1, а детально рассматривается в 12.4.1).

inserter(exclusion_set, exclusion_set.begin() ));

Упражнение 6.26

Первоначальная реализация поисковой системы отражает процедурный подход: набор глобальных функций оперирует набором независимых структур данных. Окончательный вариант представляет собой альтернативный подход, когда мы инкапсулируем функции и данные в класс TextQuery. Сравните оба способа. Каковы недостатки и преимущества каждого?

Упражнение 6.27

В данной  версии  программы  имя файла с текстом вводится по запросу.  Более удобно было бы задавать его как параметр командной строки; в главе 7 мы покажем, как это делается. Какие еще параметры командной строки желательно реализовать?

6.15. Контейнеры multimap и multiset

Контейнеры  map и  set не  допускают  повторяющихся  значений  ключей,  а  multimap (мультиотображение)  и  multiset (мультимножество)  позволяют  сохранять  ключи  с дублирующимися  значениями.  Например,  в  телефонном  справочнике  может понадобиться отдельный список номеров для каждого абонента. В перечне книг одного автора может быть несколько названий, а в нашей программе с одним словом текста сопоставляется  несколько  позиций.  Для  использования  multimap и  multiset нужно

#include <map>

multimap< key_type, value_type > multimapName;

// ключ - string, значение - list< string >

multimap< string, list< string > > synonyms;

#include <set>

включить соответствующий заголовочный файл – map или 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():

 

#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( search_item ))

{

// не найдено

case 0:

break;

// найден 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.equa1_range( search_item );

for (; pos.first != pos.second; pos.first++ )

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

}

}

}

Вставка   и  удаление  элементов   в  multimap и  multiset ничем  не  отличаются  от аналогичных операций с контейнерами map и 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" )));

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

authors[ "Barth, John" ]; // ошибка: multimap

Упражнение 6.28

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

6.16. Стек

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

#include <stack>

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

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

 

Операция

Действие

empty()

Возвращает true, если стек пуст, и false в противном случае

size()

Возвращает количество элементов в стеке

pop()

Удаляет  элемент  с  вершины  стека,  но не возвращает его значения

top()

Возвращает  значение элемента  с вершины

 

 

стека, но не удаляет его

push(item)

Помещает новый элемент в стек

 

#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()

<< " ожидается: " << 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

 

Операция

Действие

empty()

Возвращает  true,  если  очередь  пуста,  и

false в противном случае

 

size()

Возвращает количество элементов в очереди

pop()

Удаляет первый элемент очереди, но не возвращает его значения. Для очереди с приоритетом первым является элемент с наивысшим приоритетом

front()

Возвращает значение первого элемента очереди, но не удаляет его. Применимо только к простой очереди

back()

Возвращает значение последнего элемента очереди, но не удаляет его. Применимо только к простой очереди

top()

Возвращает  значение  элемента  с наивысшим приоритетом, но не удаляет его. Применимо только к очереди с приоритетом

push(item)

Помещает новый элемент в конец очереди. Для  очереди  с  приоритетом  позиция элемента определяется его приоритетом.

 

Элементы   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 ) ";

}

Наиболее   существенным   изменениям   подвергнется   конструктор   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;

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

 

};

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

iStack, определим следующий typedef:

typedef Stack<int> iStack;

Модификацию операторов класса мы оставим читателю для упражнения.

Упражнение 6.29

Модифицируйте функцию peek() (упражнение 4.23 из раздела 4.15) для шаблона класса

Stack.

Упражнение 6.30

Модифицируйте операторы для шаблона класса Stack. Запустите тестовую программу из раздела 4.15 для новой реализации

Упражнение 6.31

По аналогии с классом List из раздела 5.11.1 инкапсулируйте наш шаблон класса Stack

в пространство имен Primer_Third_Edition