Программирование • 25 октября 2024 • 5 мин чтения

STL: стандартная библиотека шаблонов C++

Рассказываем, из чего состоит стандартная библиотека C++, что такое контейнеры, алгоритмы и итераторы, какие ещё полезные шаблоны есть в STL.

Структура библиотеки STL

Стандарт языка программирования C++ состоит из двух частей:

Core Guidelines. Это ядро языка, которое включает в себя указания по поводу того, каким должен быть корректный код и как он должен работать.
Стандартная библиотека шаблонов (англ. Standard Template Library, STL). Это набор классов и функций в C++, которые по умолчанию поставляются вместе с компилятором и решают большинство задач. Чаще всего разработчики называют её просто стандартной библиотекой.

Поговорим подробнее о структуре STL. Чтобы использовать шаблон из библиотеки, в C++ нужно подключить соответствующий header — заголовок. Примеры разделов стандартной библиотеки:

Контейнеры. Обеспечивают хранение различных данных и предоставляют механизмы доступа к ним.
Алгоритмы. Выполняют различные операции над данными, хранящимися в контейнерах.
Итераторы. Используются для перемещения по элементам контейнера и доступа к их значениям. Итераторы в STL позволяют использовать одни и те же алгоритмы с разными типами контейнеров.
Функциональные объекты. Содержат инструменты для использования функционального стиля в C++ — например, позволяют использовать функцию как объект.
Утилиты. Вспомогательные функции и классы для работы с другими компонентами STL.

Схема контейнеров стандартной библиотеки шаблонов C++, которая позволяет разработчикам сосредоточиться на логике программы, а не на деталях реализации. Источник: Wikipedia

Разобраться, как использовать STL в программировании, можно на курсе «Разработчик C++». С нуля за 9 месяцев студенты учатся писать эффективный код, изучают алгоритмы и структуры данных языка, а по итогам обучения имеют портфолио из десяти проектов.

Разберём подробнее первые три раздела STL, которые программисты используют чаще всего.

Контейнеры

Контейнеры в C++ — это структуры данных в стандартной библиотеке, которыми разработчики пользуются постоянно. Они нужны для хранения и организации элементов определённого типа. По сути, контейнер — это объект, поддерживающий добавление в него других объектов.

Рассмотрим примеры контейнеров в STL.

1. Последовательные контейнеры

○ array (статический массив). Это набор элементов одного типа. Размер массива должен быть известен во время компиляции, что ограничивает его гибкость, но он полезен в ситуациях, когда требуется высокая эффективность. Главный плюс: array не использует медленные операции работы с динамической памятью.
○ vector (динамический массив). При работе с таким контейнером STL компьютер не производит лишних операций, но и не проводит проверок. К примеру, если обратиться к 15-му элементу вектора, нужно заранее проверить, что он существует. В противном случае программа может начать вести себя нестандартно.
○ list (двусвязный список). Обеспечивает быстрое добавление и удаление элементов в любом месте списка, позволяет перемещаться по нему и изменять порядок объектов.

2. Ассоциативные контейнеры

○ set (множество). Это контейнер STL, в котором хранится множество уникальных элементов. set чаще используется, чтобы проверить, есть ли в списке нужное значение.
○ map (ассоциативный массив, словарь). Нужен для хранения данных, к которым требуется быстрый доступ по ключу. Обеспечивает уникальность ключей, что делает его полезным для реализации словарей и других структур данных.

3. Контейнеры STL, не хранящие объекты

○ string_view. Шаблон стандартной библиотеки C++, который представляет собой обёртку над последовательностью символов. Он не владеет памятью и не копирует данные, а просто ссылается на существующую строку. Используется для работы с подстроками или частями строк без создания новых объектов.
○ mdspan. Это многомерный диапазон элементов. Полезен для описания блоков памяти фиксированного размера и обеспечивает быстрый доступ к элементам по индексу. Пригодится для работы с многомерными массивами и матрицами.

Возьмём для примера хранение финансовой информации в контейнерах STL. Код может быть таким:

// Храним в словаре (map) состояние банковских счетов.
map<string, int64_t> accounts;
accounts["Jeff"] = 10000000;
accounts["Bill"] = 50000000;
accounts["Elon"] = 100000000;
accounts["Mark"] = 150000000;

Алгоритмы

Алгоритмы в C++ — это функции стандартной библиотеки, которые подходят для работы с любыми контейнерами и типами данных. Они могут выполнять различные базовые операции. Например, find и binary_search используются для поиска, sort и stable_sort — для сортировки, а accumulate и partial_sum — для суммирования большого числа слагаемых.

В STL есть несколько видов алгоритмов:

