ilist item *it = mylist.find( 1 );

mylist.insert( it, ia, 6 );

изменит список таким образом:

(9) ( 0 1 1 2 3 5 8 13 21 )

Упражнение 5.22

Функции concat() и reverse() модифицируют оригинальный список. Это не всегда желательно. Напишите аналогичную пару функций, которые создают новый объект

ilist ilist::reverse copy();

ilist:

ilist ilist::concat copy( const ilist &rhs );

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

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

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

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

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

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

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

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

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

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

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

вхождение 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), не повторяя одну и ту же несколько раз.

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

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

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

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

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

! слово не встречается в строке

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

i Lincoln

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

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

i (War Rights)

Civil&&(WarIRights)

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

Например, если нужно найти все вхождения словосочетаний Civil War и Civil Rights, запрос может выглядеть таким образом9:

[ Civil && ( War Rights )

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