WikiSort.ru - Программирование

Библиотека стандартных шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

Библиотека стандартных шаблонов до включения в стандарт C++ была сторонней разработкой, вначале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода-вывода (iostream), подраздел Си и др.).

Проект под названием STLPort, основанный на SGI STL, осуществляет постоянное обновление STL, iostream и строковых классов. Некоторые другие проекты также занимаются разработкой частных применений стандартной библиотеки для различных конструкторских задач. Каждый производитель компиляторов C++ обязательно поставляет какую-либо реализацию этой библиотеки, так как она является очень важной частью стандарта и широко используется.

Архитектура STL была разработана Александром Степановым и Менг Ли.

Структура библиотеки

В библиотеке выделяют пять основных компонентов:

1. Контейнер (англ. container) — хранение набора объектов в памяти.
2. Итератор (англ. iterator) — обеспечение средств доступа к содержимому контейнера.
3. Алгоритм (англ. algorithm) — определение вычислительной процедуры.
4. Адаптер (англ. adaptor) — адаптация компонентов для обеспечения различного интерфейса.
5. Функциональный объект (англ. functor) — сокрытие функции в объекте для использования другими компонентами.

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

Контейнеры

Контейнеры библиотеки STL можно разделить на четыре категории: последовательные, ассоциативные, контейнеры-адаптеры и псевдоконтейнеры.

Контейнер	Описание
Последовательные контейнеры
vector[1]	C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за ${\displaystyle O(1)}$ . Добавление-удаление элемента в конец vector занимает амортизированное ${\displaystyle O(1)}$ время, та же операция в начале или середине vector — ${\displaystyle O(n)}$ . Стандартная быстрая сортировка за ${\displaystyle O(n\log(n))}$ . Поиск элемента перебором занимает ${\displaystyle O(n)}$ . Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.
list[2]	Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из-за большего времени доступа к элементу. Доступ по индексу за ${\displaystyle O(n)}$ . В любом месте контейнера вставка и удаление производятся очень быстро — за ${\displaystyle O(1)}$ .
deque[3]	Двухсторонняя очередь. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за ${\displaystyle O(1)}$ . Реализован в виде двусвязанного списка линейных массивов. С другой стороны, в отличие от vector, двухсторонняя очередь не гарантирует расположение всех своих элементов в непрерывном участке памяти, что делает невозможным безопасное использование арифметики указателей[4] для доступа к элементам контейнера[5][6].
Ассоциативные контейнеры
set	Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.
multiset	То же что и set, но позволяет хранить повторяющиеся элементы.
map	Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.
multimap	То же что и map, но позволяет хранить несколько одинаковых ключей.
Контейнеры-адаптеры
stack	Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.
queue	Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.
priority_queue	Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.
Псевдоконтейнеры
bitset	Служит для хранения битовых масок. Похож на vector<bool> фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.
basic_string	Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности. Элементы должны быть POD'ами. Определена конкатенация с помощью +.
valarray	Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Определены операции над двумя valarray и над valarray и скаляром (поэлементные). Эти операции возможно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками SIMD.

В контейнерах для хранения элементов используется семантика передачи объектов по значению. Другими словами, при добавлении контейнер получает копию элемента. Если создание копии нежелательно, то используют контейнер указателей на элементы. Присвоение элементов реализуется с помощью оператора присваивания, а их уничтожение происходит с использованием деструктора. В таблице приведены основные требования к элементам в контейнерах:

Все «полноценные» стандартные контейнеры удовлетворяют определённому набору требований (или соглашений). В приведённой ниже таблице полагается, что С — класс контейнера, содержащий объекты типа Т.

Итераторы

В библиотеке STL для доступа к элементам в качестве посредника используется обобщённая абстракция, именуемая итератором. Каждый контейнер поддерживает «свой» вид итератора, который представляет собой «модернизированный» интеллектуальный указатель^[7], «знающий» как получить доступ к элементам конкретного контейнера. Стандарт C++ определяет пять категорий итераторов, описанных в следующей таблице:

См. также

• Шаблоны C++
• Обобщённое программирование
• Объектно-ориентированное программирование
• Повторное использование кода
• C++
• Boost

Примечания

Ссылки

• Справочник классов и методов SGI STL, исходники (англ.)
• STL по шагам (рус.) — статьи Артема Каева
• Основы C++. Библиотека STL (рус.) — архив рассылки
• STL — Стандартная библиотека шаблонов. Руководство C++ программиста (рус.) — подробное руководство
• Использование STL в C++ (рус.)

Литература

• Скотт Мейерс. Эффективное использование STL = Effective STL. — Питер, 2002. — С. 224. — (Библиотека программиста). — ISBN 5-94723-382-7.
• Дэвид Р. Мюссер, Жилмер Дж. Дердж, Атул Сейни. C++ и STL: справочное руководство = STL Tutorial and Reference Guide: C++ Programming with the Standard Template. — 2-е издание. — М.: «Вильямс», 2010. — С. 432. — (серия C++ in Depth). — ISBN 5-89818-027-3.
• Леен Аммерааль. STL для программистов на C++ = STL for C++ programmers. — ДМК Пресс, 1999. — С. 240. — ISBN 5-256-00704-1.

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.