● Немодифицирующие операции — не меняют порядок элементов в контейнере, а только обрабатывают их значения. Например, find, count, equal_range и adjacent_find.
● Модифицирующие операции — меняют порядок или значения элементов контейнера в стандартной библиотеке STL. Например, sort, reverse, rotate, unique.
● Алгоритмы для работы с итераторами — взаимодействуют только с ними, но не с контейнерами. Например, copy, swap, fill, generate.
● Алгоритмы поиска и сортировки — нужны, чтобы находить или сортировать элементы по определённому условию. Например, binary_search, lower_bound, upper_bound, merge.
● Генераторы — создают новые элементы или последовательности. Например, transform, accumulate, inner_product.

Представим, что нужно создать звуковой сигнал. Это можно сделать с помощью алгоритма STL:

std::vector<uint16_t> signal;
signal.reserve(48000);

using namespace std;
for (auto i : views::iota(0, 240)) {
// Алгоритм fill_n используется, чтобы создать прямоугольный
// сигнал — меандр.
fill_n(back_inserter(signal), 100, 10000);
fill_n(back_inserter(signal), 100, -10000);
}

Итераторы

Итераторы в STL — это обобщённые указатели для перебора элементов в контейнерах. Они указывают на элемент в последовательности и помогают перемещаться по ней. Это позволяет использовать алгоритмы, независимые от типа контейнера.

В стандартной библиотеке C++ есть несколько категорий итераторов:

● InputIterator — позволяет читать элементы.
● OutputIterator — используется для записи элементов.
● ForwardIterator — объединяет возможности InputIterator и OutputIterator.
● BidirectionalIterator — поддерживает движение как вперёд, так и назад.
● RandomAccessIterator — поддерживает быстрые перемещения на любое количество шагов.

Возьмём для примера задачу, когда нужно выбрать отличников класса, чтобы отправить их в поход. Код может быть таким:

// Отсортируем учеников по имени
ranges::sort(students, {}, &Student::name);
// Учеников с фамилиями на A–M поведёт в поход учитель
// физики. Учеников с фамилиями на N–Z — учитель химии.
// Найдём первого ученика на N. Он будет задан итератором:
auto iter = lower_bound(students, "N");
// Теперь отсортируем по оценкам отдельно обе половинки.
auto score_is_better = [](const Student& l, const Student& r) {
return l.score > r.score;
};
std::sort(students.begin(), iter, score_is_better); // От начала до iter.
std::sort(iter, students.end(), score_is_better); // От iter до конца.

Полезные шаблоны STL

Помимо контейнеров, алгоритмов и итераторов, в стандартной библиотеке C++ есть много интересных функций и классов, которые пригодятся разработчику.

● optional. Шаблон класса, который используется для хранения объекта, но может не содержать его. Он подходит для поиска, если есть вероятность отсутствия элемента.
● print. Функция для вывода текстовой информации в консоль. Ещё на этапе компиляции она может разобрать формат данных и определить, куда поставить каждый элемент.
● Хедеры времени. В STL есть отдельная библиотека для работы со временем, в которой содержатся шаблоны, например момент времени и длительность. Также там есть несколько видов часов, например system_clock или steady_clock. Хедеры времени позволяют проводить с ним разные операции — допустим, прибавить тысячу секунд к определённому моменту.
● memory. Умные указатели, которые отслеживают использование объектов и удаляют ненужные. В C++ нет сборщика мусора, и есть миф, что нужно вручную отслеживать лишние элементы и стирать их с помощью функций new и delete. Но в современном программировании лучше использовать умные указатели и другие способы, например хранение в статической памяти.
● atomic. Средство в STL для работы с переменными, которые могут быть изменены одновременно из разных потоков выполнения. Это позволяет избежать конфликтов при доступе к общим данным и обеспечить нормальную работу многопоточных программ.
● ranges. Раздел стандартной библиотеки шаблонов, который используется для упрощения работы с последовательностями элементов, например с массивами и векторами. Позволяет выполнять операции над диапазонами элементов без необходимости явного указания начала и конца последовательности. С помощью ranges можно организовать фильтрацию диапазона сразу по нескольким критериям. При этом шаблон не будет совершать лишних действий, а пройдёт один раз и сразу проверит элементы на соответствие всем критериям.

Совет эксперта

Георгий Осипов
При работе со стандартной библиотекой стоит не оглядываться в прошлое, а смотреть в будущее. То есть применять все нововведения STL, например ranges, которые не используют многие программисты. C++ — быстро меняющийся язык, но среди разработчиков есть некоторые стереотипы о нём, которые уже не соответствуют действительности. Если когда-то язык был сложным, то сейчас в нём появилось большое количество шаблонов, которые существенно упрощают работу.

Статью подготовили: