Введение

Библиотека программного обеспечения для языка программирования C++

Стандартная библиотека шаблонов (STL) – это библиотека программного обеспечения, первоначально разработанная Александром Степановым для языка программирования C++, оказавшая влияние на многие части стандартной библиотеки C++. Она предоставляет четыре компонента: алгоритмы, контейнеры, функции и итераторы. STL предоставляет набор общих классов для C++, таких как контейнеры и ассоциативные массивы, которые могут использоваться с любым встроенным типом и с любым пользовательским типом, поддерживающим некоторые элементарные операции (например, копирование и присваивание). Алгоритмы STL независимы от контейнеров, что значительно снижает сложность библиотеки. STL достигает своих результатов благодаря использованию шаблонов. Этот подход обеспечивает полиморфизм времени компиляции, который часто более эффективен, чем традиционный полиморфизм времени выполнения. Современные компиляторы C++ оптимизированы для минимизации накладных расходов, связанных с абстракцией при интенсивном использовании STL. STL была создана как первая библиотека универсальных алгоритмов и структур данных для C++, основываясь на четырех принципах: обобщенное программирование, абстрактность без потери производительности, модель вычислений фон Неймана и семантика значений. STL и стандартная библиотека C++ – это две различные сущности.

История

В ноябре 1993 года Александр Степанов представил библиотеку, основанную на обобщённом программировании, комитету ANSI/ISO по стандартизации C++. Реакция комитета была подавляюще положительной, что привело к просьбе Эндрю Кенига подготовить официальное предложение к мартовскому заседанию 1994 года. Комитет выдвинул несколько запросов об изменениях и дополнениях, и члены комитета встретились со Степановым и Менг Ли, чтобы помочь проработать детали. Для подтверждения согласованности наиболее значительного расширения (ассоциативных контейнеров) требовалось полностью реализовать их, и эту задачу Степанов поручил Дэвиду Муссеру. Предложение было окончательно одобрено на июльском заседании комитета ANSI/ISO в 1994 году. Впоследствии документ 17 Степанова и Ли был включён в проект стандарта ANSI/ISO C++ (части разделов 17–27). Перспективы раннего широкого распространения STL значительно улучшились благодаря решению Hewlett Packard в августе 1994 года сделать свою реализацию свободно доступной в Интернете. Эта реализация, разработанная Степановым, Ли и Муссером в процессе стандартизации, стала основой для многих реализаций, предлагаемых сегодня поставщиками компиляторов и библиотек.

Алгоритмы

В STL предоставлено большое количество алгоритмов для выполнения таких операций, как поиск и сортировка, каждый из которых реализован с учетом определенного уровня итераторов (и, следовательно, будет работать с любым контейнером, предоставляющим интерфейс через итераторы). Алгоритмы поиска, такие как, и алгоритмы, использующие бинарный поиск, а также алгоритмы сортировки требуют, чтобы тип данных поддерживал оператор сравнения или была указана пользовательская функция-компаратор; этот оператор сравнения или функция-компаратор должны гарантировать строгое слабое упорядочение. Помимо этого, предоставляются алгоритмы для построения кучи из диапазона элементов, генерации лексикографически упорядоченных перестановок диапазона элементов, слияния отсортированных диапазонов и выполнения операций объединения, пересечения и разности для отсортированных диапазонов.

Функторы

STL включает в себя классы, которые перегружают оператор вызова функции. Экземпляры таких классов называются функторами или функциональными объектами. Функторы позволяют параметризовать поведение связанной функции (например, через аргументы, переданные конструктору функтора) и могут использоваться для хранения информации о состоянии, относящейся к конкретному функтору, вместе с функцией. Поскольку как функторы, так и указатели на функции могут быть вызваны с использованием синтаксиса вызова функции, они взаимозаменяемы в качестве аргументов шаблонов, когда соответствующий параметр используется только в контексте вызова функции. Особенно распространенным типом функтора является предикат. Например, алгоритмы, такие как `take`, принимают унарный предикат, который оперирует элементами последовательности. Алгоритмы, такие как сортировка, частичная сортировка, nth_element и все отсортированные контейнеры, используют бинарный предикат, который должен обеспечивать строгое слабое упорядочение, то есть он должен вести себя как проверка принадлежности к транзитивному, нерефлексивному и асимметричному бинарному отношению. Если предикат не указан, эти алгоритмы и контейнеры по умолчанию используют оператор `less`, который, в свою очередь, вызывает оператор меньше `<`.

Другие вопросы

Инициализация STL-контейнеров константами непосредственно в исходном коде не так проста, как для структур данных, унаследованных от C (это было решено в C++11 с помощью списков инициализации). STL-контейнеры не предназначены для использования в качестве базовых классов (их деструкторы намеренно не являются виртуальными); наследование от контейнера – распространенная ошибка. Концепция итераторов, реализованная в STL, может быть сложна для понимания: например, если значение, на которое указывает итератор, удалено, сам итератор становится недействительным. Это частый источник ошибок. Большинство реализаций STL предоставляют режим отладки, который работает медленнее, но позволяет выявлять подобные ошибки при использовании. Аналогичная проблема существует и в других языках, например, в Java. Диапазоны предлагаются как более безопасная и гибкая альтернатива итераторам. Определенные шаблоны итерации, такие как API перевызова (callback), не могут быть адаптированы к модели STL без использования корутин, которые не входили в стандарт C++ до C++20. Соответствие компилятору не гарантирует, что объекты Allocator, используемые для управления памятью контейнеров, будут корректно работать с поведением, зависящим от состояния. Например, переносимая библиотека не может определить тип распределителя, который будет извлекать память из разных пулов, используя различные объекты этого типа распределителя. (Meyers, p. 50) (решено в C++11). Набор алгоритмов не является полным: например, алгоритм был исключен, хотя он был добавлен в C++11.