Язык программирования C++. Пятое издание - Стенли Липпман

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

Итераторы подразделяются на пять категорий в зависимости от поддерживаемых ими функциональных возможностей. Категории итераторов: ввода, вывода, прямой, двунаправленный и произвольного доступа. Итератор относится к определенной категории, если он поддерживает функциональные возможности, обязательные для итератора данной категории.

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

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

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

Контейнеры forward_list и list определяют собственные версии некоторых из обобщенных алгоритмов. В отличие от обобщенных алгоритмов, эти специфические версии изменяют переданные им списки.

Термины

Адаптер back_inserter. Адаптер итератора, который, получив ссылку на контейнер, создает итератор вставки, использующий функцию push_back() для добавления элементов в указанный контейнер.

Адаптер front_inserter. Адаптер итератора, который, получив ссылку на контейнер, создает итератор вставки, использующий функцию push_front() для добавления элементов в начало указанного контейнера.

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

Бинарный предикат (binary predicate). Предикат с двумя параметрами.

Вызываемый объект (callable object). Объект, способный быть левым операндом оператора вызова. К вызываемым объектам относятся указатели на функции, лямбда-выражения и объекты классов, определяющих перегруженные версии оператора вызова.

Двунаправленный итератор (bidirectional iterator). Поддерживает те же операции, что и прямые итераторы, плюс способность использовать оператор -- для перемещения по последовательности назад.

Итератор istream_iterator. Потоковый итератор, обеспечивающий чтение из потока ввода.

Итератор ostream_iterator. Потоковый итератор, обеспечивающий запись в поток вывода.

Итератор ввода (input iterator). Итератор, позволяющий читать, но не записывать элементы.

Итератор вставки (insert iterator). Итератор, использующий функции контейнера для добавления элементов в данный контейнер.

Итератор вывода (output iterator). Итератор, позволяющий записывать, но не обязательно читать элементы.

Итератор перемещения (move iterator). Итератор, позволяющий перемещать элементы, а не копировать их. Итераторы перемещения рассматриваются в главе 13.

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

Категории итераторов (iterator categories). Концептуальная организация итераторов на основании поддерживаемых ими операций. Категории итераторов составляют иерархию, в которой более мощные итераторы предоставляют те же операции, что и менее мощные. Пока итератор обеспечивает, по крайней мере, достаточный уровень операций, он вполне применим. Например, некоторым алгоритмам требуются только итераторы ввода. Такие алгоритмы могут быть применены к любому другому итератору, который обладает возможностями, не ниже, чем у итератора вывода. Алгоритмы, которым необходимы итераторы прямого доступа, применимы только для тех итераторов, которые поддерживают операции прямого доступа.

Лямбда-выражение (lambda expression). Вызываемый блок кода. Лямбды немного похожи на безымянные встраиваемые функции. Они начинается со списка захвата, позволяющего лямбда-выражению получать доступ к переменным в содержащей функции. Подобно функции, имеет список параметров (возможно пустой), тип возвращаемого значения и тело функции. У лямбда-выражения может отсутствовать тип возвращаемого значения. Если тело функции представляет собой одиночный оператор return, тип возвращаемого значения выводится из типа возвращаемого объекта. В противном случае типом пропущенного возвращаемого значения по умолчанию принимается void.

Обобщенный алгоритм (generic algorithm). Алгоритм, не зависящий от типа контейнера.

Потоковый итератор (stream iterator). Итератор, который может быть связан с потоком.

Предикат (predicate). Функция, которая возвращает значение типа bool (логическое) или допускающее преобразование в него. Зачастую используется обобщенными алгоритмами для проверки элементов. Используемые библиотекой предикаты являются либо унарными (получающими один аргумент), либо бинарными (получающими два аргумента).

Прямой итератор (forward iterator). Итератор, позволяющий читать и записывать элементы, но не поддерживающий оператор --.

Реверсивный итератор (reverse iterator). Итератор, позволяющий перемещаться по последовательности назад. У этих итераторов операторы ++ и -- имеют противоположный смысл.

Список захвата (capture list). Часть лямбда-выражения, определяющая переменные из окружающего контекста, к которым может обращаться лямбда-выражение.

Унарный предикат (unary predicate). Предикат с одним параметром.

Функция bind(). Библиотечная функция, связывающая один или несколько аргументов с вызываемым выражением. Функция bind() определена в заголовке functional.

Функция cref(). Библиотечная функция, возвращающая копируемый объект, содержащий ссылку на константный объект типа, не допускающего копирования.

Функция ref(). Библиотечная функция, создающая копируемый объект из ссылки на объект типа, не допускающего копирования.

Глава 11

Ассоциативные контейнеры

Ассоциативные контейнеры кардинально отличаются от последовательных: элементы в ассоциативном контейнере хранятся и предоставляются по ключу. Элементы последовательного контейнера, напротив, хранятся и предоставляются последовательно, по их позиции в контейнере.

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

Ассоциативные контейнеры (associative container) обеспечивают быстрый поиск и предоставление элементов по ключу. Двумя первичными типами ассоциативных контейнеров являются map (карта) и set (набор). Элементами контейнера map являются пары ключ-значение (key-value pair): ключ выступает в роли индекса, а значение представляет собой хранимые в контейнере данные. Контейнер set содержит только ключи и предоставляет эффективные способы запроса на проверку наличия определенного ключа. Набор можно было бы использовать для хранения слов, которые следует проигнорировать при некой обработке текста. Карту можно использовать для словаря: слово было бы ключом, а его определение — значением.

Библиотека предоставляет восемь ассоциативных контейнеров (табл. 11.1), которые различаются по трем факторам: (1) они являются набором (set) или картой map; (2) они требуют уникальных ключей или допускает их совпадение; (3) они хранят элементы упорядочено или нет. В именах контейнеров, допускающих совпадение ключей, присутствует слово multi; имена контейнеров, не упорядочивающих хранимые ключи начинаются со слова unordered. Следовательно, unordered_multi_set — это набор, не требующий уникальных ключей и хранящий элементы неупорядоченными, в то время как set — это набор с уникальными ключами, которые хранятся упорядочено. Для организации своих элементов неупорядоченные контейнеры используют хеш-функцию. Подробно хеш-функции рассматриваются в разделе 11.4.