Программирование на языке высокого уровня

3.7. Алгоритмы

Алгоритмы – это обобщенные процедуры для обработки элементов любых контейнеров. Описание большинства алгоритмов находится в файле <algorithm>.

Например, вычисление суммы всех элементов контейнера можно выполнить при помощи стандартного алгоритма:

list<double> x;

// вычисление суммы через итераторы
list<double>::iterator it;
for(it=x.begin(); it!=x.end(); it++)
{
	 sum+=(*it); 
}

// вычисление суммы через алгоритмы
sum=accumulate(x.begin(), x.end(), 0.0);

Обобщенные процедуры для обработки элементов любых контейнеров объявлены в файле <algorithm>. Можно выделить несколько групп алгоритмов в зависимости от того, модифицируют они контейнер или только лишь извлекают необходимую информацию:

Алгоритмы не модифицирующие контейнер

Алгоритмы не модифицирующие контейнер - это процедуры поиска и сравнения.

list<string> ls;

list<string>::const_iterator it;
// поиск значения "К8" в диапазоне от ls.begin() до ls.end()
it=find(ls.begin(), ls.end(), "К8");

Алгоритмы модифицирующие значение элементов контейнера

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

vector<int> v(100);

// заполнение всех элементов от ls.begin() до ls.end() значением 0
fill(v.begin(), v.end(), 0);
// замена всех элементов от ls.begin() до ls.end(), равных -1 на 1
replace(v.begin(), v.end(), -1, 1);

Алгоритмы модифицирующие контейнер

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

vector<int> v(100);

// сортировка массива
sort(v.begin(), v.end());
// перестановка элементов массива в обратном порядке
reverse(v.begin(), v.end());

Функции-помощники (перестановки и сравнения)

vector<int> v(100);
vector<int>::iterator it=v.begin();

it++;
swap(*v.begin(), *it);

Численные алгоритмы

Численные алгоритмы объявлены в файле <numeric>:

accumulate - накапливает результаты выполнения операций над последовательностью (сложение элементов)
inner_product - накапливает результаты выполнения операций над двумя последовательностями (перемножение)
partial_sum - позволяет получить последовательность инкрементных изменений (a, a+b, a+b+c, a+b+c+d, ...)
adjacent_difference - позволяет получить последовательность инкрементных изменений (a, b-a, c-b-a, d-c-b-a, ...)

Пример работы с алгоритмами

/////////////////////////////////////////////////////////////////////////////
// Программирование на языке высокого уровня. Основы языка С++
// Пример 3.9. Пример работы с алгоритмами библиотеки STL
// 
// http://aco.ifmo.ru/el_books/programming
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#include <iostream>   // подключение библиотеки ввода-вывода
#include <vector>     // подключение описания вектора
#include <iterator>   // подключение описания итераторов, нужно для использования ostream_iterator
#include <algorithm>  // подключение описания алгоритмов 
#include <numeric>    // подключение описания численных алгоритмов (accumulate, 
using namespace std;  // подключение стандартного пространства имен для использования библиотек

/////////////////////////////////////////////////////////////////////////////
void main()
{
    vector<int> v(10);  // создание вектора из 10 элементов
    vector<int>::iterator it; // объявление итератора

    // пример работы алгоритма заполнения fill и вывод на экран
    // заполнение элементов вектора от begin() до end() числом 0
    fill(v.begin(), v.end(), 0); 
    cout<<endl<<endl<<"fill ----------------------"<<endl; 
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    // изменение значений вектора и вывод результата на экран
    for(int i=0; i<v.size(); i++)
    {
        v[i]=i;
    }
    cout<<endl<<endl<<"cycle ---------------------"<<endl;
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    // вычисление суммы через алгоритм accumulate
    // просуммировать все элементы в диапазоне от begin() до end(), начальное значение 0
    int sum=accumulate(v.begin(), v.end(), 0);
    cout<<endl<<endl<<"sum -----------------------"<<endl;
    cout<<sum;

    // поиск
    // возвращает итератор на первое число в диапазоне от begin() до end(), равное 4
    it=find(v.begin(), v.end(), 4);
    cout<<endl<<endl<<"find ----------------------"<<endl;
    cout<<*it; // вывод значения элемента по итератору

    // замена
    // заменить в диапазоне от begin() до end() все числа равные 1 на -1
    replace(v.begin(), v.end(), 1, -1); 
    // заменить в диапазоне от begin() до end() все числа равные 5 на -5
    replace(v.begin(), v.end(), 5, -5); 
    cout<<endl<<endl<<"replace -------------------"<<endl;
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    // сортировка по возрастанию 
    sort(v.begin(), v.end());
    cout<<endl<<endl<<"sort ----------------------"<<endl;
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    // создание обратной последовательности
    reverse(v.begin(), v.end());
    cout<<endl<<endl<<"reverse -------------------"<<endl;
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    // перестановка двух элементов
    it=v.begin(); // итератор на 0-й элемент
    it++;         // итератор на 1-й элемент
    swap(*v.begin(), *it); // меняем местами элементы v.begin() и it
    cout<<endl<<endl<<"swap ----------------------"<<endl;
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout<<endl;
}
/////////////////////////////////////////////////////////////////////////////