Стандартная библиотека шаблонов

Не путать со стандартной библиотекой C++ .

Для других применений см. STL .

Стандартная библиотека шаблонов ( 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++ (1, части пунктов с 17 по 27).

Перспективы скорейшего широкого распространения STL значительно улучшились после решения Hewlett-Packard сделать его реализацию свободно доступной в Интернете в августе 1994 года. Эта реализация, разработанная Степановым, Ли и Массером в процессе стандартизации, стала основой сегодня существует множество реализаций, предлагаемых поставщиками компиляторов и библиотек.

Состав

Контейнеры

STL содержит контейнеры последовательностей и ассоциативные контейнеры. Контейнеры — это объекты, в которых хранятся данные. Стандартные контейнеры последовательностей включают в себя vector, deque, и list. Стандартные ассоциативные контейнеры : set, multiset, map, multimap, hash_set, hash_map, hash_multiset и hash_multimap. Также имеются адаптеры для контейнеров. queue, priority_queue, и stack, которые представляют собой контейнеры с определенным интерфейсом, использующие другие контейнеры в качестве реализации.

Контейнер	Описание
Простые контейнеры
пара	Парный контейнер — это простой ассоциативный контейнер, состоящий из двух кортежей элементов или объектов данных, называемых «первым» и «вторым», в этом фиксированном порядке. «Пару» STL можно назначать, копировать и сравнивать. Массив объектов, выделенных на карте или hash_map (описанный ниже), по умолчанию имеет тип «пара», где все «первые» элементы действуют как уникальные ключи, каждый из которых связан со своими «вторыми» объектами значений.
Последовательности (массивы/ связанные списки ): упорядоченные коллекции.
вектор	динамический массив , такой как массив C (т. е. допускающий произвольный доступ ) с возможностью автоматического изменения размера при вставке или удалении объекта. Вставка элемента в конец вектора занимает амортизированное постоянное время . Удаление последнего элемента занимает постоянное время, поскольку изменение размера не происходит. Вставка и стирание в начале или в середине линейны во времени. Существует специализация типа bool , которая оптимизирует пространство, сохраняя значения bool в виде битов.
список	список двусвязный ; элементы не хранятся в непрерывной памяти. Противоположное представление от вектора. Медленный поиск и доступ (линейное время), но как только позиция найдена, быстрая вставка и удаление (постоянное время).
список	список односвязный ; элементы не хранятся в непрерывной памяти. Противоположное представление от вектора. Медленный поиск и доступ (линейное время), но как только позиция найдена, быстрая вставка и удаление (постоянное время). Он имеет немного более эффективную вставку и удаление и использует меньше памяти, чем двусвязный список, но его можно повторять только вперед. Он реализован в стандартной библиотеке C++ как forward_list.
deque ( двусторонняя очередь )	вектор со вставкой/стиранием в начале или конце в амортизированном постоянном времени , однако не имеет некоторых гарантий достоверности итератора после изменения дека.
Контейнерные адаптеры
очередь	Предоставляет FIFO интерфейс очереди с точки зрения push/ pop/ front/ back операции. Любая последовательность поддерживающих операций front(), back(), push_back(), и pop_front() может использоваться для создания экземпляра очереди (например, list и deque).
приоритетная очередь	Обеспечивает интерфейс приоритетной очереди с точки зрения push/pop/top операций (элемент с наивысшим приоритетом находится сверху). Любая последовательность произвольного доступа, поддерживающая операции front(), push_back(), и pop_back() может использоваться для создания экземпляра Priority_queue (например, vector и deque). Это реализовано с помощью кучи . Элементы должны дополнительно поддерживать сравнение (чтобы определить, какой элемент имеет более высокий приоритет и должен быть извлечен первым).
куча	Обеспечивает LIFO интерфейс стека с точки зрения push/pop/top операции (последний вставленный элемент находится сверху). Любая последовательность поддерживающих операций back(), push_back(), и pop_back() может использоваться для создания экземпляра стека (например, vector, list, и deque).
Ассоциативные контейнеры : неупорядоченные коллекции
набор	математический набор ; вставка/удаление элементов в наборе не делает недействительными итераторы, указывающие на набор. Предоставляет операции над множествами объединение , пересечение , разность , симметричную разность и проверку включения. Тип данных должен реализовывать оператор сравнения < или необходимо указать пользовательскую функцию сравнения; такой оператор сравнения или функция сравнения должны гарантировать строгий слабый порядок , в противном случае поведение не определено. Обычно реализуется с использованием самобалансирующегося двоичного дерева поиска .
мультимножество	то же, что набор, но допускает дублирование элементов (математическое мультимножество ).
карта	ассоциативный массив ; позволяет сопоставить один элемент данных (ключ) с другим (значением). Тип ключа должен реализовывать оператор сравнения < или необходимо указать пользовательскую функцию сравнения; такой оператор сравнения или функция сравнения должны гарантировать строгий слабый порядок , в противном случае поведение не определено. Обычно реализуется с использованием самобалансирующегося двоичного дерева поиска.
мультикарта	то же, что и карта, но допускает дублирование ключей.
hash_set hash_multiset hash_map hash_multimap	аналогично набору, мультинабору, карте или мультикарте соответственно, но реализован с использованием хеш-таблицы ; ключи не упорядочены, но хеш-функция для типа ключа должна существовать . Эти типы были исключены из стандарта C++; подобные контейнеры были стандартизированы в C++11 , но с другими именами ( unordered_set и unordered_map).
Другие типы контейнеров
набор битов	хранит последовательность битов, аналогичную вектору логических значений фиксированного размера. Реализует побитовые операции и не имеет итераторов. Не последовательность. Обеспечивает произвольный доступ.
валаррай	Другой тип данных массива, предназначенный для числового использования (особенно для представления векторов и матриц ); стандарт C++ допускает специальные оптимизации для этой цели. По словам Джосуттиса, valarray был плохо спроектирован людьми, «которые покинули комитет [стандарт C++] задолго до того, как стандарт был закончен», и шаблонов выражений . следует отдать предпочтение библиотекам Предлагаемое переписывание valarray в этом ключе была отвергнута, вместо этого став разрешением на его реализацию с использованием шаблона выражения. Часть стандарта

Итераторы

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

Фундаментальной концепцией STL является диапазон , представляющий собой пару итераторов, обозначающих начало и конец вычислений, а большинство алгоритмических шаблонов библиотеки, работающих со структурами данных, имеют интерфейсы, использующие диапазоны.

Двунаправленные итераторы могут действовать как итераторы с произвольным доступом, поэтому перемещение вперед на десять шагов можно выполнить, просто продвигаясь вперед шаг за шагом в общей сложности десять раз. Однако наличие отдельных итераторов с произвольным доступом дает преимущества в эффективности. Например, вектор будет иметь итератор произвольного доступа, а список — только двунаправленный итератор.

Итераторы — основная функция, обеспечивающая универсальность STL. Например, алгоритм обращения последовательности можно реализовать с помощью двунаправленных итераторов, а затем ту же реализацию можно использовать для списков, векторов и деков . созданные пользователем, Контейнеры, должны предоставлять только итератор, реализующий один из пяти стандартных интерфейсов итераторов, и в контейнере можно использовать все алгоритмы, предусмотренные в STL.

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

Алгоритмы

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

Функторы

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

Особенно распространенным типом функтора является предикат . Например, такие алгоритмы, как find_if возьмем унарный предикат, действующий на элементы последовательности. Такие алгоритмы, как sort, parts_sort, nth_element и все отсортированные контейнеры, используют двоичный предикат, который должен обеспечивать строгий слабый порядок , то есть он должен вести себя как проверка принадлежности транзитивного, нерефлексивного и асимметричного бинарного отношения . Если ничего не указано, эти алгоритмы и контейнеры по умолчанию используют less , что, в свою очередь, вызывает оператор «меньше чем» <.

Критика

Качество реализации компиляторов C++

Качество реализации (QoI) компилятора C++ оказывает большое влияние на удобство использования STL (и шаблонного кода в целом):

• Сообщения об ошибках, связанных с шаблонами, обычно очень длинные и их трудно расшифровать. Эта проблема считается настолько серьезной, что был написан ряд инструментов, которые упрощают и красиво выводят сообщения об ошибках, связанных с STL, чтобы сделать их более понятными.
• Неосторожное использование шаблонов может привести к раздуванию кода . Этому можно противостоять с помощью специальных методов в реализациях STL (например, использование внутренних контейнеров void* и других методов «шаблона диеты») и улучшения методов оптимизации компиляторов. Однако этот симптом аналогичен наивному ручному копированию набора функций для работы с другим типом, поскольку и того, и другого можно избежать, если проявить осторожность и хорошую технику.
• Создание экземпляра шаблона может увеличить время компиляции и использование памяти в обмен на обычное сокращение процесса принятия решений во время выполнения (например, с помощью виртуальных функций). Пока технология компиляции не улучшится, эту проблему можно лишь частично устранить путем тщательного кодирования, избегания определенных идиом и просто не использования шаблонов там, где они неуместны или где производительность во время компиляции имеет приоритет.

Другие проблемы

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

Реализации

• Оригинальная реализация STL Степанова и Ли. 1994 год, Хьюлетт-Паккард . Больше не поддерживается.
  • SGI STL, основанный на оригинальной реализации Степанова и Ли. 1997, Кремниевая графика . Больше не поддерживается.
    • STLPort на основе SGI STL.
    • Стандартная библиотека Rogue Wave (HP, SGI, SunSoft , Siemens-Nixdorf )
    • Стандартная библиотека Apache C++ (отправной точкой для этой библиотеки стала версия стандартной библиотеки Rogue Wave 2005 года). )
    • Libstdc++ использует код, полученный из SGI STL, для алгоритмов и контейнеров, определенных в C++03 .
