Текст книги "Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи"

Сложность линейная (не более N^*count сравнений).

Копирует элементы предварительно отсортированного диапазона [first1, last1) в диапазон, начинающийся с result; при этом копируются только те элементы, которых нет в диапазоне [first2, last2) (этот диапазон также должен быть предварительно отсортирован). Возвращает позицию за последним скопированным элементом в полученном диапазоне. Таким образом, алгоритм реализует аналог теоретико-множественной операции разности, при котором в исходных наборах допускаются одинаковые, с точки зрения операции сравнения, элементы. Например, при обработке наборов (10, 10, 10, 20, 20, 40) и (10, 10, 30, 40) будет получен набор (10, 20, 20). Результирующий диапазон не должен перекрываться с любым из исходных. Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.

Сложность линейная (не более 2^*(N₁ + N₂) – 1 сравнений).

Копирует элементы предварительно отсортированного диапазона [first1, last1) в диапазон, начинающийся с result; при этом копируются только те элементы, которые присутствуют в диапазоне [first2, last2) (этот диапазон также должен быть предварительно отсортирован). Возвращает позицию за последним скопированным элементом в полученном диапазоне. Таким образом, алгоритм реализует аналог теоретико-множественной операции пересечения, при котором в исходных наборах допускаются одинаковые, с точки зрения операции сравнения, элементы. Например, при обработке наборов (10, 10, 10, 20, 20, 40) и (10, 10, 30, 40) будет получен набор (10, 10, 40). Результирующий диапазон не должен перекрываться с любым из исходных. Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.

Сложность линейная (не более 2^*(N₁ + N₂) – 1 сравнений).

Выполняет слияние предварительно отсортированных диапазонов [first1, last1) и [first2, last2) и копирует полученные отсортированные элементы в диапазон, начинающийся с result; при этом копируются только те элементы, которые присутствуют только в одном из исходных диапазонов. Возвращает позицию за последним скопированным элементом в полученном диапазоне. Таким образом, алгоритм реализует аналог теоретико-множественной операции симметричной разности, при котором в исходных наборах допускаются одинаковые, с точки зрения операции сравнения, элементы. Например, при обработке наборов (10, 10, 10, 20, 20, 40) и (10, 10, 30, 40) будет получен набор (10, 20, 20, 30). Используемый алгоритм слияния обладает теми же свойствами, что и алгоритм merge; в частности, он является устойчивым. Результирующий диапазон не должен перекрываться с любым из исходных. Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.

Сложность линейная (не более 2^*(N₁ + N₂) – 1 сравнений).

Выполняет слияние предварительно отсортированных диапазонов [first1, last1) и [first2, last2) и копирует полученные отсортированные элементы в диапазон, начинающийся с result; при этом равные элементы, присутствующие в каждом из исходных диапазонов, копируются только один раз (копируется элемент из первого диапазона). Возвращает позицию за последним скопированным элементом в полученном диапазоне. Таким образом, алгоритм реализует аналог теоретико-множественной операции объединения, при котором в исходных наборах допускаются одинаковые, с точки зрения операции сравнения, элементы. Например, при обработке наборов (10, 10, 10, 20, 20, 40) и (10, 10, 30, 40) будет получен набор (10, 10, 10, 20, 20, 30, 40). Используемый алгоритм слияния обладает теми же свойствами, что и алгоритм merge; в частности, он является устойчивым. Результирующий диапазон не должен перекрываться с любым из исходных. Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.

Сложность линейная (не более 2^*(N₁ + N₂) – 1 сравнений).

Случайным образом изменяет порядок элементов из диапазона [first, last). Требует явного указания генератора случайных чисел с равномерным распределением (набор стандартных генераторов содержится в заголовочном файле <random>). Алгоритм добавлен в стандарт C++11 с целью замены алгоритма random_shuffle, объявленного в этом стандарте устаревшим.

Сложность линейная (N + 1 перемещений элементов).

Сортирует элементы в диапазоне [first, last). Сортировка не является устойчивой, т. е. равные элементы могут не сохранять свой исходный порядок. Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.

Сложность: в среднем N^*log N сравнений.

Сортирует элементы в диапазоне [first, last) в предположении, что исходный диапазон образует кучу (см. алгоритм make_heap). Сортировка не является устойчивой, т. е. равные элементы могут не сохранять свой исходный порядок. Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.

Сложность: не более N^*log N сравнений.

Меняет местами элементы диапазона [first, last) так, чтобы все элементы, удовлетворяющие предикату pred, были расположены перед теми, которые ему не удовлетворяют. Относительный порядок следования элементов сохраняется. Алгоритм возвращает итератор, указывающий на первый элемент, для которого pred возвращает false (или итератор last, если таких элементов нет).

