Алгоритмы

Алгоритмы – наборы готовых функций, которые могут быть применены к контейнерам.

Условно можно поделить на 3 группы:

1)Алгоритмы для перебора элементов контейнера и выполнения определенных действий над каждым из элементов.

count – подсчет элементов;

find – поиск;

for_each – применение заданной функции к заданному диапазону элементов;

equal – сравнение двух элементов на равенство;

swap – меняет местами заданные два значения;

fill – заполняет диапазон заданными значениями;

remove – удаление элементов из заданного диапазона.

2)Алгоритмы для сортировки элементов контейнера.

sort – сортировка заданного диапазона;

binary_search - просматривает элементы от start до end в поисках значения val. Просматриваемые элементы между start и end должны быть упорядочены по возрастанию, что определено оператором <. (start, end – итераторы).

merge – объединение двух упорядоченных последовательностей, помещая результат в третью последовательность.

3)Алгоритмы для выполнения определенных арифметических действий над элементами контейнера.

accumulate – нахождение суммы элементов контейнера или подконтейнера;

inner_product - вычисляет сумму произведений двух контейнеров, по очереди прибавляя их к указанному пользователем начальному значению. Вторая версия алгоритма позволяет переопределить используемые по умолчанию операции сложения и умножения.

partial_sum – вычисляет частичную сумму элементов, расположенных в диапазоне [start,end) и располагает результат в result. (start, end, result – итераторы).

Пример:

#include <algorithm>

#include <numeric>

void main()

{

list<int> m;

list<int>::iterator it;

m.push_back(3);

m.push_back(2);

it = find (m.begin(), m.end(), 2); // получаем указатель на элемент с значением 2.

}

Реализация сортировки.

Не все контейнеры поддерживают sort. Например, list не поддерживает, а vector поддерживает.

Пример:

#include <algorithm>

#include <numeric>

#include <vector>

using namespace std;

void main()

{

vector<int> m;

m.push_back(2);

m.push_back(1);

m.push_back(5);

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

// сортировка по возрастанию (greater)

// сортировка по убыванию (less)

}

Функция суммирования accumulate – сумма всех элементов контейнера.

int v = accumulate(m.begin(), m.end(), 2);

//значение 2 будет прибавлено к полученной сумме.

26 Stl. Аллокаторы. Функциональные объекты. Строки. Аллокаторы.

Аллокаторы – обработчики, выполняющие размещение и освобождение элементов, сохраняемых в контейнерах.

Библиотека STL позволяет использовать стандартные аллокаторы, которые реализованы в библиотеке, и собственные аллокаторы, которые реализованы пользователем.

Пример (выделение и освобождение элементов массива):

#include <memory>

using namespace std;

void main()

{

allocator <int> a;

allocator <int>::pointer p;//указывает на выделенную память под элементы (тип элементов как в скобках)

p=a.allocate(10);//выделяет память под 10 элементов типа int

for(int i=0; i<10; i++)

{

p[i]=i;//заполнение памяти

}

a.deallocate(p,10); // 10 объектов в области, указываемой p, должны быть уничтожены до этого запроса.

}

Все контейнеры STL обладают стандартными аллокаторами, но можно создать и свой аллокатор со своим размещением в памяти.