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

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.

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

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

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

два указателя в каждом элементе и необходимость использования указателя для получения значения элемента.

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