Алгоритмы и итераторы STL
Меньше кода циклов, больше выраженного намерения
Главная идея: Стандартная библиотека шаблонов (STL) делит работу с данными на три взаимодействующие части: контейнеры хранят данные, итераторы указывают в них, а алгоритмы из
<algorithm> выполняют работу. Итераторы - это клей: поскольку std::sort общается только с итераторами, один и тот же алгоритм работает и над vector, и над array, и над обычным Си-массивом.
К концу вы сможете:
- объяснить разделение на контейнер / итератор / алгоритм,
- правильно использовать полуоткрытый диапазон
[begin, end), - назвать пять категорий итераторов и что позволяет каждая,
- вызывать
sort,find,count_if,transformиaccumulateс лямбдами, - распознавать, где
rangesиз C++20 делают тот же код короче и безопаснее.
1. Три части, которые складываются вместе
До STL для каждой задачи писали свой цикл: один цикл для сортировки, другой для поиска, третий для суммирования. STL раскладывает это на переиспользуемые части. Алгоритм вроде std::sort знает, как сортировать, но ничего не знает о том, где лежат данные. Итератор - это маленький объект, ведущий себя как указатель: вы разыменовываете его через *it, чтобы прочитать элемент, и продвигаете через ++it. Контейнер вроде std::vector выдаёт вам итераторы через begin() и end().
Выигрыш - в переиспользовании: напишите алгоритм один раз, и он работает с любым контейнером, предоставляющим нужный вид итератора. Именно поэтому STL кажется небольшой, но делает так много.