Алгоритмы

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

Каждый алгоритм использует итераторы определённого типа. Например, алгоритм простого поиска (find) просматривает элементы подряд, пока нужный не будет найден. Для такой процедуры вполне достаточно итератора ввода. С другой стороны, алгоритм более быстрого двоичного поиска (binary_search) должен иметь возможность переходить к любому элементу последовательности и поэтому требует итератора с произвольным доступом. Вполне естественно, что вместо менее функционального итератора можно передать алгоритму более функциональный, но не наоборот.

Все стандартные алгоритмы описаны в заголовочном файле algorithm, в пространстве имён std.

Ниже при описании прототипов некоторых алгоритмов будем использовать следующие обозначения итераторов:

OutIt - iterator вывода;

InIt - iterator ввода;

FwdIt - однонаправленный iterator;

BidIt - двунаправленный iterator;

RanIt - iterator прямого доступа.

Алгоритмы сортировки sort, partial_sort, sort_heap

Для сортировки данных в STL имеются различные алгоритмы. Рассмотрим некоторые из них.

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

template<class RanIt>

void sort(RanIt first, RanIt last);

template<class RanIt, class Pred>

void sort(RanIt first, RanIt last, Pred pr);

Действие первого из них основано на использовании перегруженной операции opepator<() для сортировки данных по возрастанию. Второй вариант заменяет операцию сравнения функцией сравнения pr(x,y), тем самым позволяя сортировать данные в порядке, определяемом пользователем.

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

void Print(int x)

{ cout << x <<' '; }

int main()

{ vector<int> v(4);

v[0] = 3;

v[1] = 1;

v[2] = 5;

v[3] = 2;

sort(v.begin(), v.end() );

for_each(v.begin(), v.end(), Print);

return 0;

}

Результатом работы программы будет массив

1 2 3 5

Использованный в программе алгоритм for_each полезен тогда, когда надо произвести перебор всех элементов контейнера и выполнить некоторое действие для каждого из них.

Для использования алгоритма sort с тремя параметрами требуется в качестве третьего аргумента использовать указатель на функцию или функциональный объект. Например, для сортировки в обратном порядке требуется включить заголовок<functional>:

sort(v.begin(), v.end(), greater<int>() );

Алгоритм partil_sort предназначен для сортировки только части массива.

Алгоритм sort_heap предназначен для сортировки накопителя.