Глава 12. Контейнерные классы

327

friend 3

map 3

operator 6

protected 3

public 2 5

return 8 value_compare 1 5

value_type 2 7

x 7 8

У 7 8

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

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

Для каждого слова с помощью функции f i nd проверяется, содержится ли оно в словаре. Если нет (функция возвратила endO), в словарь с помощью функции insert добавляется пара, состоящая их этого слова и пустого множества (вызов конструктора set_i()). Функция insert возвращает пару, первым элементом которой (first) является итератор на вставленный элемент. Он присваивается переменной im.

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

Далее выполняется вывод словаря. Для каждого слова в цикле выводятся элементы множества номеров строк.

Глава 13

Итераторы

и функциональные объекты

Итераторы и функциональные объекты широко используются в стандартной библиотеке. Понятие итератора было введено в предыдущем разделе при рассмотрении контейнерных классов, с функциональными объектами мы встречались при рассмотрении очередей с приоритетами. Рассмотрим их более подробно для того, чтобы применять в алгоритмах библиотеки, которые описываются далее в разделе «Алгоритмы» (с. 343).

Итераторы

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

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

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

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

В итераторах используются понятия «текущий указываемый элемент» и «указать на следующий элемент». Доступ к текущему элементу последовательности выполняется аналогично указателям с помощью операций * и ->. Переход к еле-