Сложность линейная (N вызовов pred и не более N^*log N перестановок даже в случае ограниченного объема памяти).

Сортирует элементы в диапазоне [first, last). Сортировка является устойчивой, т. е. равные элементы сохраняют свой исходный порядок. Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.

Сложность: в среднем N^*log N сравнений, если достаточно памяти (при ограниченном объеме памяти – не более N^*log N^*log N сравнений).

Меняет местами значения a и b.

Меняет местами элементы диапазона [first1, last1) с элементами диапазона, начинающегося с first2 и имеющего ту же длину, что и первый диапазон. Возвращает позицию за последним элементом второго диапазона. Диапазоны не должны перекрываться.

Сложность линейная (N₁ перестановок).

Присваивает новые значения всем элементам диапазона, начинающегося с result. В первой версии алгоритма используются значения unop(^*p), где p – итератор из диапазона [first, last); во второй версии алгоритма используются значения binop(^*p1, ^*p2), где p1 – итератор из диапазона [first1, last1), а p2 – итератор из диапазона, начинающегося с first2 и имеющего ту же длину, что и первый диапазон. Возвращает позицию за последним элементом полученного диапазона. Результирующий диапазон может совпадать с любым из входных диапазонов. Тип TRes возвращаемого значения операций unop и binop может отличаться от типа T их параметров.

Сложность линейная (N вызовов unop или N₁ вызовов binop).

«Удаляет» из диапазона [first, last) повторные вхождения соседних равных элементов (удаляется вся последовательность соседних равных элементов, кроме ее начального элемента). Возвращает итератор middle, определяющий конец диапазона [first, middle), содержащего преобразованный набор без соседних равных элементов. Относительный порядок оставшихся в диапазоне [first, middle) элементов сохраняется. В результате выполнения алгоритма значения элементов в диапазоне [middle, last) становятся неопределенными. Если исходный диапазон [first, last) предварительно отсортирован, то в полученном диапазоне [first, middle) содержатся уникальные значения (также отсортированные). Для сравнения элементов используется предикат pred(^*p1, ^*p2) или (по умолчанию) операция ==.

Сложность линейная (max{0, N – 1} сравнений).

Копирует элементы диапазона [first, last) в диапазон, начинающийся с result, удаляя повторные вхождения соседних равных элементов (удаляется вся последовательность соседних равных элементов, кроме ее начального элемента). Возвращает позицию за последним элементом полученного диапазона. Для сравнения элементов используется предикат pred(^*p1, ^*p2) или (по умолчанию) операция ==.

Сложность линейная (max{0, N – 1} сравнений).

Проверяет, содержится ли в диапазоне [first, last) значение value, и возвращает итератор, который указывает на элемент, расположенный после последнего элемента со значением value (если значение не найдено, то итератор указывает на позицию в диапазоне, в которую можно вставить value, не нарушая порядка сортировки). Содержимое диапазона должно быть предварительно отсортировано в соответствии с порядком, задаваемым предикатом comp(^*p1, ^*p2) или (по умолчанию) операцией <.

Сложность логарифмическая (не более log N + 1 сравнений).

Алгоритмы, описываемые в данном пункте, определены в заголовочном файле <numeric>.

Обрабатывает элементы из диапазона [first, last), добавляя их к переменной tmp типа TRes, инициализированной значением init, и возвращает полученный результат. При добавлении используется бинарная операция binop (в виде tmp = binop(tmp, ^*p)) или (по умолчанию) операция +. Первый параметр операции binop и ее возвращаемое значение должны иметь тип TRes, а второй параметр – тип T элементов исходной последовательности. В случае использования операции + возвращаемое значение имеет тип T. Функциональный объект binop не должен иметь побочных эффектов (в стандарте С++11 это ограничение снято).

Сложность линейная (N вызовов binop).

Обрабатывает пары соседних элементов из диапазона [first, last) с помощью операции binop (в виде binop(^*(p+1), ^*p)) или (по умолчанию) бинарной операции «–» (^*(p+1) – ^*p) и записывает полученные значения в диапазон вывода, начиная с result (первым записывается значение ^*first, затем результат binop(^*(first+1),^*first) и т. д.). Возвращает позицию за последним элементом полученного диапазона. Тип TRes возвращаемого значения для операции binop может отличаться от типа T элементов исходной последовательности. Если типы T и TRes совпадают, то итератор result может совпадать с first. Функциональный объект binop не должен иметь побочных эффектов (в стандарте С++11 это ограничение снято).

Сложность линейная (N – 1 вызовов binop).

