Г. Шилтд - Самоучитель C++ (PDF) (1114887), страница 68
Текст из файла (страница 68)
Кроме этого, они позволяют одновременноработать с двумя контейнерами разных типов. Для доступа к алгоритмамбиблиотеки стандартных шаблонов в программу необходимо включить заголовок <algorithm>.В библиотеке стандартных шаблонов определяется большое число алгоритмов, которые систематизированы в табл. 14.5. Все алгоритмы представляютсобой функции-шаблоны. Это означает, что их можно использовать с контейнерами любых типов. Наиболее показательные варианты такого использования приведены в примерах данного раздела.Таблица 14.5. Алгоритмы библиотеки стандартных шаблоновАлгоритмНазначениеadjacentjflndВыполняет поиск смежных парных элементов впоследовательности.
Возвращает итератор первойпарыbfnary_searchВыполняет бинарный поиск в упорядоченной последовательностиСамоучитель C++454Таблица 14.5 (продолжение)АлгоритмНазначениеcopyКопирует последовательностьcopy_backwardАналогична функции сору{), за исключением того,что перемещает в начало последовательности элементы из ее концаcountВозвращает число элементов в последовательностиcount_IfВозвращает число элементов в последовательности,удовлетворяющих некоторому предикатуequalequal_rangeОпределяет идентичность двух диапазоновВозвращает диапазон, в который можно вставитьэлемент, не нарушив при этом порядок следованияэлементов в последовательностиfillЗаполняет диапазон заданным значениемfindВыполняет поиск диапазона для значения и возвращает первый найденный элементfind_endВыполняет поиск диапазона для подпоследовательности.
Функция возвращает итератор конца подпоследовательности внутри диапазонаfind_first_ofНаходит первый элемент внутри последовательности, парный элементу внутри диапазонаfindjfВыполняет поиск диапазона для элемента, для которого определенный пользователем унарный предикат возвращает истинуfor_eachНазначает функцию диапазону элементовgenerategenerate.nПрисваивает элементам в диапазоне значения, возвращаемые порождающей функциейincludesОпределяет, включает ли одна последовательностьвсе элементы другой последовательностиinplace_mergeВыполняет слияние одного диапазона с другим. Обадиапазона должны быть отсортированы в порядкевозрастания элементов. Результирующая последовательность сортируетсяiter_swapМеняет местами значения, на которые указываютдва итератора, являющиеся аргументами функцииlexicographical_compareСравнивает две последовательности в алфавитномпорядкеlower_boundОбнаруживает первое значение в последовательности, которое не меньше заданного значенияmake_heapВыполняет пирамидальную сортировку последовательности (пирамида, на английском языке heap, —полное двоичное дерево, обладающее тем свойством, что значение каждого узла не меньше значениялюбого из его дочерних узлов.
— Примеч. пер.)Глава 14. Библиотека стандартных шаблонов455Таблица 14.5 (продолжение)АлгоритмНазначениеmaxВозвращает максимальное из двух значенийmax elementВозвращает итераторвнутри диапазонаmergeВыполняет слияние двух упорядоченных последовательностей, а результат размещает в третьей последовательностиmlnВозвращает минимальное из двух значенийmin_elementВозвращает итератор минимального элемента внутри диапазонаmismatchОбнаруживает первое несовпадение между элементами в двух последовательностях. Возвращает итераторы обоих несовпадающих элементовnext_per mutationОбразует следующуюпоследовательностиnth_elementУпорядочивает последовательность таким образом,чтобы все элементы, меньшие заданного элементаЕ, располагались перед ним, а все элементы, большие заданного элемента Е, — после негоparti assortСортирует диапазонpartial_sort_copyСортирует диапазон, а затем копирует столько элементов, сколько войдет в результирующую последовательностьpartitionУпорядочивает последовательность таким образом,чтобы все элементы, для которых предикат возвращает истину, располагались перед элементами, длякоторых предикат возвращает ложьpop_heapМеняет местами первый и предыдущий перед последним элементы, а затем восстанавливает пирамидуprev_permutationОбразует предыдущуютельностиpush_heapРазмещает элемент на конце пирамидыrandom_shuffleБеспорядочно перемешивает последовательностьremoveremove_lfremove_copyre m ove_co py_ifУдаляет элементы из заданного диапазонаreplacereplacejfreplace_copyreplace_copy_ifЗаменяет элементы внутри диапазонаreversereverse_copyМеняет порядок сортировки элементов диапазона наобратныймаксимальногоперестановкуперестановкуэлемента(permutation)последова-Самоучитель C++456Таблица 14.5 (продолжение)АлгоритмНазначениеrotaterotate_copyВыполняет циклический сдвиг влево элементов вдиапазонеsearchВыполняет поиск подпоследовательностипоследовательностиsearch_nВыполняет поиск последовательности заданногочисла одинаковых элементовСоздает последовательность, которая содержит различающиеся участки двух упорядоченных наборовСоздает последовательность, которая содержитодинаковые участки двух упорядоченных наборовСоздает последовательность, которая содержитсимметричные различающиеся участки двух упорядоченных наборовСоздает последовательность, которая содержитобъединение (union) двух упорядоченных наборовset_differenceset_intersectionset_symmetric_dif fere neeset_unlonsortвнутриСортирует диапазонsort_heapСортирует пирамиду внутри диапазонаstable^partitionУпорядочивает последовательность таким образом,чтобы все элементы, для которых предикат возвращает истину, располагались перед элементами, длякоторых предикат возвращает ложь.
Разбиение наразделы остается постоянным; относительный порядок расположения элементов последовательностине меняетсяСортирует диапазон. Одинаковые элементы не переставляютсяstable_sortswapМеняет местами два значенияswap_rangesМеняет местами элементы в диапазонеtransformНазначает функцию диапазону элементов и сохраняет результат в новой последовательностиuniqueunique_copyУдаляет повторяющиеся элементы из диапазонаupper_boundОбнаруживает последнее значение в последовательности, которое не больше некоторого значения[Примерыl"""'''"^f1.
Одними из самых простых алгоритмов являются алгоритмы count() иcoimt_if(). Ниже представлены их основные формы:template<class Inlter, class T>size_t count(Inlter начало,Inlter окончание, const ТГлава14.Библиотекастандартныхшаблонов_457template<class Inlter, class T>size_t count (Inlter начало,Inlter окончание, UnFred &ф_предикат) ;Алгоритм count() возвращает число элементов в последовательности, начинаяс элемента, обозначенного итератором начало, и заканчивая элементом, обозначенным итератором окончание, значение которых равно параметру значение. Алгоритм countJfO возвращает число элементов в последовательности,начиная с элемента начало и заканчивая элементом окончание, для которыхунарный предикат ф_предикат возвращает истину.В следующей программе демонстрируются алгоритмы count() и count_if().// Демонстрация алгоритмов count и count_if^include <iostream>ttinclude <vector>^include <algoritm>using namespace std;/* это унарный предикат, который определяет, является ли значениечетным*/bool even(int x){return ! (x%2) ;int main { }{vector<int> v;int i ;for{i=0; i<20;i f ( i % 2 ) v.push_back(l) ;else v.push_back(2) ;cout « "Последовательность: ";for(i=0; i<v.size(}; i-н-) cout « v[i]cout « endl;int n;n = count ( v.
begin () , v.end(), 1);cout « n « " элементов равно 1\п";n = count_if (v. begin () , v.endO, even)cout « n « " четных элементов\п";return 0;_458СамоучительC++После выполнения программы на экране появится следующее:Последовательность:10 элементов равно 110 четных элементов2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1Программа начинается с создания 20- элементного вектора, содержащего чередующиеся значения 1 и 2. Для подсчета единиц используется алгоритмcount (), а для подсчета четных элементов — алгоритм count_if() Отметьте,как программируется унарный предикат even(). Все унарные предикаты получают в качестве параметра объект, тип которого тот же, что и тип объектовконтейнера, для работы с которым предназначен предикат. В зависимости отзначения этого объекта унарный предикат должен возвращать истину либоложь.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
