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

Не путать со стандартной библиотекой 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++