Помимо контейнеров и итераторов, библиотека STL также предоставляет ряд универсальных алгоритмов для работы с элементами контейнеров. Они позволяют выполнять такие операции, как поиск, сортировка, вставка, изменение позиции, удаление и копирование элементов контейнера.
Алгоритмы STL
Алгоритмы STL реализованы в виде глобальных функций, которые работают с использованием итераторов. Это означает, что каждый алгоритм нужно реализовать всего лишь один раз, и он будет работать со всеми контейнерами, которые предоставляют набор итераторов (включая и ваши собственные (пользовательские) контейнерные классы). Хотя это имеет огромный потенциал и предоставляет возможность быстро писать сложный код, у алгоритмов также есть и «тёмная сторона» — некоторая комбинация алгоритмов и типов контейнеров может не работать/работать с плохой производительностью/вызывать бесконечные циклы, поэтому следует быть осторожным.
Библиотека STL предоставляет довольно много алгоритмов. На этом уроке мы затронем лишь некоторые из наиболее распространенных и простых в использовании алгоритмов. Для их работы нужно подключить заголовочный файл algorithm.
Алгоритмы min_element() и max_element()
Алгоритмы min_element() и max_element() находят минимальный и максимальный элементы в контейнере:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <list> #include <algorithm> int main() { std::list<int> li; for (int nCount=0; nCount < 5; ++nCount) li.push_back(nCount); std::list<int>::const_iterator it; // объявляем итератор it = min_element(li.begin(), li.end()); std::cout << *it << ' '; it = max_element(li.begin(), li.end()); std::cout << *it << ' '; std::cout << '\n'; } |
Результат выполнения программы:
Алгоритмы find() и list::insert()
В следующем примере мы используем алгоритм find(), чтобы найти определенное значение в списке, а затем используем функцию list::insert() для добавления нового значения в список:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <list> #include <algorithm> int main() { std::list<int> li; for (int nCount=0; nCount < 5; ++nCount) li.push_back(nCount); std::list<int>::iterator it; // объявляем итератор it = find(li.begin(), li.end(), 2); // ищем в списке число 2 li.insert(it, 7); // используем алгоритм list::insert() для добавления числа 7 перед числом 2 for (it = li.begin(); it != li.end(); ++it) // выводим с помощью цикла и итератора элементы списка std::cout << *it << ' '; std::cout << '\n'; } |
Результат выполнения программы:
Алгоритмы sort() и reverse()
В следующем примере мы отсортируем весь вектор, выведем отсортированные элементы, а затем выведем их в обратном порядке:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vect; vect.push_back(4); vect.push_back(8); vect.push_back(-3); vect.push_back(3); vect.push_back(-8); vect.push_back(12); vect.push_back(5); std::sort(vect.begin(), vect.end()); // выполняем сортировку элементов вектора std::vector<int>::const_iterator it; // объявляем итератор for (it = vect.begin(); it != vect.end(); ++it) // выводим с помощью цикла и итератора элементы вектора std::cout << *it << ' '; std::cout << '\n'; std::reverse(vect.begin(), vect.end()); // записываем элементы вектора в обратном порядке for (it = vect.begin(); it != vect.end(); ++it) // выводим с помощью цикла и итератора элементы вектора std::cout << *it << ' '; std::cout << '\n'; } |
Результат выполнения программы:
-8 -3 3 4 5 8 12
12 8 5 4 3 -3 -8
Обратите внимание, общий алгоритм sort() не работает с вектором. У вектора есть свой собственный метод sort(), который, в данном случае, является более эффективным.
Заключение
Хотя это всего лишь небольшой пример алгоритмов, которые предоставляет STL, но этого уже должно быть достаточно, чтобы вы увидели пользу и то, насколько легко использовать алгоритмы STL в сочетании с итераторами и контейнерами.
Не пойму, почему в циклах, как край перебираемого диапазона, используется конструкция
И еще не понятно это предложение: "Обратите внимание, общий алгоритм sort() не работает с вектором — у вектора есть свой собственный метод sort(), который, в данном случае, является более эффективным".
Здесь же применили общий sort() и он дал результат -8 -3 3 4 5 8 12 — отсортировал от меньшего к большему. Или я чего-то не понял?
Итератор может указывать на любой элемент контейнера или на «пустой» элемент контейнера.
Сделано это для того, например, что бы у контейнера с нулевым количеством элементов итератор имел смысл, т.е. указывал на «пустой» элемент.
Таким образом функции end() контейнеров (и глобальная std::end() ) обычно возвращают элемент следующий ЗА последним элементом контейнера (пустой элемент). А значит последовательно перебирая итераторы унарным оператором ++, мы можем точно так же достигнуть этого пустого элемента и тем самым понять, что мы достигли конца контейнера.
Поскольку у итераторов имеет смысл операция сравнения (итераторы понимают на что указывают и можно понять, указывают они на одно и тоже или нет), то условием окончания цикла устанавливают проверку, указывает ли наш итератор на последний элемент контейнера.
Замените слово "vector" на слово "list" и все будет правильно. В тексте действительно опечатка.
Добрый день!
С итераторами удобнее использовать auto:
и так:
и даже так:
И еще, метода sort() у вектора нет, зато есть у list. Например, во втором примере можно было отсортировать список так:
спасибо
Неплохо