Студопедия

КАТЕГОРИИ:

АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Состав библиотеки алгоритмов




Все алгоритмы библиотеки можно разделить на такие группы [3]:

· немодифицирующие алгоритмы (немутирующие алгоритмы);

· модифицирующие алгоритмы (мутирующие алгоритмы);

· сортировка последовательностей;

· операции с множествами;

· операции с пирамидами (кучей);

· поиск экстремальных значений;

· перестановки в лексикографическом порядке.

 

Всего в состав этих 7 категорий входит 60 функций.

Немодифицирующие алгоритмы, как следует из их названия, не изменяют значения или числа элементов последовательностей.

Таблица 1

Немодифицирующие алгоритмы

for_each() Выполняет заданную операцию для каждого элемента последовательности
find() Находит первое вхождение элемента в последовательность
find_if() Находит первое соответствие предикату в последовательности
find_first_of() Находит значение из одной последовательности в другой
adjacent_find() Находит пару соседних значений
count() Подсчитывает количество вхождений данного значения в последовательность
count_if() Подсчитывает количество выполнений данного предиката в последовательности
mismatch() Находит первый несовпадающий элемент в двух последовательностях
equal() Проверяет тождественность двух последовательностей
search() Находит первое вхождение последовательности как подпоследовательности
find_end() Находит последнее вхождение последовательности как подпоследовательности
search_n() Находит n-е вхождение вхождение значения в последовательность

 

Модифицирующие алгоритмы объединены в одну группу по признаку того, что все они изменяют значения элементов последовательностей.

Таблица 2

Модифицирующие алгоритмы

transform() Выполняет заданную операцию над каждым элементом последовательности
copy() Копирует последовательность, начиная с первого элемента
copy_backward() Копирует последовательность, начиная с последнего элемента
swap() Меняет местами два элемента
iter_swap() Меняет местами два элемента, на которые указывают итераторы
swap_ranges() Меняет местами элементы двух последовательностей
replace() Заменяет элементы с указанным значением
replace_if() Заменяет элементы при выполнении предиката
replace_copy() Копирует последовательность, заменяя элементы с заданным значением
replace_copy_if() Копирует последовательность, заменяя элементы при выполнении предиката
fill() Заменяет все элементы заданным значением
fill_n() Заменяет первые n элементов заданным значением
generate() Заменяет все элементы результатом операции
generate_n() Заменяет первые n элементов результатом операции
remove() Удаляет элементы с заданным значением
remove_if() Подсчитывает количество вхождений данного значения в последовательность
remove_copy() Подсчитывает количество выполнений данного предиката в последовательности
remove_copy_if() Копирует последовательность, удаляя элементы, удовлетворяющие предикату
unique() Находит первый несовпадающий элемент в двух последовательностях
unique_copy() Проверяет тождественность двух последовательностей
reverse() Меняет порядок следования элементов на обратный
reverse_copy() Копирует последовательность в обратном порядке
rotate() Циклически перемещает элементы
rotate_copy() Копирует элементы в циклической последовательности
random_shuffle Перемещает элементы согласно случайному равномерному распределению («тасует» последовательность)

 

Таблица 3

Сортировка последовательностей

sort() Сортирует с хорошей средней эффективностью
stable_sort() Сортирует, сохраняя порядок равных элементов
partial_sort() Упорядочивает первую часть последовательности
partial_sort_copy() Копирует, упорядочивая первую часть последовательности
nth_element() Ставит на нужное место n-й элемент
lower_bound() Находит первое вхождение значения
upper_bound() Находит первый элемент, больший чем значение
equal_range() Находит подпоследовательность с данным значением
binary_search() Отыскивает указанное значение в отсортированной последовательности
merge() Объединяет две отсортированные последовательности
inplace_merge() Объединяет две последовательно отсортированные последовательности
partition() Перемещает вперед элементы, удовлетворяющие предикату
stable_partition() Перемещает вперед элементы, удовлетворяющие предикату, сохраняя при этом их относительный порядок следования

 

 

Таблица 4

Операции с множествами

includes() Проверяет принадлежность подмножества множеству
set_union() Конструирует отсортированное объединение множеств
set_intersection() Конструирует отсортированное пересечение множеств
set_difference() Конструирует отсортированное множество элементов, входящих в первую и не входящих во вторую последовательность
set_symmetric_difference() Конструирует отсортированное множество элементов, входящих лишь в одну из двух последовательностей

 

 

Таблица 5

Операции с пирамидой

make_heap() Подготавливает последовательность к использованию в качестве пирамиды
push_heap() Добавляет элемент в пирамиду
pop_heap() Удаляет элемент из пирамиды
sort_heap() Сортирует пирамиду

 

Таблица 6

Поиск экстремальных значений

min() Поиск меньшего из двух значений
max() Поиск большего из двух значений
min_element() Поиск минимального значения в последовательности
max_element() Поиск максимального значения в последовательности
lexicographical_compare() Лексикографическое сравнение двух последовательностей

 



Немодифицирующие алгоритмы

Операция 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 не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...