• Библиотека Dinkum STL от PJ Plauger
• Microsoft STL , поставляемый с Visual C++, является лицензионным производным от Dinkum STL. Исходный код доступен на Github .
• EASTL , разработанный Полом Педрианой из Electronic Arts и опубликованный как часть EA Open Source .

См. также

• Список библиотек шаблонов C++
• С++11
• Повышение библиотеки C++

Ссылки

• Александр Степанов и Мэн Ли, Библиотека стандартных шаблонов. Технический отчет HP Laboratories 95-11(R.1), 14 ноября 1995 г. (Пересмотренная версия А.А. Степанова и М. Ли: Библиотека стандартных шаблонов, Технический отчет X3J16/94-0095, WG21/N0482, Проект языка программирования ISO C++). , май 1994 г.)
• Александр Степанов (2007). Замечания по программированию (PDF) . Степанов размышляет о конструкции STL.
• Николай М. Джосуттис (2000). Стандартная библиотека C++: учебное пособие и справочник . Аддисон-Уэсли. ISBN  0-201-37926-0 .
• Скотт Мейерс (2001). Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов . Аддисон-Уэсли. ISBN  0-201-74962-9 .
• Эл Стивенс (март 1995 г.). «Эл Стивенс берет интервью у Алекса Степанова» . Журнал доктора Добба . Проверено 18 июля 2007 г.
• Дэвид Вандевурде и Николай М. Джосуттис (2002). Шаблоны C++: Полное руководство . Аддисон-Уэсли Профессионал. ISBN  0-201-73484-2 .
• Атул Сайни и Дэвид Р. Массер . Учебное и справочное руководство по STL: Программирование на C++ с использованием стандартной библиотеки шаблонов. Предисловие Александра Степанова; Авторские права Modena Software Inc. Аддисон-Уэсли. ISBN  0-201-63398-1 .

Внешние ссылки

• Справочник по С++
• Справочник по C++ STL , включает функции C++11.
• Руководство программиста STL от SGI . Первоначально в [1] (устаревший контент).
• Справочник по классам стандартной библиотеки Apache (ранее Rogue Wave) C++
• Руководство пользователя стандартной библиотеки C++ Apache (ранее Rogue Wave)
• Бьерн Страуструп о появлении STL (страница 5, раздел 3.1)
• Стандартная спецификация C++