Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Состав библиотеки алгоритмов
Все алгоритмы библиотеки можно разделить на такие группы [3]: · немодифицирующие алгоритмы (немутирующие алгоритмы); · модифицирующие алгоритмы (мутирующие алгоритмы); · сортировка последовательностей; · операции с множествами; · операции с пирамидами (кучей); · поиск экстремальных значений; · перестановки в лексикографическом порядке.
Всего в состав этих 7 категорий входит 60 функций. Немодифицирующие алгоритмы, как следует из их названия, не изменяют значения или числа элементов последовательностей. Таблица 1 Немодифицирующие алгоритмы
Модифицирующие алгоритмы объединены в одну группу по признаку того, что все они изменяют значения элементов последовательностей. Таблица 2 Модифицирующие алгоритмы
Таблица 3 Сортировка последовательностей
Таблица 4 Операции с множествами
Таблица 5 Операции с пирамидой
Таблица 6 Поиск экстремальных значений
Немодифицирующие алгоритмы Операция for_each(). template <class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);
Операция for_each() применяет f() к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f(). Функция должна быть унарной и выполнять доступ к элементам последовательности только на чтение. Функция f() применяется точно last-first раз. Если f() возвращает результат, то он игнорируется. Этот алгоритм рекомендуется применять всякий раз вместо явной записи цикла. Вряд ли меет смысл применять for_each() для накапливания информации об элементах контейнера (см. accumulate), поиска чего-либо в последовательности (см. find и find_if). Если ни одна из специализированных операций не подходит, то используйте for_each() для решения своей частной задачи.
Операция find(). template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value);
Операция find() возвращает первый итератор iter в диапазоне [first, last), для которого *iter == value. Если такой итератор не найден – возвращается last.
Операция find_if().
template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
Операция find_if() возвращает первый итератор iter в диапазоне [first, last), для которого pred(*iter) == true. Если такой итератор не найден, возвращается last. Другими словами, она находит первый попавшийся элемент последовательности, для которого функция-предикат pred возвратила значение true.
Операция find_first_of().
template<class FwdIt1, class FwdIt2> FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2); template<class FwdIt1, class FwdIt2, class Pred> FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2, Pred pr);
Первый вариант операции находит первое появление такого элемента в последовательности FwdIt1, значение которого равно значению любого элемента из последовательности FwdIt2. Если такое значение найдено, возвращается итератор, указывающий на позицию элемента в первой последовательности FwdIt1. Другими словами, функция определяет такое минимальное N из диапазона [0, last1 - first1), что для некоторого M из диапазона [0, last2 - first2) выражение *(first1 + N) == *(first2 + M) истинно. Если такое значение не найдено, операция возвращает last1. Второй вариант операции делает все то же самое, но вместо операции проверки на равенство == используется предикат pr. Операция adjacent_find().
template <class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred); Операция adjacent_find() возвращает первый итератор iter такой, что iter и iter+1 находятся в диапазоне [first, last) и для которого справедливо равенство *iter == *(iter + 1) или, для второго варианта операции, binary_pred(*iter, *(iter + 1)) == true. Если такой итератор iter не найден – возвращается last. Соответствующий предикат применяется, самое большее, max((last - first) - 1, 0) раз.
Операции count() и count_if(). template <class InputIterator, class T, class Size> size_t count(InputIterator first, InputIterator last, const T& value);
template <class InputIterator, class Predicate, class Size> size_t count_if(InputIterator first, InputIterator last, Predicate pred);
Операция count() подсчитывает число элементов диапазона [first, last) последовательности, значения которых равны заданному value, и возвращает это число. Операция count_if() подсчитывает число элементов диапазона [first, last) последовательности, для которых предикат pred возвращает true.
Операция mismatch().
template <class InputIterator1, class InputIterator2> pair <InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate> pair <InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
Операция mismatch() последовательно сравнивает соответствующие элементы двух последовательностей с целью поиска отличающихся элементов. Если такие элементы найдены, то возвращается пара итераторов, указывающих на эти элементы. Во втором варианте операции для сравнения используется предикат binary_pred. Если такие элементы не найдены, то возвращается пара last1 и first2 + (last1 - first1). Шаблон pair предназначен для инициализации и хранения двух итераторов, имеющих, возможно, разные типы.
Операция equal().
template <class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
Операция equal() возвращает true, если две последовательности равного размера имеют тождественные элементы, или значение false, если встречаются хотя бы два отличающихся элемента. Для проверки тождественности используется операция == или предикат binary_pred. Если число элементов последовательностей разное, то операция возвращает false.
Операция search().
template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
Операция search() предназначена для поиска в последовательности [first1,last1) первой подпоследовательности, идентичной другой последовательности [first2,last2). Для проверки идентичности используется операция == или предикат binary_pred.
Операция find_end(). template<class FwdIt1, class FwdIt2> FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2); template<class FwdIt1, class FwdIt2, class Pred> FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2, Pred pr);
Операцияfind_end() похожа на операцию search(), но отыскивает в последовательности [first1,last1) последнее появление подпоследовательности, идентичной другой последовательности [first2,last2). Для проверки идентичности используется операция == или предикат binary_pred.
Операция search_n() template<class FwdIt, class Dist, class T> FwdIt search_n(FwdIt first, FwdIt last, Dist Count, const T& val); template<class FwdIt, class Dist, class T, class Pred> FwdIt search_n(FwdIt first, FwdIt last, Dist Count, const T& val, Pred pr);
Операция search_n() предназначена для поиска заданного количества Count последовательных элементов последовательности, значения которых должны быть равны заданному значению val. Подобно другим операциям, эта операция также имеет две версии, отличающиеся способом проверки равенства. В случае успеха операция возвращает итератор, указывающий на первый из найденных элементов, а в противном случае – значение last. Пример программы, иллюстрирующей некоторые немодифицирующие алгоритмы // AlgTest.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "AlgTest.h" #include <Conio.h> #include <algorithm> // for_each, find, find_if #include <vector> #include <functional> // unary_function //… using namespace std; const int VectorSize =5; //Print – простейший объект-функция, выполняющая вывод аргумента на монитор template <class T> class Print : public unary_function<T, void> { public: void operator()(T& arg1) { cout<< arg1<<' '; } }; // GreaterThanTwo – объект-функция (предикат), которая возвращает // значение true, если аргумент превышает значение 2 template <class T> class GreaterThanTwo : public unary_function<T, bool> { public: bool operator()(T& arg1) { return (arg1>2); } }; // ShowElement – шаблонная функция, печатающая значение итератора itor, // указывающего на элемент последовательности Container. Если значение // итератора "законечное", то функция выводит строку "Last element!" template <class Container, class Iterator> void ShowElement(Container & c, Iterator & itor) { if(itor!= c.end()) cout<<*itor; else cout<<"Last element!"; } int _tmain(int argc, TCHAR* argv[], TCHAR* envp[]) { int nRetCode = 0; // initialize MFC and print and error on failure if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0)) { // TODO: change error code to suit your needs _tprintf(_T("Fatal Error: MFC initialization failed\n")); nRetCode = 1; } Print <int> DoPrint; vector <int> vInt(VectorSize); typedef vector <int>::iterator Itor; for(int i=0; i<VectorSize; i++)vInt[i]=i; Itor first = vInt.begin(); Itor last = vInt.end(); // вывести все элементы последовательности с помощью for_each // и объекта-функции DoPrint cout<<"Test method for_each()\n"; for_each(first,last,DoPrint); // 0 1 2 3 4 cout<<endl; // найти первый элемент вектора, значение которого равно 2 Itor retItor=find(first,last,2); cout<<"find(first,last,2)="; ShowElement(vInt,retItor); //find(first,last,2)=2 cout<<endl; // найти первый элемент вектора, значение которого равно 10 retItor=find(first,last,10); cout<<"find(first,last,10)="; ShowElement(vInt,retItor); //find(first,last,10)=Last element! cout<<endl; // найти первый элемент вектора, значение которого больше 2 GreaterThanTwo <int> isGreaterThanTwo; retItor=find_if(first,last,isGreaterThanTwo); cout<<"find_if(first,last,isGreaterThanTwo)="; ShowElement(vInt,retItor);//find_if(first,last,isGreaterThanTwo)=3 cout<<endl; // подсчитать число элементов вектора, значение которых равно 3 int retSize=count(first,last,3); cout<<"count(first,last,3)="<<retSize<<endl; //count(first,last,3)=1 // подсчитать число элементов вектора, значение которых больше 2 retSize=count_if(first,last,isGreaterThanTwo); cout<<"count_if(first,last,isGreaterThanTwo)="<<retSize<<endl; //count_if(first,last,isGreaterThanTwo)=2
_getch(); return nRetCode; } //вывод программы: //0 1 2 3 4 //find(first,last,2)=2 //find(first,last,10)=Last element! //find_if(first,last,isGreaterThanTwo)=3 //count(first,last,3)=1 //count_if(first,last,isGreaterThanTwo)=2
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2018-04-12; просмотров: 610. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |