stringtranslate.com

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

Стандартная библиотека шаблонов ( 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

Итераторы

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 (и шаблонного кода в целом):

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

Реализации

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

Примечания

  1. ^ Хольцнер, Стивен (2001). С++: Черная книга . Скоттсдейл, Аризона: Группа Кориолиса. п. 648. ИСБН 1-57610-777-9STL состоит из контейнеров , итераторов , объектов функций и алгоритмов .
  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. ^ Адриан Стоун. «Минимизация раздувания кода: чрезмерная специализация шаблонов».
  8. ^ Мейерс, Скотт (2005). Эффективное C++ Третье издание – 55 конкретных способов улучшить ваши проекты. Эддисон Уэсли . ISBN 0-321-33487-6.
  9. ^ Sutter, Herb ; Alexandrescu, Andrei (2004). C++ Coding Standards: 101 Rules, Guidelines, and Best Practices . Addison-Wesley. ISBN 0-321-11358-6.
  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 г. .

Ссылки

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