Алгоритми

Алгоритми STL призначені для роботи з контейнерами і іншими послідовностями. Кожен алгоритм реалізований у вигляді шаблону або набору шаблонів функції, тому може працювати з різними видами послідовностей і даними різноманітних типів. Для налаштування алгоритму на конкретні вимоги користувача застосовуються функціональні об'єкти. Використання стандартних алгоритмів, як і інших засобів стандартної бібліотеки, позбавляє програміста від написання, відлагодження і документування циклів обробки послідовностей, що зменшує кількість помилок в програмі, знижує час її розробки і робить її більш читаною і компактною. Оголошення стандартних алгоритмів знаходяться в заголовному файлі <algorithm>, стандартних функціональних об'єктів – у файлі <functional>.

Всі алгоритми STL можна розділити на чотири категорії:

– немодифікуючі операції з послідовностями;

– модифікуючі операції з послідовностями;

– алгоритми, пов'язані з сортуванням;

– алгоритми роботи з множинами і пірамідами;

Крім того, бібліотека містить узагальнені чисельні алгоритми, оголошення яких знаходяться у файлі <numeric>. В якості параметрів алгоритму передаються ітератори, що визначають початок і кінець оброблюваної послідовності. Вид ітераторів визначає типи контейнерів, для яких може використовуватися даний алгоритм. Наприклад, алгоритм сортування (sort) вимагає для своєї роботи ітератори довільного доступу, тому він не працюватиме з контейнером list. Алгоритми не виконують перевірку виходу за межі послідовності.

При описі параметрів шаблонів алгоритмів використовуються наступні скорочення:

In – ітератор для читання;

Out – ітератор для запису;

For – прямий ітератор;

Вi – двонаправлений ітератор;

Ran – ітератор довільного доступу;

Pred – унарний предикат (умова);

Binpred – бінарний предикат;

Соmр – функція порівняння;

Ор – унарна операція;

BinOp – бінарна операція.

11.3.1 Немодифікуючі операції з послідовностями

Алгоритми цієї категорії продивляються послідовність, не змінюючи її значень.

Таблиця 11.3. Немодифікуючі операції з послідовностями

Розглянемо приклади використання деяких алгоритмів.

Шаблон алгоритму adjacent_find:

tempiate<class For>For adjacent_find(For first,For last);

tempiate<class For, class BinPred>

For adjacent_find(For first, For last, BinPred pred);

Перша форма алгоритму знаходить в послідовному контейнері пару сусідніх однакових значень і повертає ітератор на перше з них або кінець послідовності (ітератор на елемент, наступний за останнім). Друга форма знаходить сусідні елементи, що задовольняють умові, заданій предикатом pred у вигляді функції або функціонального об'єкту.

Програма знаходження самої лівої пари однакових елементів цілочисельного масиву і пару елементів структури, у яких рівна сума полів):

#include <iostream>

#include <algorithm>

using namespace std;

struct A{ int x, y;};

bool f(A &a1, A& a2)

{

return a1.x + a1.y == a2.x + a2.y;

}