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

редактировать

Стандартная библиотека шаблонов (STL ) - это программная библиотека для языка программирования C ++, который повлиял на многие части стандартной библиотеки C ++. Он предоставляет четыре компонента, называемых алгоритмами, контейнерами, функциями и итераторами.

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

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

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

Содержание

  • 1 История
  • 2 Состав
    • 2.1 Контейнеры
    • 2.2 Итераторы
    • 2.3 Алгоритмы
    • 2.4 Функции
  • 3 Критические замечания
    • 3.1 Качество реализации компиляторов C ++
    • 3.2 Другие проблемы
  • 4 Реализации
  • 5 См. Также
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки

История

В ноябре 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/ backoperations.

Любая последовательность, поддерживающая операции front (), back (), push_back ()и pop_front ()можно использовать для создания экземпляра очереди (например, listи deque).

приоритетная очередь Предоставляет приоритетную очередь интерфейс с точки зрения операций push / pop / top(элемент с наивысшим приоритетом находится сверху).

Любая последовательность произвольного доступа, поддерживающая операции front (), push_back ()и pop_back (), может использоваться для создания экземпляра priority_queue (например, вектори deque). Это реализовано с использованием кучи ..

Элементы должны дополнительно поддерживать сравнение (чтобы определить, какой элемент имеет более высокий приоритет и должен быть извлечен первым).

stack Предоставляет интерфейс LIFO stack в терминах операций push / pop / top(последний вставленный элемент находится сверху).

Любая последовательность, поддерживающая операции back (), push_back ()и pop_back (), может использоваться для создания экземпляра стека (например, vector, списоки двухсторонняя очередь).

Ассоциативные контейнеры : неупорядоченные коллекции
набор математический набор ; вставка / стирание элементов в наборе не делает недействительными итераторы, указывающие на набор. Предоставляет операции набора объединение, пересечение, разность, симметричная разность и тест включения. Тип данных должен реализовывать оператор сравнения <или должна быть указана пользовательская функция компаратора; такой оператор сравнения или функция компаратора должны гарантировать строгий слабый порядок, в противном случае поведение не определено. Обычно реализуется с использованием самобалансирующегося двоичного дерева поиска.
мультимножества, как и набор, но допускает дублирование элементов (математический мультимножество ).
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, что, в свою очередь, вызывает оператор «меньше чем» <.

Критика

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

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

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

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

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

Реализации

См. Также

Примечания

Ссылки

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

Последняя правка сделана 2021-06-09 07:37:16
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте