|
C++ для начинающих |
21. Обобщенные алгоритмы в алфавитном порядке
В этом приложении мы рассмотрим все алгоритмы. Мы решили расположить их в алфавитном порядке (за небольшими исключениями), чтобы проще было найти нужный. Каждый алгоритм представлен в следующем виде: сначала описывается прототип функции, затем сам алгоритм, причем особое внимание уделяется интуитивно неочевидным особенностям, и, наконец, приводится пример программы, показывающий, как можно данный алгоритм использовать.
Первыми двумя аргументами всех обобщенных алгоритмов (естественно, не без исключений) является пара итераторов, обычно first и last, обозначающих диапазон элементов внутри контейнера или встроенного массива, над которым работает алгоритм. Этот диапазон (часто называемый интервалом с включенной левой границей), как правило, записывается в виде:
// следует читать: включая first и все последующие // элементы до last, но не включая сам last [ first, last )
Это означает, что диапазон начинается с first и заканчивается last, однако сам элемент last не включается. Если
first == last
то говорят, что диапазон пуст.
К паре итераторов предъявляется такое требование: last должен быть достижим, если начать с first и последовательно применять оператор инкремента. Однако компилятор не может проверить выполнение данного ограничения. Если требование не будет выполнено, поведение программы не определено; обычно это заканчивается ее крахом и дампом памяти.
В объявлении каждого алгоритма подразумевается минимальная поддержка, которую должны обеспечить итераторы (краткое обсуждение пяти категорий итераторов см. в разделе 12.4). Например, алгоритм find(), реализующий однопроходный обход контейнера и выполняющий только чтение, требует итератора чтения InputIterator. Ему также можно передать одно- или двунаправленный итератор или итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что подобные ошибки (при передаче итератора неподходящей категории) будут обнаружены компилятором, поскольку категории итераторов - это не сами типы, а лишь параметры, которыми конкретизируется шаблон функции.
Некоторые алгоритмы существуют в нескольких вариантах: в одном используется тот или иной встроенный оператор, а в другом - объект-функция или указатель на функцию, реализующие альтернативу этому оператору. Например, алгоритм unique() по умолчанию сравнивает соседние элементы контейнера с помощью оператора равенства, определенного в классе, к которому данные элементы принадлежат. Но если в этом классе нет оператора равенства или мы хотим сравнивать элементы иным способом, то можем передать объект-функцию или указатель на функцию, поддерживающую нужную семантику. Есть и такие алгоритмы, которые выполняют похожие действия, но имеют различные имена. Так, имена предикатных версий алгоритмов всегда заканчиваются на _if, скажем find_if(). Например, есть вариант алгоритма replace(), где используется встроенный оператор равенства, и вариант с именем replace_if(), которому передается предикатный объект-функция или указатель на функцию-предикат.
Алгоритмы, модифицирующие контейнер, обычно также существуют в двух вариантах: один осуществляет модификацию по месту, а второй возвращает копию с внесенными изменениями. Так, есть алгоритмы replace() и replace_copy(). Однако вариант с копированием (его имя всегда содержит слово _copy) имеется не для каждого алгоритма, модифицирующего контейнер. К примеру, для алгоритмов sort() его нет. В таких случаях, если нужно, чтобы алгоритм работал с копией, мы должны создать ее самостоятельно и передать в качестве аргумента.
Для использования любого обобщенного алгоритма в программу необходимо включить заголовочный файл
#include <algorithm>
Для употребления любого из четырех численных алгоритмов: adjacent_difference(), accumulate(), inner_product() и partial_sum() - нужно включить также файл
#include <numeric>
Приведенные в этом Приложении примеры программ, в которых используются алгоритмы и различные контейнерные типы, отражают существующую на момент написания книги реализацию. Применение библиотеки ввода/вывода iostream следует соглашениям, установленным до принятия стандарта; скажем, в программу включается заголовочный файл iostream.h, а не iostream. Шаблоны не поддерживают аргументы по умолчанию. Чтобы программа работала на системе, имеющейся у вас, возможно, придется изменить некоторые объявления.
Другое, более подробное, чем в этой книге, описание обобщенных алгоритмов можно найти в работе [MUSSER96], правда, оно несколько отстает от окончательного варианта стандартной библиотеки C++.
Алгоритм accumulate()
template < class InputIterator, class Type >
Type accumulate(
InputIterator first, InputIterator last,
Type init );
template < class InputIterator, class Type,
class BinaryOperation >
Type accumulate(
InputIterator first, InputIterator last,
Type init, BinaryOperation op );
Первый вариант accumulate() вычисляет сумму значений элементов последовательности из диапазона, ограниченного парой итераторов [first,last), с начальным значением, которое задано параметром init. Например, если дана последовательность {1,1,2,3,5,8} и начальное значение 0, то результатом работы алгоритма будет 20. Во втором варианте вместо оператора сложения к элементам применяется переданная бинарная операция. Если бы мы передали алгоритму accumulate() объект-функцию times Первый вариант adjacent_difference() создает новую последовательность, в которой значение каждого элемента, кроме первого, равно разности между текущим и предыдущим элементами исходной последовательности. Например, если дано {0,1,1,2,3,5,8}, то первым элементом новой последовательности будет копия: 0. Вторым - разность первых двух элементов исходной последовательности: 1. Третий элемент равен разности третьего и второго элементов: 1-1=0, и т.д. В результате мы получим последовательность {0,1,0,1,1,2,3}.
Во втором варианте разность соседних элементов вычисляется с помощью указанной бинарной операции. Возьмем ту же исходную последовательность и передадим объект-функцию times<int>. Как и раньше, первый элемент просто копируется. Второй элемент - это произведение первого и второго элементов исходной последовательности; он тоже равен 0. Третий элемент - произведение второго и третьего элементов исходной последовательности: 1 * 1 = 1, и т.д. Результат - {0,1,2,6,15,40}.
В обоих вариантах итератор OutputIterator указывает на элемент, расположенный за последним элементом новой последовательности. adjacent_difference() - это один из численных алгоритмов, для его использования в программу необходимо включить заголовочный файл adjacent_find() ищет первую пару одинаковых соседних элементов в диапазоне, ограниченном итераторами [first,last). Если соседние дубликаты найдены, то алгоритм возвращает однонаправленный итератор, указывающий на первый элемент пары, в противном случае возвращается last. Например, если дана последовательность {0,1,1,2,2,4}, то будет найдена пара [1,1] и возвращен итератор, указывающий на первую единицу.
binary_search() ищет значение value в отсортированной последовательности, ограниченной парой итераторов [first,last). Если это значение найдено, возвращается true, иначе - false. В первом варианте предполагается, что контейнер отсортирован с помощью оператора "меньше". Во втором варианте порядок определяется указанным объектом-функцией.
copy() копирует последовательность элементов, ограниченную парой итераторов [first,last), в другой контейнер, начиная с позиции, на которую указывает first2. Алгоритм возвращает итератор, указывающий на элемент второго контейнера, следующий за последним вставленным. Например, если дана последовательность {0,1,2,3,4,5}, мы можем сдвинуть элементы на один влево с помощью такого вызова:
copy() начинает копирование со второго элемента ia, копируя 1 в первую позицию, и так далее, пока каждый элемент не окажется в позиции на одну левее исходной.
copy_backward() ведет себя так же, как copy(), только элементы копируются в обратном порядке: копирование начинается с last1-1 и продолжается до first. Кроме того, элементы помещаются в целевой контейнер с конца, от позиции last2-1, пока не будет скопировано last1-first элементов.
Например, если дана последовательность {0,1,2,3,4,5}, мы можем скопировать последние три элемента (3,4,5) на место первых трех (0,1,2), установив first равным адресу значения 0, last1 - адресу значения 3, а last2 - адресу значения 5. Тогда элемент 5 попадает на место элемента 2, элемент 4 - на место 1, а элемент 3 - на место 0. В результате получим последовательность {3,4,5,3,4,5}.
count() сравнивает каждый элемент со значением value в диапазоне, ограниченном парой итераторов [first,last), с помощью оператора равенства. Алгоритм возвращает число элементов, равных value. (Отметим, что в имеющейся у нас реализации стандартной библиотеки поддерживается более ранняя спецификация count().)
count_if() применяет предикат pred к каждому элементу из диапазона, ограниченного парой итераторов [first,last). Алгоритм сообщает, сколько раз предикат оказался равным true.
equal() возвращает true, если обе последовательности одинаковы в диапазоне, ограниченном парой итераторов [first,last). Если вторая последовательность содержит дополнительные элементы, они игнорируются. Чтобы убедиться в тождественности данных последовательностей, необходимо написать:
или воспользоваться оператором равенства, определенном в классе самого контейнера: vec1 == vec2. Если второй контейнер содержит меньше элементов, чем первый, и алгоритму приходится просматривать элементы за концом контейнера, то поведение программы не определено. По умолчанию для сравнения применяется оператор равенства в классе элементов контейнера, а во втором варианте алгоритма - указанный предикат pred.
equal_range() возвращает пару итераторов: первый представляет значение итератора, возвращаемое алгоритмом lower_bound(), второй - алгоритмом upper_bound(). (О семантике этих алгоритмов рассказано в их описаниях.) Например, дана последовательность:
Обращение к equal_range() со значением 21 возвращает пару итераторов, в которой оба указывают на значение 22. Обращение же со значением 22 возвращает пару итераторов, где first указывает на 22, а second - на 23. В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера; во втором - предикат comp.
fill() помещает копию значения value в каждый элемент диапазона, ограниченного парой итераторов [first,last).
fill_n() присваивает count элементам из диапазона [first,first+count) значение value.
Элементы из диапазона, ограниченного парой итераторов [first,last), сравниваются со значением value с помощью оператора равенства, определенного для типа элементов контейнера. Как только соответствие найдено, поиск прекращается. find() возвращает итератор типа InputIterator, указывающий на найденный элемент; в противном случае возвращается last.
К каждому элементу из диапазона [first,last) последовательно применяется предикат pred. Если он возвращает true, поиск прекращается. find_if() возвращает итератор типа InputIterator, указывающий на найденный элемент; в противном случае возвращается last.
В последовательности, ограниченной итераторами [first1,last1), ведется поиск последнего вхождения последовательности, ограниченной парой [first2,last2). Например, если первая последовательность - это Mississippi, а вторая - ss, то find_end() возвращает итератор, указывающий на первую s во втором вхождении ss. Если вторая последовательность не входит в первую, то возвращается last1. В первом варианте используется оператор равенства, определенный для типа элементов контейнера, а во втором - бинарный предикат, переданный пользователем.
Последовательность, ограниченная парой [first2,last2), содержит элементы, поиск которых ведется в последовательности, ограниченной итераторами [first1,last1). Допустим, нужно найти первую гласную в последовательности символов synesthesia. Для этого определим вторую последовательность как aeiou. find_first_of() возвращает итератор, указывающий на первое вхождение любого элемента последовательности гласных букв, в данном случае e. Если же первая последовательность не содержит ни одного элемента из второй, то возвращается last1. В первом варианте используется оператор равенства, определенный для типа элементов контейнера, а во втором - бинарный предикат pred.
for_each() применяет объект-функцию func к каждому элементу в диапазоне [first,last). func не может изменять элементы, поскольку итератор записи не гарантирует поддержки присваивания. Если же модификация необходима, следует воспользоваться алгоритмом transform(). func может возвращать значение, но оно игнорируется.
generate() заполняет диапазон, ограниченный парой итераторов [first,last), путем последовательного вызова gen, который может быть объектом-функцией или указателем на функцию.
generate_n() заполняет последовательность, начиная с first, n раз вызывая gen, который может быть объектом-функцией или указателем на функцию.
includes() проверяет, каждый ли элемент последовательности [first1,last1) входит в последовательность [first2,last2). Первый вариант предполагает, что последовательности отсортированы в порядке, определяемом оператором “меньше”; второй - что порядок задается параметром-типом comp.
Первый вариант суммирует произведения соответственных членов обеих последовательностей и прибавляет результат к начальному значению init. Первая последовательность ограничена итераторами [first1,last1), вторая начинается с first2 и обходится синхронно с первой. Например, если даны последовательности {2,3,5,8} и {1,2,3,4}, то результат вычисляется следующим образом:
Если начальное значение равно 0, алгоритм вернет 55.
Во втором варианте вместо сложения используется бинарная операция op1, а вместо умножения - бинарная операция op1. Например, если для приведенных выше последовательностей применить вычитание в качестве op1 и сложение в качестве op2, то результат будет вычисляться так:
inner_product() - это один из численных алгоритмов. Для его использования в программу необходимо включить заголовочный файл inplace_merge() объединяет две соседние отсортированные последовательности, ограниченные парами итераторов [first,middle) и [middle,last). Результирующая последовательность затирает исходные, начиная с позиции first. В первом варианте для упорядочения элементов используется оператор “меньше”, определенный для типа элементов контейнера, во втором - операция сравнения, переданная программистом.
lexicographical_compare() сравнивает соответственные пары элементов из двух последовательностей, ограниченных диапазонами [first1,last1) и [first2,last2). Сравнение продолжается, пока не будет найдена первая пара различных элементов, не достигнута пара [last1,last2] или хотя бы один из элементов last1 или last2 (если последовательности имеют разные длины). При обнаружении первой пары различных элементов алгоритм возвращает:
если меньше элемент первой последовательности, то true, иначе false;
если last1 достигнут, а last2 нет, то true;
если last2 достигнут, а last1 нет, то false;
если достигнуты и last1, и last2 (т.е. все элементы одинаковы), то false. Иными словами, первая последовательность лексикографически не меньше второй.
Например, даны такие последовательности:
В них первая пара элементов одинакова, а вторая различна. Pooh считается больше, чем Pooch, так как c лексикографически меньше h (такой способ сравнения применяется при составлении словарей). В этом месте алгоритм заканчивается (третья пара элементов не сравнивается). Результатом сравнения будет false.
Во втором варианте алгоритма вместо оператора сравнения используется предикатный объект:
lower_bound() возвращает итератор, указывающий на первую позицию в отсортированной последовательности, ограниченной диапазоном [first,last), в которую можно вставить значение value, не нарушая упорядоченности. В этой позиции находится значение, большее либо равное value. Например, если дана такая последовательность:
то обращение к lower_bound() с аргументом value=21 возвращает итератор, указывающий на 23. Обращение с аргументом 22 возвращает тот же итератор. В первом варианте алгоритма используется оператор “меньше”, определенный для типа элементов контейнера, а во втором для упорядочения элементов применяется объект comp.
max() возвращает наибольшее из двух значений aval и bval. В первом варианте используется оператор "больше", определенный в классе Type; во втором - операция сравнения comp.
max_element() возвращает итератор, указывающий на элемент, который содержит наибольшее значение в последовательности, ограниченной диапазоном [first,last). В первом варианте используется оператор "больше", определенный для типа элементов контейнера; во втором - операция сравнения comp.
min() возвращает меньшее из двух значений aval и bval. В первом варианте используется оператор “меньше”, определенный для типа Type; во втором - операция сравнения comp.
max_element() возвращает итератор, указывающий на элемент, который содержит наименьшее значение последовательности, ограниченной диапазоном [first,last). В первом варианте используется оператор "меньше", определенный для типа элементов контейнера; во втором - операция сравнения comp.
merge() объединяет две отсортированные последовательности, ограниченные диапазонами [first1,last1) и [first2,last2), в единую отсортированную последовательность, начинающуюся с позиции result. Результирующий итератор записи указывает на элемент за концом новой последовательности. В первом варианте для упорядочения используется оператор "меньше", определенный для типа элементов контейнера; во втором - операция сравнения comp.
mismatch() сравнивает две последовательности и находит первую позицию, где элементы различны. Возвращается пара итераторов, каждый из которых указывает на эту позицию в соответствующей последовательности. Если все элементы одинаковы, то каждый итератор в паре указывает на элемент last в своем контейнере. Так, если даны последовательности meet и meat, то оба итератора указывают на третий элемент. В первом варианте для сравнения элементов применяется оператор равенства, а во втором - операция сравнения, заданная пользователем. Если вторая последовательность длиннее первой, "лишние" элементы игнорируются; если же она короче, то поведение программы не определено.
next_permutation() берет последовательность, ограниченную диапазоном [first,last), и, считая ее перестановкой, возвращает следующую за ней (о том, как упорядочиваются перестановки, говорилось в разделе 12.5). Если следующей перестановки не существует, алгоритм возвращает false, иначе - true. В первом варианте для определения следующей перестановки используется оператор “меньше” в классе элементов контейнера, а во втором - операция сравнения comp. Последовательные обращения к next_permutation() генерируют все возможные перестановки только в том случае, когда исходная последовательность отсортирована. Если бы в показанной ниже программе мы предварительно не отсортировали строку musil, получив ilmsu, то не удалось бы сгенерировать все перестановки.
nth_element() переупорядочивает последовательность, ограниченную диапазоном [first,last), так что все элементы, меньшие чем тот, на который указывает итератор nth, оказываются перед ним, а все большие элементы - после. Например, если есть массив
то вызов nth_element(), в котором nth указывает на седьмой элемент (его значение равно 26):
генерирует последовательность, в которой семь элементов, меньших 26, оказываются слева от 26, а четыре элемента, больших 26, справа:
При этом не гарантируется, что элементы, расположенные по обе стороны от nth, упорядочены. В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, во втором - бинарная операция сравнения, заданная программистом.
partial_sort() сортирует часть последовательности, укладывающуюся в диапазон [first,middle). Элементы в диапазоне [middle,last) остаются неотсортированными. Например, если дан массив
то вызов partial_sort(),где middle указывает на шестой элемент:
генерирует последовательность, в которой наименьшие пять (т.е. middle-first) элементов отсортированы:
Элементы от middle до last-1 не расположены в каком-то определенном порядке, хотя значения каждого из них лежат вне отсортированной последовательности. В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция сравнения comp.
partial_sort_copy() ведет себя так же, как partial_sort(), только частично упорядоченная последовательность копируется в контейнер, ограниченный диапазоном [result_first,result_last] (если мы задаем отдельный контейнер для копирования результата, то в нем оказывается упорядоченная последовательность). Например, даны два массива:
Тогда обращение к partial_sort_copy(), где в качестве middle указан восьмой элемент:
заполняет массив ia2 пятью отсортированными элементами: {12,15,17,19,20}. Оставшиеся два элемента отсортированы не будут.
Первый вариант partial_sum() создает из последовательности, ограниченной диапазоном [first,last), новую последовательность, в которой значение каждого элемента равно сумме всех предыдущих, включая и данный. Так, из последовательности {0,1,1,2,3,5,8} будет создана {0,1,2,4,7,12,20}, где, например, четвертый элемент равен сумме трех предыдущих (0,1,1) и его самого (2), что дает значение 4.
Во втором варианте вместо оператора сложения используется бинарная операция, заданная программистом. Предположим, мы задали последовательность {1,2,3,4} и объект-функцию times<int>. Результатом будет {1,2,6,24}. В обоих случаях итератор записи OutputIterator указывает на элемент за последним элементом новой последовательности.
partial_sum() - это один из численных алгоритмов. Для его использования необходимо включить в программу стандартный заголовочный файл <numeric>.
partition() переупорядочивает элементы в диапазоне [first,last). Все элементы, для которых предикат pred равен true, помещаются перед элементами, для которых он равен false. Например, если дана последовательность {0,1,2,3,4,5,6} и предикат, проверяющий целое число на четность, то мы получим две последовательности - {0,2,4,6} и {1,3,5}. Хотя гарантируется, что четные элементы будут помещены перед нечетными, их первоначальное взаимное расположение может и не сохраниться, т.е. 4 может оказаться перед 2, а 5 перед 1. Сохранение относительного порядка обеспечивает алгоритм stable_partition(), рассматриваемый ниже.
prev_permutation() берет последовательность, ограниченную диапазоном [first,last), и, рассматривая ее как перестановку, возвращает предшествующую ей (о том, как упорядочиваются перестановки, говорилось в разделе 12.5). Если предыдущей перестановки не существует, алгоритм возвращает false, иначе true. В первом варианте для определения предыдущей перестановки используется оператор "меньше" для типа элементов контейнера, а во втором - бинарная операция сравнения, заданная программистом.
random_shuffle() переставляет элементы из диапазона [first,last) в случайном порядке. Во втором варианте можно передать объект-функцию или указатель на функцию, генерирующую случайные числа. Ожидается, что генератор rand возвращает значение типа double в интервале [0,1].
remove() удаляет из диапазона [first,last) все элементы со значением value. Этот алгоритм (как и remove_if()) на самом деле не исключает элементы из контейнера (т.е. размер контейнера сохраняется), а перемещает каждый оставляемый элемент в очередную позицию, начиная с first. Возвращаемый итератор указывает на элемент, следующий за позицией, в которую помещен последний неудаленный элемент. Рассмотрим, например, последовательность {0,1,0,2,0,3,0,4}. Предположим, что нужно удалить все нули. В результате получится последовательность {1,2,3,4,0,4,0,4}. 1 помещена в первую позицию, 2 - во вторую, 3 - в третью и 4 - в четвертую. Элементы, начиная с 0 в пятой позиции, - это "отходы" алгоритма. Возвращенный итератор указывает на 0 в пятой позиции. Обычно этот итератор затем передается алгоритму erase(), который удаляет неподходящие элементы. (При работе со встроенным массивом лучше использовать алгоритмы remove_copy() и remove_copy_if(), а не remove() и remove_if(), поскольку его размер невозможно изменить)
remove_copy() копирует все элементы, кроме имеющих значение value, в контейнер, на начало которого указывает result. Возвращаемый итератор указывает на элемент за последним скопированным. Исходный контейнер не изменяется.
remove_if() удаляет из диапазона [first,last) все элементы, для которых значение предиката pred равно true. remove_if() (как и remove()) фактически не исключает удаленные элементы из контейнера. Вместо этого каждый оставляемый элемент перемещается в очередную позицию, начиная с first. Возвращаемый итератор указывает на элемент, следующий за позицией, в которую помещен последний неудаленный элемент. Обычно этот итератор затем передается алгоритму erase(), который удаляет неподходящие элементы. (Для встроенных массивов лучше использовать алгоритм remove_copy_if().)
remove_copy_if() копирует все элементы, для которых предикат pred равен false, в контейнер, на начало которого указывает итератор result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
replace() заменяет в диапазоне [first,last) все элементы со значением old_value на new_value.
replace_copy() ведет себя так же, как replace(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
replace_if() заменяет значения всех элементов в диапазоне [first,last), для которых предикат pred равен true, на new_value.
replace_copy_if() ведет себя так же, как replace_if(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
reverse() меняет порядок элементов контейнера в диапазоне [first,last) на противоположный. Например, если есть последовательность {0,1,1,2,3}, то после обращения получится {3,2,1,1,0}.
Алгоритм reverse_copy()
template< class BidirectionalIterator, class OutputIterator >
OutputIterator
reverse_copy( BidirectionalIterator first,
BidirectionalIterator last, OutputIterator result );
reverse_copy() ведет себя так же, как reverse(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
#include <algorithm>
#include <list>
#include <string>
#include <iostream.h>
/* печатается:
Исходная последовательность строк:
Signature of all things I am here to
read seaspawn and seawrack that rusty boot
Последовательность строк после применения reverse():
boot rusty that seawrack and seaspawn read to
here am I things all of Signature
*/
class print_elements {
public:
void operator()( string elem ) {
cout << elem
<< ( _line_cnt++%8 ? " " : "\n\t" );
}
static void reset_line_cnt() { _line_cnt = 1; }
private:
static int _line_cnt;
};
int print_elements::_line_cnt = 1;
int main()
{
string sa[] = { "Signature", "of", "all", "things",
"I", "am", "here", "to", "read",
"seaspawn", "and", "seawrack", "that",
"rusty", "boot"
};
list< string, allocator > slist( sa, sa+15 );
cout << "Исходная последовательность строк:\n\t";
for_each( slist.begin(), slist.end(), print_elements() );
cout << "\n\n";
reverse( slist.begin(), slist.end() );
print_elements::reset_line_cnt();
cout << "Последовательность строк после применения reverse():\n\t";
for_each( slist.begin(), slist.end(), print_elements() ); cout << "\n";
list< string, allocator > slist_copy( slist.size() );
reverse_copy( slist.begin(), slist.end(),
slist_copy.begin() );
}
rotate() перемещает элементы из диапазона [first,last) в конец контейнера. Элемент, на который указывает middle, становится первым. Например, для слова "hissboo" вращение вокруг буквы 'b' превращает слово в "boohiss".
rotate_copy() ведет себя так же, как rotate(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
Если даны два диапазона, то search() возвращает итератор, указывающий на первую позицию в диапазоне [first1,last1), начиная с которой второй диапазон входит как подпоследовательность. Если подпоследовательность не найдена, возвращается last1. Например, в слове Mississippi подпоследовательность iss встречается дважды, и search() возвращает итератор, указывающий на начало первого вхождения. В первом варианте для сравнения элементов используется оператор равенства, во втором - указанная программистом операция сравнения.
search_n() ищет в последовательности [first,last) подпоследовательность, состоящую из count повторений значения value. Если она не найдена, возвращается last. Например, для поиска подстроки ss в строке Mississippi следует задать value равным 's', а count равным 2. Если же нужно найти две расположенные подряд подстроки ssi, то value задается равным "ssi", а count снова 2. search_n() возвращает итератор на первый элемент со значением value. В первом варианте для сравнения элементов используется оператор равенства, во втором - указанная программистом операция сравнения.
set_difference() строит отсортированную последовательность из элементов, имеющихся в первой последовательности [first1,last1), но отсутствующих во второй - [first2,last2). Например, разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора "меньше", определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
set_intersection() строит отсортированную последовательность из элементов, встречающихся в обеих последовательностях - [first1,last1) и [first2,last2). Например, пересечение последовательностей {0,1,2,3} и {0,2,4,6} равно {0,2}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора "меньше", определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
set_symmetric_difference() строит отсортированную последовательность из элементов, которые встречаются только в первой последовательности [first1,last1) или только во второй - [first2,last2). Например, симметрическая разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3,4,6}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
set_union() строит отсортированную последовательность из элементов, которые встречаются либо в первой последовательности [first1,last1), либо во второй - [first2,last2), либо в обеих. Например, объединение последовательностей {0,1,2,3} и {0,2,4,6} равно {0,1,2,3,4,6}. Если элемент присутствует в обеих последовательностях, то копируется экземпляр из первой. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
sort() переупорядочивает элементы в диапазоне [first,last) по возрастанию, используя оператор "меньше", определенный для типа элементов контейнера. Во втором варианте порядок устанавливается операцией сравнения comp. (Для сохранения относительного порядка равных элементов пользуйтесь алгоритмом stable_sort().) Мы не приводим пример, специально иллюстрирующий применение алгоритма sort(), поскольку его можно найти во многих других программах, в частности в binary_search(), equal_range() и inplace_merge().
stable_partition() ведет себя так же, как partition(), но гарантированно сохраняет относительный порядок элементов контейнера. Вот та же программа, что и для алгоритма partition(), но с использованием stable_partition().
stable_sort() ведет себя так же, как sort(), но гарантированно сохраняет относительный порядок равных элементов контейнера. Второй вариант упорядочивает элементы на основе заданной программистом операции сравнения comp.
swap_ranges() обменивает элементы из диапазона [first1,last) с элементами другого диапазона, начиная с first2. Эти последовательности могут находиться в одном контейнере или в разных. Поведение программы не определено, если они находятся в одном контейнере и при этом частично перекрываются, а также в случае, когда вторая последовательность короче первой. Алгоритм возвращает итератор, указывающий на элемент за последним переставленным.
Первый вариант transform() генерирует новую последовательность, применяя операцию op к каждому элементу из диапазона [first,last). Например, если есть последовательность {0,1,1,2,3,5} и объект-функция Double, удваивающий свой аргумент, то в результате получим {0,2,2,4,6,10}.
Второй вариант генерирует новую последовательность, применяя бинарную операцию bop к паре элементов, один из которых взят из диапазона [first1,last1), а второй - из последовательности, начинающейся с first2. Поведение программы не определено, если во второй последовательности меньше элементов, чем в первой. Например, для двух последовательностей {1,3,5,9} и {2,4,6,8} и объекта-функции AddAndDouble, которая складывает два элемента и удваивает их сумму, результатом будет {6,14,22,34}.
Оба варианта transform() помещают результирующую последовательность в контейнер с элемента, на который указывает итератор result. Этот итератор может адресовать и элемент любого из входных контейнеров, в таком случае исходные элементы будут заменены на результат выполнения transform(). Выходной итератор указывает на элемент за последним помещенным в результирующий контейнер.
Все группы равных соседних элементов заменяются одним. В первом варианте при сравнении используется оператор равенства, определенный для типа элементов в контейнере. Во втором варианте два элемента равны, если бинарный предикат pred для них возвращает true. Таким образом, слово mississippi будет преобразовано в misisipi. Обратите внимание, что три буквы 'i' не являются соседними, поэтому они не заменяются одной, как и две пары несоседних 's'. Если нужно, чтобы все одинаковые элементы были заменены одним, придется сначала отсортировать контейнер.
На самом деле поведение unique() интуитивно не совсем очевидно и напоминает remove(). В обоих случаях размер контейнера не изменяется: каждый уникальный элемент помещается в очередную позицию, начиная с first.
В нашем примере физически будет получено слово misisipippi, где ppi - остаток, "отходы" алгоритма. Возвращаемый итератор указывает на начало этого остатка и обычно передается алгоритму erase() для удаления ненужных элементов. (Поскольку для встроенного массива операция erase() не поддерживается, то лучше воспользоваться алгоритмом unique_copy().)
unique_copy() копирует входной контейнер в выходной, заменяя группы одинаковых соседних элементов на один элемент с тем же значением. О том, что понимается под равными элементами, говорилось при описании алгоритма unique(). Чтобы все дубликаты были гарантированно удалены, входной контейнер необходимо предварительно отсортировать. Возвращаемый итератор указывает на элемент за последним скопированным.
upper_bound() возвращает итератор, указывающий на последнюю позицию в отсортированной последовательности [first,last), в которую еще можно вставить значение value, не нарушая упорядоченности. Значения всех элементов, начиная с этой позиции и далее, будут больше, чем value. Например, если дана последовательность:
то обращение к upper_bound() с value=21 вернет итератор, указывающий на значение 22, а обращение с value=22 - на значение 23. В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера; во втором - заданная программистом операция comp.
В стандартной библиотеке используется макс-хип. Макс-хип - это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [SEDGEWICK88]. Альтернативой ему является мин-хип, для которого значение ключа в каждом узле меньше либо равно значению ключа в каждом из узлов-потомков.) В реализации из стандартной библиотеки самое большое значение (корень дерева) всегда оказывается в начале массива. Например, приведенная последовательность букв удовлетворяет требованиям, накладываемым на хип:
В данном примере X - это корневой узел, слева от него находится T, а справа - O. Обратите внимание, что потомки не обязательно должны быть упорядочены (т.е. значение в левом узле не обязано быть меньше, чем в правом). G и S - потомки узла T, а M и N - потомки узла O. Аналогично A и E - потомки G, R и A - потомки S, I - левый потомок M, а N - листовой узел без потомков.
Четыре обобщенных алгоритма для работы с хипом: make_heap(), pop_heap(), push_heap() и sort_heap() - поддерживают его создание и различные манипуляции. В последних трех алгоритмах предполагается, что последовательность, ограниченная парой итераторов, - действительно хип (в противном случае поведение программы не определено). Заметим, что список нельзя использовать как контейнер для хранения хипа, поскольку он не поддерживает произвольный доступ. Встроенный массив для размещения хипа использовать можно, но в этом случае трудно применять алгоритмы pop_heap() и push_heap(), так как они требуют изменения размера контейнера. Мы опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы.
make_heap() преобразует в хип последовательность, ограниченную диапазоном [first,last). В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp.
pop_heap() в действительности не исключает наибольший элемент, а переупорядочивает хип. Он переставляет элементы в позициях first и last-1, а затем перестраивает в хип последовательность в диапазоне [first,last-1). После этого “вытолкнутый” элемент можно получить посредством функции-члена back() контейнера либо по-настоящему исключить его с помощью pop_back(). В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp.
push_heap() предполагает, что последовательность, ограниченная диапазоном [first,last-1), - хип и что новый добавляемый к хипу элемент находится в позиции last-1. Все элементы в диапазоне [first,last) реорганизуются в новый хип. Перед вызовом push_heap() необходимо вставить новый элемент в конец контейнера, возможно, применив функцию push_back() (это показано в примере ниже). В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера; во втором - операция comp.
sort_heap() сортирует последовательность в диапазоне [first,last), предполагая, что это правильно построенный хип; в противном случае поведение программы не определено. (Разумеется, после сортировки хип перестает быть хипом!) В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp.
#include <numeric>
#include <list>
#include <functional>
#include <iostream.h>
/*
* выход:
* accumulate()
* работает с последовательностью {1,2,3,4}
* результат для сложения по умолчанию: 10
* результат для объекта-функции plus<int>: 10
*/
int main()
{
int ia[] = { 1, 2, 3, 4 };
list<int,allocator> ilist( ia, ia+4 );
int ia_result = accumulate(&ia[0], &ia[4], 0);
int ilist_res = accumulate(
ilist.begin(), ilist.end(), 0, plus<int>() );
cout << "accumulate()\n\t"
<< "работает с последовательностью {1,2,3,4}\n\t"
<< "результат для сложения по умолчанию: "
<< ia_result << "\n\t"
<< "результат для объекта-функции plus<int>: "
<< ilist_res
<< endl;
return 0;
}
Алгоритм adjacent_difference()
template < class InputIterator, class OutputIterator >
OutputIterator adjacent_difference(
InputIterator first, InputIterator last,
OutputIterator result );
template < class InputIterator, class OutputIterator >
class BinaryOperation >
OutputIterator adjacent_difference(
InputIterator first, InputIterator last,
OutputIterator result, BinaryOperation op );
#include <numeric>
#include <list>
#include <functional>
#include <iterator>
#include <iostream.h>
int main()
{
int ia[] = { 1, 1, 2, 3, 5, 8 };
list<int,allocator> ilist(ia, ia+6);
list<int,allocator> ilist_result(ilist.size());
adjacent_difference(ilist.begin(), ilist.end(),
ilist_result.begin() );
// на выходе печатается:
// 1 0 1 1 2 3
copy( ilist_result.begin(), ilist_result.end(),
ostream_iterator<int>(cout," "));
cout << endl;
adjacent_difference(ilist.begin(), ilist.end(),
ilist_result.begin(), times<int>() );
// на выходе печатается:
// 1 1 2 6 15 40
copy( ilist_result.begin(), ilist_result.end(),
ostream_iterator<int>(cout," "));
cout << endl;
}
Алгоритм adjacent_find()
template < class ForwardIterator >
ForwardIterator
adjacent_find( ForwardIterator first, ForwardIterator last );
template < class ForwardIterator, class BinaryPredicate >
ForwardIterator
adjacent_find( ForwardIterator first,
ForwardIterator last, Predicate pred );
#include <algorithm>
#include <vector>
#include <iostream.h>
#include <assert.h>
class TwiceOver {
public:
bool operator() ( int val1, int val2 )
{ return val1 == val2/2 ? true : false; }
};
int main()
{
int ia[] = { 1, 4, 4, 8 };
vector< int, allocator > vec( ia, ia+4 );
int *piter;
vector< int, allocator >::iterator iter;
// piter указывает на ia[1]
piter = adjacent_find( ia, ia+4 );
assert( *piter == ia[ 1 ] );
// iter указывает на vec[2]
iter = adjacent_find( vec.begin(), vec.end(), TwiceOver() );
assert( *iter == vec[ 2 ] );
// пришли сюда: все хорошо
cout < <"ok: adjacent-find() завершился успешно!\n";
return 0;
}
Алгоритм binary_search()
template < class ForwardIterator, class Type >
bool
binary_search( ForwardIterator first,
ForwardIterator last, const Type &value );
template < class ForwardIterator, class Type >
bool
binary_search( ForwardIterator first,
ForwardIterator last, const Type &value,
Compare comp );
#include <algorithm>
#include <vector>
#include <assert.h>
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
vector< int, allocator > vec( ia, ia+12 );
sort( &ia[0], &ia[12] );
bool found_it = binary_search( &ia[0], &ia[12], 18 );
assert( found_it == false );
vector< int > vec( ia, ia+12 );
sort( vec.begin(), vec.end(), greater<int>() );
found_it = binary_search( vec.begin(), vec.end(),
26, greater<int>() );
assert( found_it == true );
}
Алгоритм copy()
template < class InputIterator, class OutputIterator >
OutputIterator
copy( InputIterator first1, InputIterator last,
OutputIterator first2 )
int ia[] = {0, 1, 2, 3, 4, 5 };
// сдвинуть элементы влево на один, получится {1,2,3,4,5,5}
copy( ia+1, ia+6, ia );
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
/* печатается:
0 1 1 3 5 8 13
сдвиг массива влево на 1:
1 1 3 5 8 13 13
сдвиг вектора влево на 2:
1 3 5 8 13 8 13
*/
int main()
{
int ia[] = { 0, 1, 1, 3, 5, 8, 13 };
vector< int, allocator > vec( ia, ia+7 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность элементов:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
// сдвиг влево на один элемент
copy( ia+1, ia+7, ia );
cout << "сдвиг массива влево на 1:\n";
copy( ia, ia+7, ofile ); cout << '\n';
// сдвиг влево на два элемента
copy( vec.begin()+2, vec.end(), vec.begin() );
cout << "сдвиг вектора влево на 2:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм copy_backward()
template < class BidirectionalIterator1,
class BidirectionalIterator2 >
BidirectionalIterator2
copy_backward( BidirectionalIterator1 first,
BidirectionalIterator1 last1,
BidirectionalIterator2 last2 )
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
class print_elements {
public:
void operator()( string elem ) {
cout <<elem
< <( _line_cnt++%8 ? " " : "\n\t" );
}
static void reset_line_cnt() { _line_cnt = 1; }
private:
static int _line_cnt;
};
int print_elements::_line_cnt = 1;
/* печатается:
исходный список строк:
The light untonsured hair grained and hued like
pale oak
после copy_backward( begin+1, end-3, end ):
The light untonsured hair light untonsured hair grained
and hued
*/
int main()
{
string sa[] = {
"The", "light", "untonsured", "hair",
"grained", "and", "hued", "like", "pale", "oak" };
vector< string, allocator > svec( sa, sa+10 );
cout < <"исходный список строк:\n\t";
for_each( svec.begin(), svec.end(), print_elements() );
cout << "\n\n";
copy_backward( svec.begin()+1, svec.end()-3, svec.end() );
print_elements::reset_line_cnt();
cout << "после copy_backward( begin+1, end-3, end ):\n";
for_each( svec.begin(), svec.end(), print_elements() );
cout << "\n";
}
Алгоритм count()
template < class InputIterator, class Type >
iterator_traits<InputIterator>::distance_type
count( InputIterator first,
InputIterator last, const Type& value );
#include <algorithm>
#include <string>
#include <list>
#include <iterator>
#include <assert.h>
#include <iostream.h>
#include <fstream.h>
/***********************************************************************
* прочитанный текст:
Alice Emma has long flowing red hair. Her Daddy says
when the wind blows through her hair, it looks almost alive,
like a fiery bird in flight. A beautiful fiery bird, he tells her,
magical but untamed. "Daddy, shush, there is no such thing,"
she tells him, at the same time wanting him to tell her more.
Shyly, she asks, "I mean, Daddy, is there?"
************************************************************************
* программа выводит:
* count(): fiery встречается 2 раз(а)
************************************************************************
*/
int main()
{
ifstream infile( "alice_emma" );
assert ( infile != 0 );
list<string,allocator> textlines;
typedef list<string,allocator>::difference_type diff_type;
istream_iterator< string, diff_type > instream( infile ),
eos;
copy( instream, eos, back_inserter( textlines ));
string search_item( "fiery" );
/*********************************************************************
* примечание: ниже показан интерфейс count(), принятый в
* стандартной библиотеке. В текущей реализации библиотеки
* от RogueWave поддерживается более ранняя версия, в которой
* типа distance_type еще не было, так что count()
* возвращала результат в последнем аргументе
*
* вот как должен выглядеть вызов:
*
* typedef iterator_traits<InputIterator>::
* distance_type dis_type;
*
* dis_type elem_count;
* elem_count = count( textlines.begin(), textlines.end(),
* search_item );
***********************************************************************
int elem_count = 0;
list<string,allocator>::iterator
ibegin = textlines.begin(),
iend = textlines.end();
// устаревшая форма count()
count( ibegin, iend, search_item, elem_count );
cout < <"count(): " < < search_item
< <" встречается " < < elem_count < < " раз(а)\n";
}
Алгоритм count_if()
template < class InputIterator, class Predicate >
iterator_traits<InputIterator>::distance_type
count_if( InputIterator first,
InputIterator last, Predicate pred );
#include <algorithm>
#include <list>
#include <iostream.h>
class Even {
public:
bool operator()( int val )
{ return val%2 ? false : true; }
};
int main()
{
int ia[] = {0,1,1,2,3,5,8,13,21,34};
list< int,allocator > ilist( ia, ia+10 );
/*
* не поддерживается в текущей реализации
*****************************************************
typedef
iterator_traits<InputIterator>::distance_type
distance_type;
distance_type ia_count, list_count;
// счетчик четных элементов: 4
ia_count = count_if( &ia[0], &ia[10], Even() );
list_count = count_if( ilist.begin(), ilist_end(),
bind2nd(less<int>(),10) );
******************************************************
*/
int ia_count = 0;
count_if( &ia[0], &ia[10], Even(), ia_count );
// печатается:
// count_if(): есть 4 четных элемент(а).
cout << "count_if(): есть "
<< ia_count << " четных элемент(а).\n";
int list_count = 0;
count_if( ilist.begin(), ilist.end(),
bind2nd(less<int>(),10), list_count );
// печатается:
// count_if(): есть 7 элемент(ов), меньших 10.
cout << "count_if(): есть "
<< list_count
<< " элемент(ов), меньших 10.\n";
}
Алгоритм equal()
template< class InputIterator1, class InputIterator2 >
bool
equal( InputIterator1 first1,
InputIterator1 last, InputIterator2 first2 );
template< class InputIterator1, class InputIterator2,
class BinaryPredicate >
bool
equal( InputIterator1 first1, InputIterator1 last,
InputIterator2 first2, BinaryPredicate pred );
if ( vec1.size() == vec2.size() &&
equal( vec1.begin(), vec1.end(), vec2.begin() );
#include <algorithm>
#include <list>
#include <iostream.h>
class equal_and_odd{
public:
bool
operator()( int val1, int val2 )
{
return ( val1 == val2 &&
( val1 == 0 || val1 % 2 ))
? true : false;
}
};
int main()
{
int ia[] = { 0,1,1,2,3,5,8,13 };
int ia2[] = { 0,1,1,2,3,5,8,13,21,34 };
bool res;
// true: обе последовательности совпадают до длины ia
// печатается: int ia[7] равно int ia2[9]? Да.
res = equal( &ia[0], &ia[7], &ia2[0] );
cout << "int ia[7] равно int ia2[9]? "
< <( res ? "Да" : "Нет" ) << ".\n";
list< int, allocator > ilist( ia, ia+7 );
list<int, allocator > ilist2( ia2, ia2+9 );
// печатается: список ilist равен ilist2? Да.
res = equal( ilist.begin(), ilist.end(), ilist2.begin() );
cout << "список ilist равен ilist2? "
<< ( res ? "Да" : "Нет" ) << ".\n";
// false: 0, 2, 8 не являются равными и нечетными
// печатается: список ilist equal_and_odd() ilist2? Нет.
res = equal( ilist.begin(), ilist.end(),
ilist2.begin(), equal_and_odd() );
cout << "список ilist equal_and_odd() ilist2? "
<< ( res ? "Да" : "Нет" ) << ".\n";
return 0;
}
Алгоритм equal_range()
template< class ForwardIterator, class Type >
pair< ForwardIterator, ForwardIterator >
equal_range( ForwardIterator first,
ForwardIterator last, const Type &value );
template< class ForwardIterator, class Type, class Compare >
pair<ForwardIterator, ForwardIterator >
equal_range( ForwardIterator first,
ForwardIterator last, const Type &value,
Compare comp );
int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};
#include <algorithm>
#include <vector>
#include <utility>
#include <iostream.h>
/* печатается:
последовательность элементов массива после сортировки:
12 15 17 19 20 22 23 26 29 35 40 51
результат equal_range при поиске значения 23:
*ia_iter.first: 23 *ia_iter.second: 26
результат equal_range при поиске отсутствующего значения 21:
*ia_iter.first: 22 *ia_iter.second: 22
последовательность элементов вектора после сортировки:
51 40 35 29 26 23 22 20 19 17 15 12
результат equal_range при поиске значения 26:
*ivec_iter.first: 26 *ivec_iter.second: 23
результат equal_range при поиске отсутствующего значения 21:
*ivec_iter.first: 20 *ivec_iter.second: 20
*/
int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > ivec( ia, ia+12 );
ostream_iterator< int > ofile( cout, " " );
sort( &ia[0], &ia[12] );
cout < < "последовательность элементов массива после сортировки:\n";
copy( ia, ia+12, ofile ); cout < < "\n\n";
pair< int*,int* > ia_iter;
ia_iter = equal_range( &ia[0], &ia[12], 23 );
cout < < "результат equal_range при поиске значения 23:\n\t"
< < "*ia_iter.first: " < < *ia_iter.first < < "\t"
< < "*ia_iter.second: " < < *ia_iter.second < <"\n\n";
ia_iter = equal_range( &ia[0], &ia[12], 21 );
cout < < "результат equal_range при поиске "
< < "отсутствующего значения 21:\n\t"
< < "*ia_iter.first: " < < *ia_iter.first < < "\t"
< < "*ia_iter.second: " < < *ia_iter.second < < "\n\n";
sort( ivec.begin(), ivec.end(), greater<int>() );
cout < < "последовательность элементов вектора после сортировки:\n";
copy( ivec.begin(), ivec.end(), ofile ); cout < < "\n\n";
typedef vector< int, allocator >::iterator iter_ivec;
pair< iter_ivec, iter_ivec > ivec_iter;
ivec_iter = equal_range( ivec.begin(), ivec.end(), 26,
greater<int>() );
cout < < "результат equal_range при поиске значения 26:\n\t"
< < "*ivec_iter.first: " < < *ivec_iter.first < <"\t"
< <"*ivec_iter.second: " < < *ivec_iter.second
< < "\n\n";
ivec_iter = equal_range( ivec.begin(), ivec.end(), 21,
greater<int>() );
cout < < "результат equal_range при поиске отсутствующего значения 21:\n\t"
< < "*ivec_iter.first: " < < *ivec_iter.first < < "\t"
< < "*ivec_iter.second: " < < *ivec_iter.second
< < "\n\n";
}
Алгоритм fill()
template< class ForwardIterator, class Type >
void
fill( ForwardIterator first,
ForwardIterator last, const Type& value );
#include <algorithm>
#include <list>
#include <string>
#include <iostream.h>
/* печатается:
исходная последовательность элементов массива:
0 1 1 2 3 5 8
массив после fill(ia+1,ia+6):
0 9 9 9 9 9 8
исходная последовательность элементов списка:
c eiffel java ada perl
список после fill(++ibegin,--iend):
c c++ c++ c++ perl
*/
int main()
{
const int value = 9;
int ia[] = { 0, 1, 1, 2, 3, 5, 8 };
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность элементов массива:\n";
copy( ia, ia+7, ofile ); cout << "\n\n";
fill( ia+1, ia+6, value );
cout << "массив после fill(ia+1,ia+6):\n";
copy( ia, ia+7, ofile ); cout << "\n\n";
string the_lang( "c++" );
string langs[5] = { "c", "eiffel", "java", "ada", "perl" };
list< string, allocator > il( langs, langs+5 );
ostream_iterator< string > sofile( cout, " " );
cout << "исходная последовательность элементов списка:\n";
copy( il.begin(), il.end(), sofile ); cout << "\n\n";
typedef list<string,allocator> ::iterator iterator;
iterator ibegin = il.begin(), iend = il.end();
fill( ++ibegin, --iend, the_lang );
cout << "список после fill(++ibegin,--iend):\n";
copy( il.begin(), il.end(), sofile ); cout << "\n\n";
}
Алгоритм fill_n()
template< class ForwardIterator, class Size, class Type >
void
fill_n( ForwardIterator first,
Size n, const Type& value );
#include <algorithm>
#include <vector>
#include <string>
#include <iostream.h>
class print_elements {
public:
void operator()( string elem ) {
cout << elem
< <( _line_cnt++%8 ? " " : "\n\t" );
}
static void reset_line_cnt() { _line_cnt = 1; }
private:
static int _line_cnt;
};
int print_elements::_line_cnt = 1;
/* печатается:
исходная последовательность элементов массива:
0 1 1 2 3 5 8
массив после fill_n( ia+2, 3, 9 ):
0 1 9 9 9 5 8
исходная последовательность строк:
Stephen closed his eyes to hear his boots
crush crackling wrack and shells
последовательность после применения fill_n():
Stephen closed his xxxxx xxxxx xxxxx xxxxx xxxxx
xxxxx crackling wrack and shells
*/
int main()
{
int value = 9; int count = 3;
int ia[] = { 0, 1, 1, 2, 3, 5, 8 };
ostream_iterator< int > iofile( cout, " " );
cout << "исходная последовательность элементов массива:\n";
copy( ia, ia+7, iofile ); cout << "\n\n";
fill_n( ia+2, count, value );
cout << "массив после fill_n( ia+2, 3, 9 ):\n";
copy( ia, ia+7, iofile ); cout << "\n\n";
string replacement( "xxxxx" );
string sa[] = { "Stephen", "closed", "his", "eyes", "to",
"hear", "his", "boots", "crush", "crackling",
"wrack", "and", "shells" };
vector< string, allocator>svec( sa, sa+13 );
cout << "исходная последовательность строк:\n\t";
for_each( svec.begin(), svec.end(), print_elements() );
cout << "\n\n";
fill_n( svec.begin()+3, count*2, replacement );
print_elements::reset_line_cnt();
cout << "последовательность после применения fill_n():\n\t";
for_each( svec.begin(), svec.end(), print_elements() );
cout << "\n";
}
Алгоритм find()
template< class InputIterator, class T >
InputIterator
find( InputIterator first,
InputIterator last, const T &value );
#include <algorithm>
#include <iostream.h>
#include <list>
#include <string>
int main()
{
int array[ 17 ] = { 7,3,3,7,6,5,8,7,2,1,3,8,7,3,8,4,3 };
int elem = array[ 9 ];
int *found_it;
found_it = find( &array[0], &array[17], elem );
// печатается: поиск первого вхождения 1 найдено!
cout << "поиск первого вхождения "
<< elem < <"\t"
<< ( found_it ? "найдено!\n" : "не найдено!\n" );
string beethoven[] = {
"Sonata31", "Sonata32", "Quartet14", "Quartet15",
"Archduke", "Symphony7" };
string s_elem( beethoven[ 1 ] );
list< string, allocator > slist( beethoven, beethoven+6 );
list< string, allocator >::iterator iter;
iter = find( slist.begin(), slist.end(), s_elem );
// печатается: поиск первого вхождения Sonata32 найдено!
cout << "поиск первого вхождения "
<< s_elem << "\t"
<< ( found_it ? "найдено!\n" : "не найдено!\n" );
}
Алгоритм find_if()
template< class InputIterator, class Predicate >
InputIterator
find_if( InputIterator first,
InputIterator last, Predicate pred );
#include <algorithm>
#include <list>
#include <set>
#include <string>
#include <iostream.h>
// альтернатива оператору равенства
// возвращает true, если строка содержится в объекте-члене FriendSet
class OurFriends { // наши друзья
public:
bool operator()( const string& str ) {
return ( friendset.count( str ));
}
static void
FriendSet( const string *fs, int count ) {
copy( fs, fs+count,
inserter( friendset, friendset.end() ));
}
private:
static set< string, less<string>, allocator > friendset;
};
set< string, less<string>, allocator > OurFriends::friendset;
int main()
{
string Pooh_friends[] = { "Пятачок", "Тигра", "Иа-Иа" };
string more_friends[] = { "Квазимодо", "Чип", "Пятачок" };
list<string,allocator> lf( more_friends, more_friends+3 );
// заполнить список друзей Пуха
OurFriends::FriendSet( Pooh_friends, 3 );
list<string,allocator>::iterator our_mutual_friend;
our_mutual_friend =
find_if( lf.begin(), lf.end(), OurFriends());
// печатается:
// Представьте-ка, наш друг Пятачок - также друг Пуха.
if ( our_mutual_friend != lf.end() )
cout << "Представьте-ка, наш друг "
<< *our_mutual_friend
<< " также друг Пуха.\n";
return 0;
}
Алгоритм find_end()
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1
find_end( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
template< class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate >
ForwardIterator1
find_end( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred );
#include <algorithm>
#include <vector>
#include <iostream.h>
#include <assert.h>
int main()
{
int array[ 17 ] = { 7,3,3,7,6,5,8,7,2,1,3,7,6,3,8,4,3 };
int subarray[ 3 ] = { 3, 7, 6 };
int *found_it;
// find найти последнее вхождение последовательности 3,7,6
// в массив и вернуть адрес первого ее элемента ...
found_it = find_end( &array[0], &array[17],
&subarray[0], &subarray[3] );
assert( found_it == &array[10] );
vector< int, allocator > ivec( array, array+17 );
vector< int, allocator > subvec( subarray, subarray+3 );
vector< int, allocator >::iterator found_it2;
found_it2 = find_end( ivec.begin(), ivec.end(),
subvec.begin(), subvec.end(),
equal_to<int>() );
assert( found_it2 == ivec.begin()+10 );
cout << "ok: find_end правильно вернула начало "
<< "последнего вхождения последовательности: 3,7,6!\n";
}
Алгоритм find_first_of()
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1
find_first_of( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
template< class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate >
ForwardIterator1
find_first_of( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred );
#include <algorithm>
#include <vector>
#include <string>
#include <iostream.h>
int main()
{
string s_array[] = { "Ee", "eE", "ee", "Oo", "oo", "ee" };
// возвращает первое вхождение "ee" -- &s_array[2]
string to_find[] = { "oo", "gg", "ee" };
string *found_it =
find_first_of( s_array, s_array+6,
to_find, to_find+3 );
// печатается:
// найдено: ee
// &s_array[2]: 0x7fff2dac
// &found_it: 0x7fff2dac
if ( found_it != &s_array[6] )
cout << "найдено: " << *found_it << "\n\t"
<< "&s_array[2]:\t" << &s_array[2] << "\n\t"
<< "&found_it:\t" << found_it << "\n\n";
vector< string, allocator > svec( s_array, s_array+6);
vector< string, allocator > svec_find( to_find, to_find+2 );
// возвращает вхождение "oo" -- svec.end()-2
vector< string, allocator >::iterator found_it2;
found_it2 = find_first_of(
svec.begin(), svec.end(),
svec_find.begin(), svec_find.end(),
equal_to<string>() );
// печатает:
// тоже найдено: oo
// &svec.end()-2: 0x100067b0
// &found_it2: 0x100067b0
if ( found_it2 != svec.end() )
cout << "тоже найдено: " << *found_it2 << "\n\t"
<< "&svec.end()-2:\t" << svec.end()-2 << "\n\t"
<< "&found_it2:\t" << found_it2 << "\n";
}
Алгоритм for_each()
template< class InputIterator, class Function >
Function
for_each( InputIterator first,
InputIterator last, Function func );
#include <algorithm>
#include <vector>
#include <iostream.h>
template <class Type>
void print_elements( Type elem ) { cout << elem < <" "; }
int main()
{
vector< int, allocator > ivec;
for ( int ix = 0; ix < 10; ix++ )
ivec.push_back( ix );
void (*pfi)( int ) = print_elements;
for_each( ivec.begin(), ivec.end(), pfi );
return 0;
}
Алгоритм generate()
template< class ForwardIterator, class Generator >
void
generate( ForwardIterator first,
ForwardIterator last, Generator gen );
#include <algorithm>
#include <list>
#include <iostream.h>
int odd_by_twos() {
static int seed = -1;
return seed += 2;
}
template <class Type>
void print_elements( Type elem ) { cout < < elem < < " "; }
int main()
{
list< int, allocator > ilist( 10 );
void (*pfi)( int ) = print_elements;
generate( ilist.begin(), ilist.end(), odd_by_twos );
// печатается:
// элементы в списке, первый вызов:
// 1 3 5 7 9 11 13 15 17 19
cout < < "элементы в списке, первый вызов:\n";
for_each( ilist.begin(), ilist.end(), pfi );
generate( ilist.begin(), ilist.end(), odd_by_twos );
// печатается:
// элементы в списке, второй вызов:
// 21 23 25 27 29 31 33 35 37 39
cout < <"\n\nэлементы в списке, второй вызов:\n";
for_each( ilist.begin(), ilist.end(), pfi );
return 0;
}
Алгоритм generate_n()
template< class OutputIterator,
class Size, class Generator >
void
generate_n( OutputIterator first, Size n, Generator gen );
#include <algorithm>
#include <iostream.h>
#include <list>
class even_by_twos {
public:
even_by_twos( int seed = 0 ) : _seed( seed ){}
int operator()() { return _seed += 2; }
private:
int _seed;
};
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
int main()
{
list< int, allocator > ilist( 10 );
void (*pfi)( int ) = print_elements;
generate_n( ilist.begin(), ilist.size(), even_by_twos() );
// печатается:
// generate_n с even_by_twos():
// 2 4 6 8 10 12 14 16 18 20
cout << "generate_n с even_by_twos():\n";
for_each( ilist.begin(), ilist.end(), pfi ); cout << "\n";
generate_n( ilist.begin(), ilist.size(), even_by_twos( 100 ) );
// печатается:
// generate_n с even_by_twos( 100 ):
// 102 104 106 108 110 112 114 116 118 120
cout << "generate_n с even_by_twos( 100 ):\n";
for_each( ilist.begin(), ilist.end(), pfi );
}
Алгоритм includes()
template< class InputIterator1, class InputIterator2 >
bool
includes( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2 );
template< class InputIterator1, class InputIterator2,
class Compare >
bool
includes( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp );
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int ia1[] = { 13, 1, 21, 2, 0, 34, 5, 1, 8, 3, 21, 34 };
int ia2[] = { 21, 2, 8, 3, 5, 1 };
// алгоритму includes следует передавать отсортированные контейнеры
sort( ia1, ia1+12 ); sort( ia2, ia2+6 );
// печатает: каждый элемент ia2 входит в ia1? Да
bool res = includes( ia1, ia1+12, ia2, ia2+6 );
cout < < "каждый элемент ia2 входит в ia1? "
< <(res ? "Да" : "Нет") < < endl;
vector< int, allocator > ivect1( ia1, ia1+12 );
vector< int, allocator > ivect2( ia2, ia2+6 );
// отсортирован в порядке убывания
sort( ivect1.begin(), ivect1.end(), greater<int>() );
sort( ivect2.begin(), ivect2.end(), greater<int>() );
res = includes( ivect1.begin(), ivect1.end(),
ivect2.begin(), ivect2.end(),
greater<int>() );
// печатает: каждый элемент ivect2 входит в ivect1? Да
cout < < "каждый элемент ivect2 входит в ivect1? "
< < (res ? "Да" : "Нет") < < endl;
}
Алгоритм inner_product()
template< class InputIterator1, class InputIterator2
class Type >
Type
inner_product(
InputIterator1 first1, InputIterator1 last,
InputIterator2 first2, Type init );
template< class InputIterator1, class InputIterator2
class Type,
class BinaryOperation1, class BinaryOperation2 >
Type
inner_product(
InputIterator1 first1, InputIterator1 last,
InputIterator2 first2, Type init,
BinaryOperation1 op1, BinaryOperation2 op2 );
2*1 + 3*2 + 5*3 + 8*4
(2+1) - (3+2) - (5+3) - (8+4)
#include <numeric>
#include <vector>
#include <iostream.h>
int main()
{
int ia[] = { 2, 3, 5, 8 };
int ia2[] = { 1, 2, 3, 4 };
// перемножить пары элементов из обоих массивов,
// сложить и добавить начальное значение: 0
int res = inner_product( &ia[0], &ia[4], &ia2[0], 0 );
// печатает: скалярное произведение массивов: 55
cout << "скалярное произведение массивов: "
<< res << endl;
vector<int, allocator> vec( ia, ia+4 );
vector<int, allocator> vec2( ia2, ia2+4 );
// сложить пары элементов из обоих векторов,
// вычесть из начального значения: 0
res = inner_product( vec.begin(), vec.end(),
vec2.begin(), 0,
minus<int>(), plus<int>() );
// печатает: скалярное произведение векторов: -28
cout << "скалярное произведение векторов: "
<< res << endl;
return 0;
}
Алгоритм inplace_merge()
template <class BidirectionalIterator >
void
inplace_merge( BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last );
template< class BidirectionalIterator, class Compare >
void
inplace_merge( BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp );
#include <algorithm>
#include <vector>
#include <iostream.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
/*
* печатает:
ia разбит на два отсортированных подмассива:
12 15 17 20 23 26 29 35 40 51 10 16 21 41 44 54 62 65 71 74
ia inplace_merge:
10 12 15 16 17 20 21 23 26 29 35 40 41 44 51 54 62 65 71 74
ivec разбит на два отсортированных подвектора:
51 40 35 29 26 23 20 17 15 12 74 71 65 62 54 44 41 21 16 10
ivec inplace_merge:
74 71 65 62 54 51 44 41 40 35 29 26 23 21 20 17 16 15 12 10
*/
int main()
{
int ia[] = { 29,23,20,17,15,26,51,12,35,40,
74,16,54,21,44,62,10,41,65,71 };
vector< int, allocator > ivec( ia, ia+20 );
void (*pfi)( int ) = print_elements;
// отсортировать обе подпоследовательности
sort( &ia[0], &ia[10] );
sort( &ia[10], &ia[20] );
cout << "ia разбит на два отсортированных подмассива: \n";
for_each( ia, ia+20, pfi ); cout << "\n\n";
inplace_merge( ia, ia+10, ia+20 );
cout << "ia inplace_merge:\n";
for_each( ia, ia+20, pfi ); cout << "\n\n";
sort( ivec.begin(), ivec.begin()+10, greater<int>() );
sort( ivec.begin()+10, ivec.end(), greater<int>() );
cout << "ivec разбит на два отсортированных подвектора: \n";
for_each( ivec.begin(), ivec.end(), pfi ); cout << "\n\n";
inplace_merge( ivec.begin(), ivec.begin()+10,
ivec.end(), greater<int>() );
cout << "ivec inplace_merge:\n";
for_each( ivec.begin(), ivec.end(), pfi ); cout << endl;
}
Алгоритм iter_swap()
template< class ForwardIterator1, class ForwardIterator2 >
void
iter_swap( ForwardIterator1 a, ForwardIterator2 b );
iter_swap() обменивает значения элементов, на которые указывают итераторы a и b.
#include <algorithm>
#include <list>
#include <iostream.h>
int main()
{
int ia[] = { 5, 4, 3, 2, 1, 0 };
list< int,allocator > ilist( ia, ia+6 );
typedef list< int, allocator >::iterator iterator;
iterator iter1 = ilist.begin(),iter2,
iter_end = ilist.end();
// отсортировать список "пузырьком" ...
for ( ; iter1 != iter_end; ++iter1 )
for ( iter2 = iter1; iter2 != iter_end; ++iter2 )
if ( *iter2 < *iter1 )
iter_swap( iter1, iter2 );
// печатается:
// ilist после сортировки "пузырьком" с помощью iter_swap():
// { 0 1 2 3 4 5 }
cout << "ilist после сортировки "пузырьком" с помощью iter_swap(): { ";
for ( iter1 = ilist.begin(); iter1 != iter_end; ++iter1 )
cout << *iter1 << " ";
cout << "}\n";
return 0;
}
Алгоритм lexicographical_compare()
template< class InputIterator1, class InputIterator2 >
bool
lexicographical_compare(
InputIterator1 first1, InputIterator1 last1,
InputIterator1 first2, InputIterator2 last2 );
template< class InputIterator1, class InputIterator2,
class Compare >
bool
lexicographical_compare(
InputIterator1 first1, InputIterator1 last1,
InputIterator1 first2, InputIterator2 last2,
Compare comp );
string arr1[] = { "Piglet", "Pooh", "Tigger" };
string arr2[] = { "Piglet", "Pooch", "Eeyore" };
#include <algorithm>
#include <list>
#include <string>
#include <assert.h>
#include <iostream.h>
class size_compare {
public:
bool operator()( const string &a, const string &b ) {
return a.length() <= b.length();
}
};
int main()
{
string arr1[] = { "Piglet", "Pooh", "Tigger" };
string arr2[] = { "Piglet", "Pooch", "Eeyore" };
bool res;
// на втором элементе получаем false
// Pooch меньше Pooh
// на третьем элементе тоже получили бы false
res = lexicographical_compare( arr1, arr1+3,
arr2, arr2+3 );
assert( res == false );
// получаем true: длина каждого элемента ilist2
// меньше либо равна длине соответственного
// элемента ilist1
list< string, allocator > ilist1( arr1, arr1+3 );
list< string, allocator > ilist2( arr2, arr2+3 );
res = lexicographical_compare(
ilist1.begin(), ilist1.end(),
ilist2.begin(), ilist2.end(), size_compare() );
assert( res == true );
cout < <"ok: lexicographical_compare завершился успешно!\n";
}
Алгоритм lower_bound()
template< class ForwardIterator, class Type >
ForwardIterator
lower_bound( ForwardIterator first,
ForwardIterator last, const Type &value );
template< class ForwardIterator, class Type, class Compare >
ForwardIterator
lower_bound( ForwardIterator first,
ForwardIterator last, const Type &value,
class Compare );
int ia = = {12,15,17,19,20,22,23,26,29,35,40,51};
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
sort( &ia[0], &ia[12] );
int search_value = 18;
int *ptr = lower_bound( ia, ia+12, search_value );
// печатается:
// Первый элемент, перед которым можно вставить 18, - это 19
// Предыдущее значение равно 17
cout << "Первый элемент, перед которым можно вставить "
<< search_value
<< ", - это "
<< *ptr << endl
<< "Предыдущее значение равно "
<< *(ptr-1) << endl;
vector< int, allocator > ivec( ia, ia+12 );
// отсортировать в порядке возрастания ...
sort( ivec.begin(), ivec.end(), greater<int>() );
search_value = 26;
vector< int, allocator >::iterator iter;
// необходимо указать, как именно
// осуществлялась сортировка ...
iter = lower_bound( ivec.begin(), ivec.end(),
search_value, greater<int>() );
// печатается:
// Первый элемент, перед которым можно вставить 26, - это 26
// Предыдущее значение равно 29
cout << "Первый элемент, перед которым можно вставить "
<< search_value
<< ", - это "
<< *iter << endl
<< "Предыдущее значение равно "
<< *(iter-1) << endl;
return 0;
}
Алгоритм max()
template< class Type >
const Type&
max( const Type &aval, const Type &bval );
template< class Type, class Compare >
const Type&
max( const Type &aval, const Type &bval, Compare comp );
Алгоритм max_element()
template< class ForwardIterator >
ForwardIterator
max_element( ForwardIterator first,
ForwardIterator last );
template< class ForwardIterator, class Compare >
ForwardIterator
max_element( ForwardIterator first,
ForwardIterator last, Compare comp );
Алгоритм min()
template< class Type >
const Type&
min( const Type &aval, const Type &bval );
template< class Type, class Compare >
const Type&
min( const Type &aval, const Type &bval, Compare comp );
Алгоритм min_element()
template< class ForwardIterator >
ForwardIterator
min_element( ForwardIterator first,
ForwardIterator last );
template<class ForwardIterator, class Compare >
ForwardIterator
min_element( ForwardIterator first,
ForwardIterator last, Compare comp );
// иллюстрирует max(), min(), max_element(), min_element()
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int ia[] = { 7, 5, 2, 4, 3 };
const vector< int, allocator > ivec( ia, ia+5 );
int mval = max( max( max( max(ivec[4],ivec[3]),
ivec[2]),ivec[1]),ivec[0]);
// вывод: результат вложенных вызовов max() равен: 7
cout << "результат вложенных вызовов max() равен: "
<< mval << endl;
mval = min( min( min( min(ivec[4],ivec[3]),
ivec[2]),ivec[1]),ivec[0]);
// вывод: результат вложенных вызовов min() равен: 2
cout << "результат вложенных вызовов min() равен: "
<< mval << endl;
vector< int, allocator >::const_iterator iter;
iter = max_element( ivec.begin(), ivec.end() );
// вывод: результат вложенных вызовов max_element() также равен: 7
cout << "результат вложенных вызовов max_element() также равен: "
<< *iter << endl;
iter = min_element( ivec.begin(), ivec.end() );
// вывод: результат вложенных вызовов min_element() также равен: 2
cout << "результат вложенных вызовов min_element() также равен: "
<< *iter << endl;
}
Алгоритм merge()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
merge( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
merge( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
#include <algorithm>
#include <vector>
#include <list>
#include <deque>
#include <iostream.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
int ia2[] = {74,16,39,54,21,44,62,10,27,41,65,71};
vector< int, allocator > vec1( ia, ia +12 ),
vec2( ia2, ia2+12 );
int ia_result[24];
vector< int, allocator > vec_result(vec1.size()+vec2.size());
sort( ia, ia +12 );
sort( ia2, ia2+12 );
// печатается:
// 10 12 15 16 17 19 20 21 22 23 26 27 29 35
// 39 40 41 44 51 54 62 65 71 74
merge( ia, ia+12, ia2, ia2+12, ia_result );
for_each( ia_result, ia_result+24, pfi ); cout << "\n\n";
sort( vec1.begin(), vec1.end(), greater<int>() );
sort( vec2.begin(), vec2.end(), greater<int>() );
merge( vec1.begin(), vec1.end(),
vec2.begin(), vec2.end(),
vec_result.begin(), greater<int>() );
// печатается: 74 71 65 62 54 51 44 41 40 39 35 29 27 26 23 22
// 21 20 19 17 16 15 12 10
for_each( vec_result.begin(), vec_result.end(), pfi );
cout < <"\n\n";
}
Алгоритм mismatch()
template< class InputIterator1, class InputIterator2 >
pair<InputIterator1, InputIterator2>
mismatch( InputIterator1 first,
InputIterator1 last, InputIterator2 first2 );
template< class InputIterator1, class InputIterator2,
class BinaryPredicate >
pair<InputIterator1, InputIterator2>
mismatch( InputIterator1 first, InputIterator1 last,
InputIterator2 first2, BinaryPredicate pred );
#include <algorithm>
#include <list>
#include <utility>
#include <iostream.h>
class equal_and_odd{
public:
bool operator()( int ival1, int ival2 )
{
// оба значения равны друг другу?
// оба равны нулю? оба нечетны?
return ( ival1 == ival2 &&
( ival1 == 0 || ival1%2 ));
}
};
int main()
{
int ia[] = { 0,1,1,2,3,5,8,13 };
int ia2[] = { 0,1,1,2,4,6,10 };
pair<int*,int*> pair_ia = mismatch( ia, ia+7, ia2 );
// печатается: первая пара неодинаковых: ia: 3 и ia2: 4
cout << "первая пара неодинаковых: ia: "
<<*pair_ia.first << " и ia2: "
<< *pair_ia.second << endl;
list<int,allocator> ilist( ia, ia+7 );
list<int,allocator> ilist2( ia2, ia2+7 );
typedef list<int,allocator>::iterator iter;
pair<iter,iter> pair_ilist =
mismatch( ilist.begin(), ilist.end(),
ilist2.begin(), equal_and_odd() );
// печатается: первая пара неодинаковых: либо не равны, либо не нечетны:
// ilist: 2 и ilist2: 2
cout << "первая пара неодинаковых: либо не равны, "
<< "либо не нечетны: \n\tilist: "
<< *pair_ilist.first << " и ilist2: "
<< *pair_ilist.second << endl;
}
Алгоритм next_permutation()
template < class BidirectionalIterator >
bool
next_permutation( BidirectionalIterator first,
BidirectionalIterator last );
template < class BidirectionalIterator, class Compare >
bool
next_permutation( BidirectionalIterator first,
BidirectionalIterator last, class Compare );
#include <algorithm>
#include <vector>
#include <iostream.h>
void print_char( char elem ) { cout << elem ; }
void (*ppc)( char ) = print_char;
/* печатается:
ilmsu ilmus ilsmu ilsum ilums ilusm imlsu imlus
imslu imsul imuls imusl islmu islum ismlu ismul
isulm isuml iulms iulsm iumls iumsl iuslm iusml
limsu limus lismu lisum liums liusm lmisu lmius
lmsiu lmsui lmuis lmusi lsimu lsium lsmiu lsmui
lsuim lsumi luims luism lumis lumsi lusim lusmi
milsu milus mislu misul miuls miusl mlisu mlius
mlsiu mlsui mluis mlusi msilu msiul msliu mslui
msuil msuli muils muisl mulis mulsi musil musli
silmu silum simlu simul siulm siuml slimu slium
slmiu slmui sluim slumi smilu smiul smliu smlui
smuil smuli suilm suiml sulim sulmi sumil sumli
uilms uilsm uimls uimsl uislm uisml ulims ulism
ulmis ulmsi ulsim ulsmi umils umisl umlis umlsi
umsil umsli usilm usiml uslim uslmi usmil usmli
*/
int main()
{
vector<char,allocator> vec(5);
// последовательность символов: musil
vec[0] = 'm'; vec[1] = 'u'; vec[2] = 's';
vec[3] = 'i'; vec[4] = 'l';
int cnt = 2;
sort( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), ppc ); cout << "\t";
// генерируются все перестановки строки "musil"
while( next_permutation( vec.begin(), vec.end()))
{
for_each( vec.begin(), vec.end(), ppc );
cout << "\t";
if ( ! ( cnt++ % 8 )) {
cout < <"\n";
cnt = 1;
}
}
cout << "\n\n";
return 0;
}
Алгоритм nth_element()
template < class RandomAccessIterator >
void
nth_element( RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last );
template < class RandomAccessIterator, class Compare >
void
nth_element( RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last, Compare comp );
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
nth_element( &ia[0], &ia[6], &ia[2] );
{23,20,22,17,15,19,12,26,51,35,40,29}
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходный вектор: 29 23 20 22 17 15 26 51 19 12 35 40
вектор, отсортированный относительно элемента 26
12 15 17 19 20 22 23 26 51 29 35 40
вектор, отсортированный по убыванию относительно элемента 23
40 35 29 51 26 23 22 20 19 17 15 12
*/
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
vector< int,allocator > vec( ia, ia+12 );
ostream_iterator<int> out( cout," " );
cout << "исходный вектор: ";
copy( vec.begin(), vec.end(), out ); cout << endl;
cout << "вектор, отсортированный относительно элемента "
<< *( vec.begin()+6 ) << endl;
nth_element( vec.begin(), vec.begin()+6, vec.end() );
copy( vec.begin(), vec.end(), out ); cout << endl;
cout << " вектор, отсортированный по убыванию "
<< "относительно элемента "
<< *( vec.begin()+6 ) << endl;
nth_element( vec.begin(), vec.begin()+6,
vec.end(), greater<int>() );
copy( vec.begin(), vec.end(), out ); cout << endl;
}
Алгоритм partial_sort()
template < class RandomAccessIterator >
void
partial_sort( RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last );
template < class RandomAccessIterator, class Compare >
void
partial_sort( RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp );
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
partial_sort( &ia[0], &ia[5], &ia[12] );
{12,15,17,19,20,29,23,22,26,51,35,40}.
Алгоритм partial_sort_copy()
template < class InputIterator, class RandomAccessIterator >
RandomAccessIterator
partial_sort_copy( InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last );
template < class InputIterator, class RandomAccessIterator,
class Compare >
RandomAccessIterator
partial_sort_copy( InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp );
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
int ia2[5];
partial_sort_copy( &ia[0], &ia[7], &ia[12],
&ia2[0], &ia2[5] );
#include <algorithm>
#include <vector>
#include <iostream.h>
/*
* печатается:
исходный вектор: 69 23 80 42 17 15 26 51 19 12 35 8
результат применения partial_sort() к вектору: семь элементов
8 12 15 17 19 23 26 80 69 51 42 35
результат применения partial_sort_copy() к первым семи
элементам вектора в порядке убывания
26 23 19 17 15 12 8
*/
int main()
{
int ia[] = { 69,23,80,42,17,15,26,51,19,12,35,8 };
vector< int,allocator > vec( ia, ia+12 );
ostream_iterator<int> out( cout," " );
cout << "исходный вектор: ";
copy( vec.begin(), vec.end(), out ); cout << endl;
cout << "результат применения partial_sort() к вектору: "
<< "семь элементов \n";
partial_sort( vec.begin(), vec.begin()+7, vec.end() );
copy( vec.begin(), vec.end(), out ); cout << endl;
vector< int, allocator > res(7);
cout << " результат применения partial_sort_copy() к первым семи \n\t"
<< "элементам вектора в порядке убывания \n";
partial_sort_copy( vec.begin(), vec.begin()+7, res.begin(),
res.end(), greater<int>() );
copy( res.begin(), res.end(), out ); cout << endl;
}
Алгоритм partial_sum()
template < class InputIterator, class OutputIterator >
OutputIterator
partial_sum(
InputIterator first, InputIterator last,
OutputIterator result );
template < class InputIterator, class OutputIterator,
class BinaryOperation >
OutputIterator
partial_sum(
InputIterator first, InputIterator last,
OutputIterator result, BinaryOperation op );
#include <numeric>
#include <vector>
#include <iostream.h>
/*
* печатается:
элементы: 1 3 4 5 7 8 9
частичная сумма элементов:
1 4 8 13 20 28 37
частичная сумма элементов с использованием times<int>():
1 3 12 60 420 3360 30240
*/
int main()
{
const int ia_size = 7;
int ia[ ia_size ] = { 1, 3, 4, 5, 7, 8, 9 };
int ia_res[ ia_size ];
ostream_iterator< int > outfile( cout, " " );
vector< int, allocator > vec( ia, ia+ia_size );
vector< int, allocator > vec_res( vec.size() );
cout << "элементы: ";
copy( ia, ia+ia_size, outfile ); cout << endl;
cout << "частичная сумма элементов:\n";
partial_sum( ia, ia+ia_size, ia_res );
copy( ia_res, ia_res+ia_size, outfile ); cout << endl;
cout <<"частичная сумма элементов с использованием times<int>():\n";
partial_sum( vec.begin(), vec.end(), vec_res.begin(),
times<int>() );
copy( vec_res.begin(), vec_res.end(), outfile );
cout <<endl;
}
Алгоритм partition()
template < class BidirectionalIterator, class UnaryPredicate >
BidirectionalIterator
partition(
BidirectionalIterator first,
BidirectionalIterator last, UnaryPredicate pred );
#include <algorithm>
#include <vector>
#include <iostream.h>
class even_elem {
public:
bool operator()( int elem )
{ return elem%2 ? false : true; }
};
/*
* печатается:
исходная последовательность:
29 23 20 22 17 15 26 51 19 12 35 40
разбиение, основанное на четности элементов:
40 12 20 22 26 15 17 51 19 23 35 29
разбиение, основанное на сравнении с 25:
12 23 20 22 17 15 19 51 26 29 35 40
*/
int main()
{
const int ia_size = 12;
int ia[ia_size] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector<int, allocator > vec( ia, ia+ia_size );
ostream_iterator< int > outfile( cout, " " );
cout << "исходная последовательность: \n";
copy( vec.begin(), vec.end(), outfile ); cout << endl;
cout << "разбиение, основанное на четности элементов:\n";
partition( &ia[0], &ia[ia_size], even_elem() );
copy( ia, ia+ia_size, outfile ); cout << endl;
cout << "разбиение, основанное на сравнении с 25:\n";
partition( vec.begin(), vec.end(), bind2nd(less<int>(),25) );
copy( vec.begin(), vec.end(), outfile ); cout << endl;
}
Алгоритм prev_permutation()
template < class BidirectionalIterator >
bool
prev_permutation( BidirectionalIterator first,
BidirectionalIterator last );
template < class BidirectionalIterator, class Compare >
bool
prev_permutation( BidirectionalIterator first,
BidirectionalIterator last, class Compare );
#include <algorithm>
#include <vector>
#include <iostream.h>
// печатается: n d a n a d d n a d a n a n d a d n
int main()
{
vector< char, allocator > vec( 3 );
ostream_iterator< char > out_stream( cout, " " );
vec[0] = 'n'; vec[1] = 'd'; vec[2] = 'a';
copy( vec.begin(), vec.end(), out_stream ); cout << "\t";
// сгенерировать все перестановки "dan"
while( prev_permutation( vec.begin(), vec.end() )) {
copy( vec.begin(), vec.end(), out_stream );
cout << "\t";
}
cout << "\n\n";
}
Алгоритм random_shuffle()
template < class RandomAccessIterator >
void
random_shuffle( RandomAccessIterator first,
RandomAccessIterator last );
template < class RandomAccessIterator,
class RandomNumberGenerator >
void
random_shuffle( RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator rand);
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
vector< int, allocator > vec;
for ( int ix = 0; ix < 20; ix++ )
vec.push_back( ix );
random_shuffle( vec.begin(), vec.end() );
// печатает:
// random_shuffle для последовательности 1 .. 20:
// 6 11 9 2 18 12 17 7 0 15 4 8 10 5 1 19 13 3 14 16
cout << "random_shuffle для последовательности 1 .. 20:\n";
copy( vec.begin(), vec.end(), ostream_iterator<int >( cout,""));
}
Алгоритм remove()
template< class ForwardIterator, class Type >
ForwardIterator
remove( ForwardIterator first,
ForwardIterator last, const Type &value );
Алгоритм remove_copy()
template< class InputIterator, class OutputIterator,
class Type >
OutputIterator
remove_copy( InputIterator first, InputIterator last,
OutputIterator result, const Type &value );
#include <algorithm>
#include <vector>
#include <assert.h>
#include <iostream.h>
/* печатается:
исходный вектор:
0 1 0 2 0 3 0 4 0 5
вектор после remove до erase():
1 2 3 4 5 3 0 4 0 5
вектор после erase():
1 2 3 4 5
массив после remove_copy()
1 2 3 4 5
*/
int main()
{
int value = 0;
int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 };
vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout," ");
vector< int, allocator >::iterator vec_iter;
cout << "исходный вектор:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vec_iter = remove( vec.begin(), vec.end(), value );
cout << "вектор после remove до erase():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
// удалить из контейнера неподходящие элементы
vec.erase( vec_iter, vec.end() );
cout << "вектор после erase():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
int ia2[5];
vector< int, allocator > vec2( ia, ia+10 );
remove_copy( vec2.begin(), vec2.end(), ia2, value );
cout << "массив после remove_copy():\n";
copy( ia2, ia2+5, ofile ); cout << endl;
}
Алгоритм remove_if()
template< class ForwardIterator, class Predicate >
ForwardIterator
remove_if( ForwardIterator first,
ForwardIterator last, Predicate pred );
Алгоритм remove_copy_if()
template< class InputIterator, class OutputIterator,
class Predicate >
OutputIterator
remove_copy_if( InputIterator first, InputIterator last,
OutputIterator result, Predicate pred );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
0 1 1 2 3 5 8 13 21 34
последовательность после применения remove_if < 10:
13 21 34
последовательность после применения remove_copy_if четное:
1 1 3 5 13 21
*/
class EvenValue {
public:
bool operator()( int value ) {
return value % 2 ? false : true; }
};
int main()
{
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };
vector< int, allocator >::iterator iter;
vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
iter = remove_if( vec.begin(), vec.end(),
bind2nd(less<int>(),10) );
vec.erase( iter, vec.end() );
cout << "последовательность после применения remove_if < 10:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vector< int, allocator > vec_res( 10 );
iter = remove_copy_if( ia, ia+10, vec_res.begin(), EvenValue() );
cout << "последовательность после применения remove_copy_if четное:\n";
copy( vec_res.begin(), iter, ofile ); cout << '\n';
}
Алгоритм replace()
template< class ForwardIterator, class Type >
void
replace( ForwardIterator first, ForwardIterator last,
const Type& old_value, const Type& new_value );
Алгоритм replace_copy()
template< class InputIterator, class InputIterator,
class Type >
OutputIterator
replace_copy( InputIterator first, InputIterator last,
class OutputIterator result,
const Type& old_value, const Type& new_value );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
Christopher Robin Mr. Winnie the Pooh Piglet Tigger Eeyore
последовательность после применения replace():
Christopher Robin Pooh Piglet Tigger Eeyore
*/
int main()
{
string oldval( "Mr. Winnie the Pooh" );
string newval( "Pooh" );
ostream_iterator< string > ofile( cout, " " );
string sa[] = {
"Christopher Robin", "Mr. Winnie the Pooh",
"Piglet", "Tigger", "Eeyore"
};
vector< string, allocator > vec( sa, sa+5 );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout <<'\n';
replace( vec.begin(), vec.end(), oldval, newval );
cout << "последовательность после применения replace():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vector< string, allocator > vec2;
replace_copy( vec.begin(), vec.end(),
inserter( vec2, vec2.begin() ),
newval, oldval );
cout << "последовательность после применения replace_copy():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм replace_if()
template< class ForwardIterator, class Predicate, class Type >
void
replace_if( ForwardIterator first, ForwardIterator last,
Predicate pred, const Type& new_value );
Алгоритм replace_copy_if()
template<class ForwardIterator, class OutputIterator,
class Predicate, class Type >
OutputIterator
replace_copy_if( ForwardIterator first, ForwardIterator last,
class OutputIterator result,
Predicate pred, const Type& new_value );
#include <algorithm>
#include <vector>
#include <iostream.h>
/*
исходная последовательность:
0 1 1 2 3 5 8 13 21 34
последовательность после применения replace_if < 10 с заменой на 0:
0 0 0 0 0 0 0 13 21 34
последовательность после применения replace_if четное с заменой на 0:
0 1 1 0 3 5 0 13 21 0
*/
class EvenValue {
public:
bool operator()( int value ) {
return value % 2 ? false : true; }
};
int main()
{
int new_value = 0;
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };
vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( ia, ia+10, ofile ); cout << '\n';
replace_if( &ia[0], &ia[10],
bind2nd(less<int>(),10), new_value );
cout << "последовательность после применения replace_if < 10 "
<< "с заменой на 0:\n";
copy( ia, ia+10, ofile ); cout << '\n';
replace_if( vec.begin(), vec.end(),
EvenValue(), new_value );
cout << "последовательность после применения replace_if четное"
<< "с заменой на 0:\n";
copy( vec.begin(), vec.end(), ofile ); cout <<'\n';
}
Алгоритм reverse()
template< class BidirectionalIterator >
void
reverse( BidirectionalIterator first,
BidirectionalIterator last );
Алгоритм rotate()
template< class ForwardIterator >
void
rotate( ForwardIterator first,
ForwardIterator middle, ForwardIterator last );
Алгоритм rotate_copy()
template< class ForwardIterator, class OutputIterator >
OutputIterator
rotate_copy( ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
1 3 5 7 9 0 2 4 6 8 10
вращение вокруг среднего элемента(0) ::
0 2 4 6 8 10 1 3 5 7 9
вращение вокруг предпоследнего элемента(8) ::
8 10 1 3 5 7 9 0 2 4 6
rotate_copy вокруг среднего элемента ::
7 9 0 2 4 6 8 10 1 3 5
*/
int main()
{
int ia[] = { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10 };
vector< int, allocator > vec( ia, ia+11 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
rotate( &ia[0], &ia[5], &ia[11] );
cout << "вращение вокруг среднего элемента(0) ::\n";
copy( ia, ia+11, ofile ); cout << '\n';
rotate( vec.begin(), vec.end()-2, vec.end() );
cout << "вращение вокруг предпоследнего элемента(8) ::\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vector< int, allocator > vec_res( vec.size() );
rotate_copy( vec.begin(), vec.begin()+vec.size()/2,
vec.end(), vec_res.begin() );
cout << "rotate_copy вокруг среднего элемента ::\n";
copy( vec_res.begin(), vec_res.end(), ofile );
cout << '\n';
}
Алгоритм search()
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator
search( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
template< class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate >
ForwardIterator
search( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
Ожидаем найти подстроку 'ate': a t e
Ожидаем найти подстроку 'vat': v a t
*/
int main()
{
ostream_iterator< char > ofile( cout, " " );
char str[ 25 ] = "a fine and private place";
char substr[] = "ate";
char *found_str = search(str,str+25,substr,substr+3);
cout << "Ожидаем найти подстроку 'ate': ";
copy( found_str, found_str+3, ofile ); cout << '\n';
vector< char, allocator > vec( str, str+24 );
vector< char, allocator > subvec(3);
subvec[0]='v'; subvec[1]='a'; subvec[2]='t';
vector< char, allocator >::iterator iter;
iter = search( vec.begin(), vec.end(),
subvec.begin(), subvec.end(),
equal_to< char >() );
cout << "Ожидаем найти подстроку 'vat': ";
copy( iter, iter+3, ofile ); cout << '\n';
}
Алгоритм search_n()
template< class ForwardIterator, class Size, class Type >
ForwardIterator
search_n( ForwardIterator first, ForwardIterator last,
Size count, const Type &value );
template< class ForwardIterator, class Size,
class Type, class BinaryPredicate >
ForwardIterator
search_n( ForwardIterator first, ForwardIterator last,
Size count, const Type &value, BinaryPredicate pred );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
Ожидаем найти два вхождения 'o': o o
Ожидаем найти подстроку 'mou': m o u
*/
int main()
{
ostream_iterator< char > ofile( cout, " " );
const char blank = ' ';
const char oh = 'o';
char str[ 26 ] = "oh my a mouse ate a moose";
char *found_str = search_n( str, str+25, 2, oh );
cout << "Ожидаем найти два вхождения 'o': ";
copy( found_str, found_str+2, ofile ); cout < <'\n';
vector< char, allocator > vec( str, str+25 );
// найти первую последовательность из трех символов,
// ни один из которых не равен пробелу: mou of mouse
vector< char, allocator >::iterator iter;
iter = search_n( vec.begin(), vec.end(), 3,
blank, not_equal_to< char >() );
cout < <"Ожидаем найти подстроку 'mou': ";
copy( iter, iter+3, ofile ); cout < < '\n';
}
Алгоритм set_difference()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_difference( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_difference( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
Алгоритм set_intersection()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
Алгоритм set_symmetric_difference()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
Алгоритм set_union()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
#include <algorithm>
#include <set>
#include <string>
#include <iostream.h>
/* печатается:
элементы множества #1:
Иа-Иа Пух Пятачок Тигра
элементы множества #2:
Бука Пух Слонопотам
элементы set_union():
Бука Иа-Иа Пух Пятачок Слонопотам Тигра
элементы set_intersection():
Пух
элементы set_difference():
Иа-Иа Пятачок Тигра
элементы_symmetric_difference():
Бука Иа-Иа Пятачок Слонопотам Тигра
*/
int main()
{
string str1[] = { "Пух", "Пятачок", "Тигра", "Иа-Иа" };
string str2[] = { "Пух", "Слонопотам", "Бука" };
ostream_iterator< string > ofile( cout, " " );
set<string,less<string>,allocator> set1( str1, str1+4 );
set<string,less<string>,allocator> set2( str2, str2+3 );
cout << "элементы множества #1:\n\t";
copy( set1.begin(), set1.end(), ofile ); cout << "\n\n";
cout << "элементы множества #2:\n\t";
copy( set2.begin(), set2.end(), ofile ); cout << "\n\n";
set<string,less<string>,allocator> res;
set_union( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_union():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
res.clear();
set_intersection( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_intersection():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
res.clear();
set_difference( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_difference():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
res.clear();
set_symmetric_difference( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_symmetric_difference():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
}
Алгоритм sort()
template< class RandomAccessIterator >
void
sort( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
sort( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
Алгоритм stable_partition()
template< class BidirectionalIterator, class Predicate >
BidirectionalIterator
stable_partition( BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
29 23 20 22 17 15 26 51 19 12 35 40
устойчивое разбиение по четным элементам:
20 22 26 12 40 29 23 17 15 51 19
устойчивое разбиение по элементам, меньшим 25:
23 20 22 17 15 19 12 29 26 51 35 40
*/
class even_elem {
public:
bool operator()( int elem ) {
return elem%2 ? false : true;
}
};
int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > vec( ia, ia+12 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
stable_partition( &ia[0], &ia[12], even_elem() );
cout << "устойчивое разбиение по четным элементам:\n";
copy( ia, ia+11, ofile ); cout << '\n';
stable_partition( vec.begin(), vec.end(),
bind2nd(less<int>(),25) );
cout << "устойчивое разбиение по элементам, меньшим 25:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм stable_sort()
template<class RandomAccessIterator >
void
stable_sort( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
stable_sort( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
29 23 20 22 12 17 15 26 51 19 12 23 35 40
устойчивая сортировка - по умолчанию в порядке возрастания:
12 12 15 17 19 20 22 23 23 26 29 35 40 51
устойчивая сортировка: в порядке убывания:
51 40 35 29 26 23 23 22 20 19 17 15 12 12
*/
int main()
{
int ia[] = { 29,23,20,22,12,17,15,26,51,19,12,23,35,40 };
vector< int, allocator > vec( ia, ia+14 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
stable_sort( &ia[0], &ia[14] );
cout << "устойчивая сортировка - по умолчанию "
<< "в порядке возрастания:\n";
copy( ia, ia+14, ofile ); cout << '\n';
stable_sort( vec.begin(), vec.end(), greater<int>() );
cout << "устойчивая сортировка: в порядке убывания:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм swap()
template< class Type>
void
swap ( Type &ob1, Type &ob2 );
swap() обменивает значения объектов ob1 и ob2.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
3 4 5 0 1 2
после применения swap() в процедуре пузырьковой сортировки:
0 1 2 3 4 5
*/
int main()
{
int ia[] = { 3, 4, 5, 0, 1, 2 };
vector<int, allocator > vec( ia, ia+6 );
for ( int ix = 0; ix < 6; ++ix )
for ( int iy = ix; iy < 6; ++iy ) {
if ( vec[iy] < vec[ ix ] )
swap( vec[iy], vec[ix] );
}
ostream_iterator< int > ofile( cout, " ");
cout << "исходная последовательность:\n";
copy( ia, ia+6, ofile ); cout <<'\n';
cout << "после применения swap() в процедуре "
<< "пузырьковой сортировки:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм swap_ranges()
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator2
swap_ranges( ForwardIterator1 first1, ForwardIterator1 last,
ForwardIterator2 first2 );
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность элементов первого контейнера:
0 1 2 3 4 5 6 7 8 9
исходная последовательность элементов второго контейнера:
5 6 7 8 9
массив после перестановки двух половин:
5 6 7 8 9 0 1 2 3 4
первый контейнер после перестановки двух векторов:
5 6 7 8 9 5 6 7 8 9
второй контейнер после перестановки двух векторов:
0 1 2 3 4
*/
int main()
{
int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int ia2[] = { 5, 6, 7, 8, 9 };
vector< int, allocator > vec( ia, ia+10 );
vector< int, allocator > vec2( ia2, ia2+5 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность элементов первого контейнера:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
cout << "исходная последовательность элементов второго контейнера:\n";
copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';
// перестановка внутри одного контейнера
swap_ranges( &ia[0], &ia[5], &ia[5] );
cout << "массив после перестановки двух половин:\n";
copy( ia, ia+10, ofile ); cout << '\n';
// перестановка разных контейнеров
vector< int, allocator >::iterator last =
find( vec.begin(), vec.end(), 5 );
swap_ranges( vec.begin(), last, vec2.begin() );
cout << "первый контейнер после перестановки двух векторов:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
cout << "второй контейнер после перестановки двух векторов:\n";
copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';
}
Алгоритм transform()
template< class InputIterator, class OutputIterator,
class UnaryOperation >
OutputIterator
transform( InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation >
OutputIterator
transform( InputIterator1 first1, InputIterator1 last,
InputIterator2 first2, OutputIterator result,
BinaryOperation bop );
#include <algorithm>
#include <vector>
#include <math.h>
#include <iostream.h>
/*
* печатается:
исходный массив: 3 5 8 13 21
преобразование элементов путем удваивания: 6 10 16 26 42
преобразование элементов путем взятия разности: 3 5 8 13 21
*/
int double_val( int val ) { return val + val; }
int difference( int val1, int val2 ) {
return abs( val1 - val2 ); }
int main()
{
int ia[] = { 3, 5, 8, 13, 21 };
vector<int, allocator> vec( 5 );
ostream_iterator<int> outfile( cout, " " );
cout << "исходный массив: ";
copy( ia, ia+5, outfile ); cout << endl;
cout << "преобразование элементов путем удваивания: ";
transform( ia, ia+5, vec.begin(), double_val );
copy( vec.begin(), vec.end(), outfile ); cout << endl;
cout << "преобразование элементов путем взятия разности: ";
transform( ia, ia+5, vec.begin(), outfile, difference );
cout << endl;
}
Алгоритм unique()
template< class ForwardIterator >
ForwardIterator
unique( ForwardIterator first,
ForwardIterator last );
template< class ForwardIterator, class BinaryPredicate >
ForwardIterator
unique( ForwardIterator first,
ForwardIterator last, BinaryPredicate pred );
Алгоритм unique_copy()
template< class InputIterator, class OutputIterator >
OutputIterator
unique_copy( InputIterator first, InputIterator last,
OutputIterator result );
template< class InputIterator, class OutputIterator,
class BinaryPredicate >
OutputIterator
unique_copy( InputIterator first, InputIterator last,
OutputIterator result, BinaryPredicate pred );
#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
#include <assert.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;
void (*pfs)( string ) = print_elements;
int main()
{
int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 };
vector<int,allocator> vec( ia, ia+10 );
vector<int,allocator>::iterator vec_iter;
// последовательность не изменяется: нули не стоят рядом
// печатается: 0 1 0 2 0 3 0 4 0 5
vec_iter = unique( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// отсортировать вектор, затем применить unique: модифицируется
// печатается: 0 1 2 3 4 5 2 3 4 5
sort( vec.begin(), vec.end() );
vec_iter = unique( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// удалить из контейнера ненужные элементы
// печатается: 0 1 2 3 4 5
vec.erase( vec_iter, vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
string sa[] = { "enough", "is", "enough",
"enough", "is", "good" };
vector<string,allocator> svec( sa, sa+6 );
vector<string,allocator> vec_result( svec.size() );
vector<string,allocator>::iterator svec_iter;
sort( svec.begin(), svec.end() );
svec_iter = unique_copy( svec.begin(), svec.end(),
vec_result.begin() );
// печатается: enough good is
for_each( vec_result.begin(), svec_iter, pfs );
cout << "\n\n";
}
Алгоритм upper_bound()
template<class ForwardIterator, class Type >
ForwardIterator
upper_bound( ForwardIterator first,
ForwardIterator last, const Type &value );
template< class ForwardIterator, class Type, class Compare >
ForwardIterator
upper_bound( ForwardIterator first,
ForwardIterator last, const Type &value,
Compare comp );
int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};
#include <algorithm>
#include <vector>
#include <assert.h>
#include <iostream.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
vector<int,allocator> vec(ia,ia+12);
sort(ia,ia+12);
int *iter = upper_bound(ia,ia+12,19);
assert( *iter == 20 );
sort( vec.begin(), vec.end(), greater<int>() );
vector<int,allocator>::iterator iter_vec;
iter_vec = upper_bound( vec.begin(), vec.end(),
27, greater<int>() );
assert( *iter_vec == 26 );
// печатается: 51 40 35 29 27 26 23 22 20 19 17 15 12
vec.insert( iter_vec, 27 );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
}
Алгоритмы для работы с хипом
X T O G S M N A E R A I
Алгоритм make_heap()
template< class RandomAccessIterator >
void
make_heap( RandomAccessIterator first,
RandomAccessIterator last );
template<class RandomAccessIterator, class Compare >
void
make_heap( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
Алгоритм pop_heap()
template< class RandomAccessIterator >
void
pop_heap( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
pop_heap( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
Алгоритм push_heap()
template< class RandomAccessIterator >
void
push_heap( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
push_heap( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
Алгоритм sort_heap()
template< class RandomAccessIterator >
void
sort_heap( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
sort_heap( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
#include <algorithm>
#include <vector>
#include <assert.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector<int, allocator > vec( ia, ia+12 );
// печатается: 51 35 40 23 29 20 26 22 19 12 17 15
make_heap( &ia[0], &ia[12] );
void (*pfi)( int ) = print_elements;
for_each( ia, ia+12, pfi ); cout << "\n\n";
// печатается: 12 17 15 19 23 20 26 51 22 29 35 40
// минимальный хип: в корне наименьший элемент
make_heap( vec.begin(), vec.end(), greater<int>() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// печатается: 12 15 17 19 20 22 23 26 29 35 40 51
sort_heap( ia, ia+12 );
for_each( ia, ia+12, pfi ); cout <<"\n\n";
// добавим новый наименьший элемент
vec.push_back( 8 );
// печатается: 8 17 12 19 23 15 26 51 22 29 35 40 20
// новый наименьший элемент должен оказаться в корне
push_heap( vec.begin(), vec.end(), greater<int>() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// печатается: 12 17 15 19 23 20 26 51 22 29 35 40 8
// наименьший элемент должен быть заменен на следующий по порядку
pop_heap( vec.begin(), vec.end(), greater<int>() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
}
Назад
Содержание