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

Таблица 10.7. Аргументы алгоритма-члена splice()классов listи forward_list

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

Аналогично алгоритмы merge()и splice()деструктивны к своим аргументам. Например, обобщенная версия функции merge()запишет объединенную последовательность по заданному итератору назначения; две исходных последовательности останутся неизменны. Специфическая для списка функция merge()разрушит заданный список — элементы будут удаляться из списка аргумента по мере их объединения в объект, для которого был вызван аргумент merge(). После объединения элементы из обоих списков продолжают существовать, но принадлежат уже одному списку.

Упражнение 10.42. Переделайте программу, устранявшую повторяющиеся слова, написанную в разделе 10.2.3, так, чтобы использовался список, а не вектор.

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

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

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

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

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

Контейнеры 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). Поддерживает те же операции, что и двунаправленный итератор, плюс способность использовать операторы сравнения для выяснения позиций двух итераторов относительно друг друга, а также способность осуществлять с итераторами арифметические действия, обеспечивая таким образом произвольный доступ к элементам.