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

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, запрос может выглядеть таким образом :

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, или

! Lincoln

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

( Abe || Abraham ) Lincoln

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

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

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

Рис. 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))

there ((3,5),(5,7))

thing ((3,9))

through ((1,4))

time ((4,6))

untamed ((3,2))

wanting ((4,7))

wind ((1,2))

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

( line 1 ) Alice Emma has long flowing red hair. Her Daddy says

enter a word against which to search the text.

( 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.

enter a word against which to search the text.

to quit, enter a single character == .

Ok, bye!

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