КонтейнерыстандартнойбиблиотекиSTL.
Стандартная библиотека шаблонов (STL) (англ. StandardTemplateLibrary) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.
В библиотеке выделяют пять основных компонентов:
Контейнер (англ. container) — хранение набора объектов в памяти.
Итератор (англ. iterator) — обеспечение средств доступа к содержимому контейнера.
Алгоритм (англ. algorithm) — определение вычислительной процедуры.
Адаптер (англ. adaptor) — адаптация компонентов для обеспечения различного интерфейса.
Функциональный объект (англ. functor) — сокрытие функции в объекте для использования другими компонентами.
Последовательные контейнеры
vector C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за. Добавление-удаление элемента в конец vector занимает амортизированное время, та же операция в начале или середине vector —. Стандартная быстрая сортировка за. Поиск элемента перебором занимает. Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.
list Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из-за большего времени доступа к элементу. Доступ по индексу за. В любом месте контейнера вставка и удаление производятся очень быстро — за.
|
|
|
deque Дэк. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за. Реализован в виде двусвязанного списка линейных массивов. С другой стороны, в отличие от vector, дек не гарантирует расположение всех своих элементов в непрерывном участке памяти, что делает невозможным безопасное использование арифметики указателей для доступа к элементам контейнера.
Ассоциативные контейнеры
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.
|
|
|
В контейнерах для хранения элементов используется семантика передачи объектов по значению. Другими словами, при добавлении контейнер получает копию элемента. Если создание копии нежелательно, то используют контейнер указателей на элементы. Присвоение элементов реализуется с помощью оператора присваивания, а их разрушение происходит с использованием деструктора.
Дата добавления: 2015-12-21; просмотров: 18; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!