Standard Template Library

Standard Template Library

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

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

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

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

Содержание

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

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

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

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

Контейнеры

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

Контейнер Описание
Последовательные контейнеры
vector C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за O(1). Добавление-удаление элемента в конец vector занимает амортизированное O(1) время, та же операция в начале или середине vector — O(n). Стандартная быстрая сортировка за O(n * log(n)). Поиск элемента перебором занимает O(n). Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.
list Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из за большего времени доступа к элементу. Доступ по индексу за O(n). В любом месте контейнера вставка и удаление производятся очень быстро - за O(1). Благодаря этому достигается высокая эффективность автоматического упорядочивания элементов при вставке, что, в свою очередь, обеспечивает быстрый бинарный поиск за O(log(n)). Встроенная в контейнер сортировка эффективнее стандартной быстрой, и выполняется за O(n).
deque Очередь. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за O(1). Реализован в виде двусвязанного списка линейных массивов.
Ассоциативные контейнеры
set Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.
multiset То же что и set, но позволяет хранить повторяющиеся элементы.
map Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.
multimap То же что и map, но позволяет хранить повторяющиеся ключи.
Контейнеры-адаптеры
stack Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.
queue Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.
priority_queue Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.
Псевдоконтейнеры
bitset Служит для хранения битовых масок. Похож на vector<bool> фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.
basic_string Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности.
valarray Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Однако, в нём реализованы операции, которые можно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками
Метод Описание Примечание
Конструктор копии Создает новый элемент, идентичный старому Используется при каждой вставке элемента в контейнер
Оператор присваивания Заменяет содержимое элемента копией исходного элемента Используется при каждой модификации элемента
Деструктор Разрушает элемент Используется при каждом удалении элемента
Конструктор по умолчанию Создает элемент без аргументов Применяется только для определенных операций
operator== Сравнивает два элемента Используется при выполнении operator== для двух контейнеров
operator< Определяет, меньше ли один элемент другого Используется при выполнении operator< для двух контейнеров

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

Выражение Возвращаемый тип Сложность Примечание
C::value_type T Время компиляции
C::reference T Время компиляции
C::const_reference Время компиляции
C::pointer Тип указателя, указывающего на C::reference Время компиляции Указатель на Т
C::iterator Тип итератора, указывающего на C::reference Время компиляции Итератор любого типа, кроме итератора вывода
C::const_iterator Тип итератора, указывающего на C::const_reference Время компиляции Итератор любого типа, кроме итератора вывода
C::size_type Беззнаковый целочисленный тип Время компиляции
C obj; Постоянная После: obj.size() == 0
C obj1; obj1 = obj2; Линейная После: obj1 == obj2
C obj; (&obj)->~C(); Результат не используется Линейная После: a.size() == 0.
obj.begin() Постоянная
obj.end() Постоянная
obj1 == obj2 Обратимый в bool Линейная
obj1 != obj2 Обратимый в bool Линейная
obj.size() size_type Постоянная
obj.empty() Обратимый в bool Постоянная
obj1 < obj2 Обратимый в bool Линейная
obj1 > obj2 Обратимый в bool Линейная
obj1 <= obj2 Обратимый в bool Линейная
obj1 >= obj2 Обратимый в bool Линейная
obj.swap(obj2) void Постоянная

Итераторы

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

Категория Поддерживаемые операции Примечание
Входные operator++, operator*, operator->, конструктор копии, operator=, operator==, operator!= Обеспечивают доступ для чтения в одном направлении. Позволяют выполнить присваивание или копирование с помощью оператора присваиваивания и конструктора копии
Выходные operator++, operator*, конструктор копии Обеспечивают доступ для записи в одном направлении. Их нельзя сравнивать на равенство.
Однонаправленные operator++, operator*, operator->, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!= Обеспечивают доступ для чтения и записи в одном направлении. Позволяют выполнить присваивание или копирование с помощью оператора присваиваивания и конструктора копии. Их можно сравнивать на равенство.
Двунаправленные operator++, operator--, operator*, operator->, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!= Поддерживают все функции, описанные для однонаправленных итераторов (см. выше). Кроме того, они позволяют переходит к предыдущему элементу.
Произвольного доступа operator++, operator--, operator*, operator->, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!=, operator+, operator-, operator+=, operator-=, operator<, operator>, operator<=, operator>=, operator[] Эквивалентны обычным указателям: поддерживают арифметику указателей, синтаксис индексации массивов и все формы сравнения.

См. также

Ссылки


Wikimedia Foundation. 2010.

Полезное


Смотреть что такое "Standard Template Library" в других словарях:

  • Standard Template Library — (STL) type of library for compiling C++ programs that enables the user to employ generic container classes and generic algorithms (Computers) …   English contemporary dictionary

  • Standard Template Library — C++ Standard Library fstream iomanip ios iostream sstream string …   Wikipedia

  • Standard Template Library — Pour les articles homonymes, voir STL. La Standard Template Library (STL) est une bibliothèque C++, normalisée par l ISO (document ISO/CEI 14882) et mise en œuvre à l aide des templates. Cette bibliothèque fournit : un ensemble de classes… …   Wikipédia en Français

  • Standard Template Library — Als Standard Template Library (STL) werden verschiedene in der Programmiersprache C++ geschriebene Bibliotheken bezeichnet. Ursprünglich wurde mit Standard Template Library eine in den 1980er Jahren bei Hewlett Packard (kurz: HP) entwickelte, in… …   Deutsch Wikipedia

  • Active Template Library — The Active Template Library (ATL) is a set of template based C++ classes developed by Microsoft that simplify the programming of Component Object Model (COM) objects. The COM support in Microsoft Visual C++ allows developers to create a variety… …   Wikipedia

  • Active Template Library — Bei der Active Template Library (ATL) handelt es sich um eine Sammlung von Visual C++ Klassenbibliotheken für Microsoft Windows zur Erstellung und Nutzung von COM Komponenten, einschließlich ActiveX Steuerelementen. Der Namensbestandteil Template …   Deutsch Wikipedia

  • Active Template Library — Pour les articles homonymes, voir ATL. L Active Template Library (ATL) signifie en français bibliothèque de modèles actifs. L ATL est une bibliothèque de classes C++ développée par Microsoft qui simplifie la programmation des composants logiciels …   Wikipédia en Français

  • Windows Template Library — The Windows Template Library (WTL) is a free software, object oriented C++ template library for Win32 development. WTL was created by Microsoft employee Nenad Stefanovic for internal use and later released as an unsupported add on to Visual… …   Wikipedia

  • Windows Template Library — Тип библиотека (программирование) Разработчик Nenad Stefanovic Написана на С++ Операционная система Microsoft Windows Последняя версия WTL 8.1.11324 (21.11.2011) Лицензия …   Википедия

  • Material Template Library — MTL material format Extension .mtl Développé par Wavefront Technologies Type de format Format de texture 3D …   Wikipédia en Français


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»