Алгоритмы STL

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

find(iterator begin, iterator end, some_typy value) осуществляет поиск элемента в интервале. find(...) возвращает итератор, указывающий на первый найденный элемент, либо end, если подходящих элементов найдено не было.

vector<int> v;
for(int i = 1; i <= 100; i++) {
   v.push_back(i*i);
}

if(find(v.begin(), v.end(), 49) != v.end()) {
   // число 49 найдено в списке квадратов натуральных чисел, 
   // не превосходящих 100
}
else {
   // число 49 не найдено
}

Чтобы получить значение, итератор необходимо разыменовать. Это не актуально для алгоритма find(...), но будет активно использоваться в дальнейшем.

Если контейнер поддерживает итераторы произвольного доступа, то можно найти индекс найденного элемента. Для это из значения, которое вернул алгоритм, нужно вычесть начало интервала:

int i = find(v.begin(), v.end(), 49) - v.begin();
if(i < v.size()) {
   // 49 найдено
   assert(v[i] == 49);
}

Напомним, что для использования стандартных алгоритмов STL следует подключать модуль algorithm.

Алгоритмы min_element и max_element в пояснениях не нуждаются:

int data[5] = { 1, 5, 2, 4, 3 };
vector<int> X(data, data+5);

// Значение
int v1 = *max_element(X.begin(), X.end()); 

// Индекс
int i1 = min_element(X.begin(), X.end()) - X.begin()); 

int v2 = *max_element(data, data+5); 
// Либо же просто в массиве
int i3 = min_element(data, data+5) - data;

В рамках введения в экстремальное программирование следует присмотреться к следующему макросу:

#define all(c) c.begin(),c.end()

(скобки вокруг правой части здесь ставить ни в коем случае нельзя!)

Также часто используется алгоритм sort(iterator begin, iterator end).

vector<int> X;
...
sort(X.begin(), X.end()); // Стандартный вызов
sort(all(X)); // Почувствуйте разницу
sort(X.rbegin(), X.rend()); // Сортировка в обратном порядке

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

deque<int> q;
...
// Упорядочим элементы в q по неубыванию
vector<int> v(all(q)); 
// то же, что vector<int> v(q.begin(), q.end());
sort(all(v));
q.assign(all(v)); 
// то же, что q = deque<int>(all(v));