Стандартная библиотека шаблонов (STL ) - это программная библиотека для языка программирования C ++, который повлиял на многие части стандартной библиотеки C ++. Он предоставляет четыре компонента, называемых алгоритмами, контейнерами, функциями и итераторами.
. STL предоставляет набор общих классов для C ++, например контейнеры и ассоциативные массивы, которые можно использовать с любым встроенным типом и с любым определяемым пользователем типом, который поддерживает некоторые элементарные операции (например, копирование и присваивание). Алгоритмы STL не зависят от контейнеров, что значительно снижает сложность библиотеки.
STL достигает своих результатов за счет использования шаблонов. Этот подход обеспечивает полиморфизм времени компиляции, который часто более эффективен, чем традиционный полиморфизм времени выполнения. Современные компиляторы C ++ настроены так, чтобы минимизировать штрафы за абстракцию, возникающие из-за интенсивного использования STL.
STL была создана как первая библиотека общих алгоритмов и структур данных для C ++ с учетом четырех идей: универсальное программирование, абстрактность без потери эффективности, модель вычислений фон Неймана и семантика значений.
В ноябре 1993 года Александр Степанов представил библиотеку на основе универсального программирования для стандартизации C ++. Ответ комитета был в основном положительным и привел к запросу от Эндрю Кенига о формальном предложении к встрече в марте 1994 года. У комитета было несколько запросов об изменениях и расширениях, и члены комитета встретились со Степановым, чтобы помочь проработать детали. Требования для наиболее значимого расширения (ассоциативные контейнеры ) должны были быть согласованы путем их полной реализации, и Степанов делегировал эту задачу Дэвиду Массеру. Предложение было окончательно одобрено на заседании комитета ANSI / ISO в июле 1994 года. Впоследствии документ Степанова и Ли 17 был включен в черновой вариант стандарта ANSI / ISO C ++ (1, части пунктов с 17 по 27).
Перспективы раннего повсеместного распространения STL были значительно улучшены с решением Hewlett-Packard сделать его реализацию свободно доступной в Интернете в августе 1994 года. Эта реализация, разработанная Степановым, Ли, и Musser в процессе стандартизации, стали основой многих реализаций, предлагаемых сегодня поставщиками компиляторов и библиотек.
STL содержит последовательность контейнеров и ассоциативные контейнеры. Контейнеры - это объекты, в которых хранятся данные. Стандартные контейнеры последовательностей включают вектор
, deque
и список
. Стандартные ассоциативные контейнеры : set
, multiset
, map
, multimap
, hash_set
, hash_map
, hash_multiset
и hash_multimap
. Существуют также адаптеры контейнеров queue
, priority_queue
и stack
, которые представляют собой контейнеры с определенным интерфейсом, использующие другие контейнеры в качестве реализации.
Контейнер | Описание |
---|---|
Простые контейнеры | |
пара | Контейнер пары - это простой ассоциативный контейнер, состоящий из 2- кортежа элементов данных или объекты, называемые «первым» и «вторым», в этом фиксированном порядке. «Пара» STL может быть назначена, скопирована и сравнена. Массив объектов, размещенных на карте или hash_map (описанном ниже), по умолчанию имеет тип «пара», где все «первые» элементы действуют как уникальные ключи, каждый из которых связан со своими «вторыми» объектами значений. |
Последовательности (массивы / связанные списки ): упорядоченные коллекции | |
вектор | a динамический массив, например массив C (т. Е. Способный к произвольный доступ ) с возможностью автоматического изменения размера при вставке или стирании объекта. Вставка элемента в конец вектора занимает амортизированное постоянное время. Удаление последнего элемента занимает только постоянное время, потому что изменение размера не происходит. Вставка и стирание в начале или в середине линейны во времени. Для типа bool существует специализация, которая оптимизирует пространство, сохраняя значения bool в виде битов. |
список | a двусвязный список ; элементы не хранятся в непрерывной памяти. Противоположное представление от вектора. Медленный поиск и доступ (линейное время), но как только позиция была найдена, быстрая вставка и удаление (постоянное время). |
slist. | a односвязный список ; элементы не хранятся в непрерывной памяти. Противоположное представление от вектора. Медленный поиск и доступ (линейное время), но как только позиция была найдена, быстрая вставка и удаление (постоянное время). Он имеет немного более эффективную вставку и удаление и использует меньше памяти, чем двусвязный список, но его можно повторять только вперед. Он реализован в стандартной библиотеке C ++ как forward_list . |
deque (двусторонняя очередь ) | вектор с вставкой / стиранием в начале или конце в амортизируемый постоянное время, однако отсутствуют некоторые гарантии действительности итератора после изменения двухсторонней очереди. |
Адаптеры контейнера | |
очередь | Предоставляет интерфейс FIFO очереди с точки зрения push / pop / front / back operations. Любая последовательность, поддерживающая операции |
приоритетная очередь | Предоставляет приоритетную очередь интерфейс с точки зрения операций push / pop / top (элемент с наивысшим приоритетом находится сверху). Любая последовательность произвольного доступа, поддерживающая операции Элементы должны дополнительно поддерживать сравнение (чтобы определить, какой элемент имеет более высокий приоритет и должен быть извлечен первым). |
stack | Предоставляет интерфейс LIFO stack в терминах операций push / pop / top (последний вставленный элемент находится сверху). Любая последовательность, поддерживающая операции |
Ассоциативные контейнеры : неупорядоченные коллекции | |
набор | математический набор ; вставка / стирание элементов в наборе не делает недействительными итераторы, указывающие на набор. Предоставляет операции набора объединение, пересечение, разность, симметричная разность и тест включения. Тип данных должен реализовывать оператор сравнения < или должна быть указана пользовательская функция компаратора; такой оператор сравнения или функция компаратора должны гарантировать строгий слабый порядок, в противном случае поведение не определено. Обычно реализуется с использованием самобалансирующегося двоичного дерева поиска. |
мультимножества | , как и набор, но допускает дублирование элементов (математический мультимножество ). |
map | an ассоциативный массив ; позволяет отображать один элемент данных (ключ) в другой (значение). Тип ключа должен реализовывать оператор сравнения < или должна быть указана пользовательская функция компаратора; такой оператор сравнения или функция компаратора должны гарантировать строгое слабое упорядочение, в противном случае поведение не определено. Обычно реализуется с использованием самобалансирующегося двоичного дерева поиска. |
multimap | То же, что и карта, но допускает дублирование ключей. |
hash_set. hash_multiset. hash_map. hash_multimap | аналогично набору, мультимножеству, карте или нескольким картам, соответственно, но реализовано с использованием хеша таблица ; ключи не упорядочены, но для типа ключа должна существовать хэш-функция . Эти типы были исключены из стандарта C ++; похожие контейнеры были стандартизированы в C ++ 11, но с разными именами (unordered_set и unordered_map ). |
Другие типы контейнеров | |
bitset | хранят последовательности битов, аналогичные вектору bools фиксированного размера. Реализует побитовые операции и не имеет итераторов. Не последовательность. Предоставляет произвольный доступ. |
valarray | Другой тип данных массива, предназначенный для числового использования (особенно для представления векторов и матриц ); стандарт C ++ допускает определенные оптимизации для этой намеченной цели. По словам Джосуттиса, valarray был плохо спроектирован людьми, «которые покинули комитет [стандарт C ++] задолго до того, как стандарт был завершен», и поэтому следует отдавать предпочтение библиотекам шаблонов выражений . Предложенная переписать часть стандарта valarray в этом ключе была отклонена, вместо этого она стала разрешением на ее реализацию с использованием шаблона выражения. |
STL реализует пять различных типов итераторы. Это итераторы ввода (которые можно использовать только для чтения последовательности значений), итераторы вывода (которые можно использовать только для записи последовательности значений), итераторы вперед (которые можно читать, записывать и перемещать вперед), двунаправленные итераторы (которые подобны прямым итераторам, но могут также перемещаться назад) и итераторы произвольного доступа (которые могут свободно перемещаться на любое количество шагов за одну операцию).
Фундаментальная концепция STL - это диапазон, который представляет собой пару итераторов, обозначающих начало и конец вычисления, и большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны.
Возможно, чтобы двунаправленные итераторы действовали как итераторы с произвольным доступом, поэтому можно было бы продвинуться на десять шагов, просто продвигаясь вперед на шаг за один раз в общей сложности десять раз. Однако наличие отдельных итераторов произвольного доступа дает преимущества в эффективности. Например, вектор будет иметь итератор с произвольным доступом, а список - только двунаправленный итератор.
Итераторы - это основная особенность, обеспечивающая универсальность STL. Например, алгоритм реверсирования последовательности может быть реализован с использованием двунаправленных итераторов, а затем та же реализация может использоваться для списков, векторов и двухсторонних записей. Создаваемые пользователем контейнеры должны предоставлять только итератор, который реализует один из пяти стандартных интерфейсов итератора, и все алгоритмы, представленные в STL, могут использоваться в контейнере.
За эту общность также иногда приходится платить. Например, выполнение поиска в ассоциативном контейнере , таком как карта или набор, может быть намного медленнее при использовании итераторов, чем при вызове функций-членов, предлагаемых самим контейнером. Это связано с тем, что методы ассоциативного контейнера могут использовать информацию о внутренней структуре, которая непрозрачна для алгоритмов, использующих итераторы.
В STL предусмотрено большое количество алгоритмов для выполнения таких действий, как поиск и сортировка, каждый из которых требует определенного уровня итератора (и поэтому будет работать с любым контейнером, который предоставляет интерфейс с помощью итераторов). Алгоритмы поиска, такие как binary_search
и lower_bound
, используют двоичный поиск и подобные алгоритмы сортировки требуют, чтобы тип данных реализовывал оператор сравнения <
или пользовательская функция компаратора должна быть указано; такой оператор сравнения или функция компаратора должны гарантировать строгий слабый порядок. Помимо этого, предусмотрены алгоритмы для создания кучи из диапазона элементов, генерации лексикографически упорядоченных перестановок диапазона элементов, объединения отсортированных диапазонов и выполнения union, пересечения, разница отсортированных диапазонов.
STL включает классы, которые перегружают оператор вызова функции (operator ()
). Экземпляры таких классов называются функторами или объектами функций. Функторы позволяют параметризовать поведение связанной функции (например, с помощью аргументов, передаваемых в конструктор функтора) и могут использоваться для сохранения связанной информации о состоянии каждого функтора вместе с функцией. Поскольку как функторы, так и указатели функций могут быть вызваны с использованием синтаксиса вызова функции, они взаимозаменяемы в качестве аргументов шаблонов, когда соответствующий параметр появляется только в контекстах вызова функции.
Наиболее распространенным типом функтора является предикат. Например, такие алгоритмы, как find_if
, принимают унарный предикат , который работает с элементами последовательности. Такие алгоритмы, как sort, partial_sort, nth_element и все отсортированные контейнеры, используют предикат двоичный, который должен обеспечивать строгий слабый порядок, то есть он должен вести себя как членство проверка транзитивного, нерефлексивного и асимметричного бинарного отношения. Если ничего не указано, эти алгоритмы и контейнеры по умолчанию используют less, что, в свою очередь, вызывает оператор «меньше чем» <.
Качество реализации (QoI) компилятора C ++ имеет большое влияние на удобство использования STL (и шаблонного кода в целом):
copy_if
был исключен, хотя он был добавлен в C ++ 11.