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

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

Стандартная библиотека шаблонов ( STL ) — это программная библиотека, изначально разработанная Александром Степановым для языка программирования C++ , которая повлияла на многие части стандартной библиотеки C++ . Она предоставляет четыре компонента, называемые алгоритмами , контейнерами , функциями и итераторами . ^[1]

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

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

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

STL и стандартная библиотека C++ — это две разные сущности. ^[3]

История

В ноябре 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_maphash_multisethash_multimap queuepriority_queuestack

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

Итераторы

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

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

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

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

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

Алгоритмы

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

Функторы

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

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

Критика

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

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

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

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

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

Реализации

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

Смотрите также

Примечания

^ Хольцнер, Стивен (2001). С++: Черная книга . Скоттсдейл, Аризона: Группа Кориолиса. п. 648. ИСБН 1-57610-777-9STL состоит из контейнеров , итераторов , объектов функций и алгоритмов .
^ Массер, Дэвид (2001). Учебное пособие и справочник STL: Программирование на C++ с использованием стандартной библиотеки шаблонов . Эддисон Уэсли . ISBN 0-201-37923-6.
^ Lightness Races in Orbit (5 марта 2011 г.). «В чем разница между «STL» и «C++ Standard Library»?». Stack Overflow . Получено 21 октября 2021 г. .
^ Джосуттис, Николай М. (1999). Стандартная библиотека C++: Учебное пособие и справочник . Addison-Wesley Professional. стр. 547. ISBN 9780201379266.
^ Вандевурде, Дэвид; Джосуттис, Николай М. (2002). Шаблоны C++: Полное руководство . Эддисон Уэсли . ISBN 0-201-73484-2.
^ Степанов, Александр; Ли, Мэн (31 октября 1995 г.). "The Standard Template Library" (PDF) . Получено 16 декабря 2018 г. . Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон — это пара итераторов, которые обозначают начало и конец вычисления. [...] в общем случае диапазон [i, j) относится к элементам в структуре данных, начиная с того, на который указывает i, и до того, на который указывает j, но не включая его. Диапазон [i, j) действителен тогда и только тогда, когда j достижим из i.
^ Адриан Стоун. «Минимизация раздувания кода: чрезмерная специализация шаблонов».
^ Мейерс, Скотт (2005). Эффективное C++ Третье издание – 55 конкретных способов улучшить ваши проекты. Эддисон Уэсли . ISBN 0-321-33487-6.
^ Sutter, Herb ; Alexandrescu, Andrei (2004). C++ Coding Standards: 101 Rules, Guidelines, and Best Practices . Addison-Wesley. ISBN 0-321-11358-6.
^ Андрей Александреску (6 мая 2009 г.). «Итераторы должны уйти» (PDF) . BoostCon 2009. Получено 19 марта 2011 г.
^ Мэтью Уилсон (февраль 2004 г.). «API перечисления обратных вызовов и концепция итератора ввода». Журнал доктора Добба .
^ Бьярне Страуструп (2000). Язык программирования C++ (3-е изд.). Addison-Wesley. ISBN 0-201-70073-5.^{: стр.530}
^ Еще алгоритмы STL (редакция 2)
^ "Стандартная библиотека Apache C++". stdcxx.apache.org . Получено 1 марта 2023 г. .

Ссылки

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

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

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

[1] Хольцнер, Стивен (2001). С++: Черная книга . Скоттсдейл, Аризона: Группа Кориолиса. п. 648. ИСБН 1-57610-777-9STL состоит из контейнеров , итераторов , объектов функций и алгоритмов .

[stltutorial-2] Массер, Дэвид (2001). Учебное пособие и справочник STL: Программирование на C++ с использованием стандартной библиотеки шаблонов . Эддисон Уэсли . ISBN 0-201-37923-6.

[3] Lightness Races in Orbit (5 марта 2011 г.). «В чем разница между «STL» и «C++ Standard Library»?». Stack Overflow . Получено 21 октября 2021 г. .

[4] Джосуттис, Николай М. (1999). Стандартная библиотека C++: Учебное пособие и справочник . Addison-Wesley Professional. стр. 547. ISBN 9780201379266.

[5] Вандевурде, Дэвид; Джосуттис, Николай М. (2002). Шаблоны C++: Полное руководство . Эддисон Уэсли . ISBN 0-201-73484-2.

[6] Степанов, Александр; Ли, Мэн (31 октября 1995 г.). "The Standard Template Library" (PDF) . Получено 16 декабря 2018 г. . Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон — это пара итераторов, которые обозначают начало и конец вычисления. [...] в общем случае диапазон [i, j) относится к элементам в структуре данных, начиная с того, на который указывает i, и до того, на который указывает j, но не включая его. Диапазон [i, j) действителен тогда и только тогда, когда j достижим из i.

[7] Адриан Стоун. «Минимизация раздувания кода: чрезмерная специализация шаблонов».

[effcpp-8] Мейерс, Скотт (2005). Эффективное C++ Третье издание – 55 конкретных способов улучшить ваши проекты. Эддисон Уэсли . ISBN 0-321-33487-6.

[cppcs-9] Sutter, Herb ; Alexandrescu, Andrei (2004). C++ Coding Standards: 101 Rules, Guidelines, and Best Practices . Addison-Wesley. ISBN 0-321-11358-6.

[itersmustgo-10] Андрей Александреску (6 мая 2009 г.). «Итераторы должны уйти» (PDF) . BoostCon 2009. Получено 19 марта 2011 г.

[11] Мэтью Уилсон (февраль 2004 г.). «API перечисления обратных вызовов и концепция итератора ввода». Журнал доктора Добба .

[12] Бьярне Страуструп (2000). Язык программирования C++ (3-е изд.). Addison-Wesley. ISBN 0-201-70073-5.^{: стр.530}

[13] Еще алгоритмы STL (редакция 2)

[14] "Стандартная библиотека Apache C++". stdcxx.apache.org . Получено 1 марта 2023 г. .