Вычисляет сумму попарных произведений («внутреннее произведение») элементов двух диапазонов: [first1, last1) и диапазона такой же длины, начинающегося с first2 (переменная суммирования tmp инициализируется значением init). Вместо бинарных операций «+» и «^*» могут использоваться операции binop1 и binop2 соответственно: tmp = binop1(tmp, binop2(^*p1, ^*p2)). Параметры операции binop2 должны иметь тип T элементов исходной последовательности, а тип возвращаемого значения должен совпадать с типом второго параметра операции binop1. Первый параметр операции binop1 и ее возвращаемое значение должны иметь тип TRes. В случае использования операций «+» и «^*» возвращаемое значение алгоритма имеет тип T. Функциональные объекты binop1 и binop2 не должны иметь побочных эффектов (в стандарте С++11 это ограничение снято).

Сложность линейная (N₁ вызовов binop1 и binop2).

Заполняет диапазон [first, last) последовательно увеличивающимися значениями типа T, причем первое значение равно value, а все последующие полагаются равными результату очередного вызова операции инкремента ++value (название алгоритма заимствовано из языка программирования APL, в котором имеется одноименная операция).

Сложность линейная (N – 1 операций инкремента и N присваиваний).

Записывает частичные суммы (^*first, ^*first + ^*(first+1), (^*first + ^*(first+1)) + ^*(first+2), …) в диапазон, начинающийся с result. Вместо операции по умолчанию «+» может использоваться бинарная операция binop. Возвращает позицию за последним элементом полученного диапазона. Итератор result может совпадать с first. Функциональный объект binop не должен иметь побочных эффектов (в стандарте С++11 это ограничение снято).

Сложность линейная (N – 1 вызовов binop).

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

• back_insert_iterator (для вставки в конец контейнера)

Доступен для всех последовательных контейнеров. Может создаваться с помощью функции back_inserter(c), где c – контейнер. Каждое обращение к подобному итератору для записи в контейнер c элемента e приводит к вызову функции-члена c.push_back(e).

• front_insert_iterator (для вставки в начало контейнера)

Доступен для тех контейнеров, для которых реализована функция-член push_front(), т. е. для дека и списка. Может создаваться с помощью функции front_inserter(c), где c – контейнер. Каждое обращение к подобному итератору для записи в контейнер c элемента e приводит к вызову функции-члена c.push_front(e). В результате последовательность элементов, добавляемых с помощью данного итератора, будет размещена в начале контейнера в обратном порядке.

• insert_iterator (для вставки в любую позицию контейнера)

Доступен для всех контейнеров. Может создаваться с помощью функции inserter(c, pos), где c – контейнер, а pos – итератор данного контейнера, определяющий место вставки. Каждое обращение к подобному итератору для записи в контейнер c элемента e приводит к выполнению операторов pos = c.insert(pos, e); ++pos; таким образом, следующая вставка будет выполняться за вставленным ранее элементом. В частности, вставка с помощью итератора inserter(c, c.begin()) отличается от вставки с помощью итератора front_inserter(c) тем, что в первом случае вставляемые элементы будут располагаться в контейнере в исходном порядке. Применение итераторов inserter(c, c.end()) и back_inserter(c) приводит к одинаковому результату.

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

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

При использовании компилятора gcc этот оператор решает поставленную задачу, однако в Visual Studio он приводит к зависанию программы.

Если требуется продублировать все элементы списка, записав их в конец в обратном порядке, то вариант

решает задачу в gcc, а в Visual Studio создает список, в котором последний элемент исходного списка появляется не 2, а 3 раза. Например, список 1, 2, 3 преобразуется в 1, 2, 3, 3, 3, 2, 1.

В то же время при дублировании элементов списка в его начало проблем не возникает; в частности, первая из рассмотренных задач успешно решается в Visual Studio оператором

а для решения второй можно использовать два действия:

Таким образом, можно сформулировать следующие рекомендации по безопасному использованию итераторов вставки:

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

• если требуется преобразовать и вставить данные из одной части контейнера в другую его часть, то следует принимать во внимание вид контейнера и расположение позиции вставки и исходных данных. Если позиция вставки и диапазон исходных данных «отграничены» друг от друга, то в случае списка действие всегда является безопасным, а в случае вектора оно будет безопасным, если, в дополнение к предыдущему условию, диапазон исходных данных расположен до позиции вставки и, кроме того, емкость вектора позволит завершить процедуру вставки без перераспределения памяти. В случае дека указанное действие никогда не является безопасным;

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

1.4. Стандартные функциональные объекты

Стандартные функциональные объекты определены в пространстве имен std (за исключением объектов-заменителей _1, _2, _3, …, определенных в пространстве имен std::placeholders). Для возможности работы с ними надо подключить заголовочный файл <functional>.

В настоящем разделе описывается большинство стандартных функциональных объектов, включая функциональные адаптеры (см. п. 1.4.2) и объекты для арифметических и логических операций (см. п. 1.4.3).

Раздел стандартной библиотеки шаблонов, связанный со стандартными функциональными объектами, в стандарте C++11 был подвергнут наиболее существенным изменениям. В то время как для контейнеров и алгоритмов нововведения стандарта C++11 связаны в основном с добавлением новых возможностей (и небольшими модификациями прежних), практически все прежние функциональные адаптеры в стандарте C++11 были объявлены устаревшими и заменены новыми вариантами. В п. 1.4.2, посвященном функциональным адаптерам, описаны как прежние их варианты (они помечены словом deprecated), так и новые (помечены текстом C++11).

Интересно отметить, что адаптеры-инверторы not1 и not2, будучи объявлены устаревшими, не получили в стандарте C++11 должной замены; их новый вариант not_fn предполагается включить лишь в стандарт C++17. По указанной причине, хотя в данной книге не рассматриваются нововведения языка C++, добавленные после стандарта C++11, для адаптера not_fn было сделано исключение.

Объекты-заменители (placeholders), определенные в пространстве имен std::placeholders и используемые в функциональном адаптере-связывателе bind. При указании в программе директивы using namespace std::placeholders; она должна располагаться после подключения заголовочного файла <functional>.

Шаблон класса, который должен быть базовым для классов, реализующих функциональный объект в виде бинарной операции () с параметрами типа TArg1 и TArg2 и возвращаемым значением типа TRes.

Функциональный адаптер-связыватель (binder), принимающий функциональный объект op(x1, x2, x3, …, xN) с N параметрами и возвращающий функциональный объект с M параметрами (y1, y2, …, yM), где M ≤ N. Среди параметров arg1, …, argN должно быть M заменителей вида _1, _2, _3, …, определяющих положение и порядок параметров нового функционального объекта (_1 соответствует параметру y1, _2 – параметру y2 и т. д.). Параметры из списка arg1, …, argN, не являющиеся заменителями, задают фиксированные значения для соответствующих параметров исходного функционального объекта.

Например, в случае вызова bind(op, a1, _3, _2, a4, _1) на основе объекта op(x1, x2, x3, x4, x5) с пятью параметрами создается объект с тремя параметрами (y1, y2, y3), который определяется через исходный объект следующим образом: op(a1, y3, y2, a4, y1) (первый и четвертый параметры исходного функционального объекта получают фиксированные значения a1 и a4 соответственно).

В отличие от старых связывателей bind1st и bind2nd связыватель bind может принимать в качестве своего первого параметра непосредственно функции-члены классов (для которых не требуется вызывать дополнительный функциональный адаптер mem_fn).

Функциональный адаптер-связыватель (binder), принимающий функциональный объект op(x1, x2) с двумя параметрами и возвращающий функциональный объект op(arg1, x2) с одним параметром x2 (первый параметр исходного функционального объекта получает фиксированное значение arg1).

Функциональный адаптер-связыватель (binder), принимающий функциональный объект op(x1, x2) с двумя параметрами и возвращающий функциональный объект op(x1, arg2) с одним параметром x1 (второй параметр исходного функционального объекта получает фиксированное значение arg2).

Шаблон, являющийся полиморфной оболочкой, обобщающей понятие указателя на функцию. Может использоваться в качестве базового для классов, реализующих функциональный объект в виде операции () с параметрами типа (TArg1, TArg2, …) и возвращаемым значением типа TRes. Число параметров может быть произвольным.

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

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

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

Функциональный адаптер-инвертор (negator), принимающий функциональный объект-предикат pred(x1, x2, …) с произвольным числом параметров и возвращающий функциональный объект, являющийся логическим отрицанием объекта pred: !pred(x1, x2, …).

Функциональный адаптер-инвертор (negator), принимающий функциональный объект-предикат pred(x) с одним параметром и возвращающий функциональный объект, являющийся логическим отрицанием объекта pred: !pred(x).

Инвертор not1 не может применяться к функциональному объекту, возвращаемому связывателем bind: комбинация not1(bind(pred, …)) приводит к ошибке компиляции. В то же время допустимыми являются комбинации not1(bind1st(pred, arg1)) и not1(bind2nd(pred, arg2)).

Функциональный адаптер-инвертор (negator), принимающий функциональный объект-предикат pred(x1, x2) с двумя параметрами и возвращающий функциональный объект, являющийся логическим отрицанием объекта pred: !pred(x1, x2).

Инвертор not2 не может применяться к функциональному объекту, возвращаемому связывателем bind: комбинация not2(bind(pred, …)) приводит к ошибке компиляции. В то же время допустимыми являются комбинации bind(not2(pred), …), bind1st(not2(pred), arg1) и bind2nd(not2(pred), arg2).

Шаблон класса, который должен быть базовым для классов, реализующих функциональный объект в виде унарной операции () с параметром типа TArg и возвращаемым значением типа TRes.