РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
Шрифт:
iterator - итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.
const_iterator - постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.
size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
difference_type - знаковый целочисленный тип. Точный зависит от исполнения и определяется в Allocator.
insert (вставка) в середину двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. insert и push (помещение) с обоих концов двусторонней очереди делают недействительными все итераторы двусторонней очереди, но не влияют на действительность всех ссылок на двустороннюю очередь. В худшем случае вставка единственного элемента в двустороннюю очередь занимает линейное время от минимума двух расстояний: от точки вставки - до начала и до конца двусторонней очереди. Вставка единственного элемента либо в начало, либо в конец двусторонней очереди всегда занимает постоянное время и вызывает единственный запрос конструктора копии T. То есть двусторонняя очередь особенно оптимизирована для помещения и извлечения элементов в начале и в конце.
erase (стирание) в середине двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. erase и pop (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.
Ассоциативные контейнеры (Associative containers)
Ассоциативные контейнеры обеспечивают быстрый поиск данных, основанных на ключах. Библиотека предоставляет четыре основных вида ассоциативных контейнеров: set (множество), multiset (множество с дубликатами), map (словарь) и multimap (словарь с дубликатами).
Все они берут в качестве параметров Key (ключ) и упорядочивающее отношение Compare, которое вызывает полное упорядочение по элементам Key. Кроме того, map и multimap ассоциируют произвольный тип T с Key. Объект типа Compare называется сравнивающим объектом (comparison object) контейнера.
В этом разделе, когда мы говорим о равенстве ключей, мы подразумеваем отношение эквивалентности, обусловленное сравнением и не (not) operator== для ключей. То есть считается, что два ключа k1 и k2 являются равными, если для сравнивающего объекта comp истинно comp(k1, k2)==false && comp(k2, k1)==false.
Ассоциативный контейнер поддерживает уникальные ключи (unique keys), если он может содержать, самое большее, один элемент для каждого значения ключа. Иначе он поддерживает равные ключи (equal keys). set и map поддерживают уникальные ключи. multiset и multimap поддерживают равные ключи.
Для set и multiset значимый тип - тот же самый, что и тип ключа. Для map и multimap он равен pair‹const Key, T›.
iterator ассоциативного контейнера относится к категории двунаправленного итератора. insert не влияет на действительность итераторов и ссылок контейнера, а erase делает недействительными только итераторы и ссылки на стёртые элементы.
В следующей таблице обозначается: X - класс ассоциативного контейнера, a - значение X, a_uniq - значение X, когда X поддерживает уникальные ключи, a a_eq - значение X, когда X поддерживает многократные ключи, i и j удовлетворяют требованиям итераторов ввода и указывают на элементы value_type, [i, j) - допустимый диапазон, p - допустимый итератор для a, q - разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t -
Таблица 12. Требования ассоциативных контейнеров (в дополнение к контейнерам)
| выражение | возвращаемый тип | утверждение/примечание состояние до/после | сложность |
|---|---|---|---|
| X::key_type | Key | – | время компиляции |
| X::key_compare | Compare | по умолчанию less‹key_type›. | время компиляции |
| X::value_compare | тип бинарного предиката | то же, что key_compare для set и multiset; отношение упорядочения пар, вызванное первым компонентом (т.е. Key), для map и multimap. | время компиляции |
| X(c); X a(c); | – | создает пустой контейнер; использует с как объект сравнения. | постоянная |
| X; X a; | – | создает пустой контейнер; использует Compare как объект сравнения. | постоянная |
| X(i,j,c); X a(i,j,c); | – | cоздает пустой контейнер и вставляет в него элементы из диапазона [i, j); использует с как объект сравнения. | вообще NlogN (N - расстояние от i до j); линейная, если [i, j) отсортирован value_comp |
| X(i,j); X a(i,j); | – | то же, что выше, но использует Compare как объект сравнения. | то же, что выше |
| a.key_comp | X::key_compare | возвращает объект сравнения, из которого а был создан. | постоянная |
| a.value_comp | X::value_compare | возвращает объект value_compare, созданный из объекта сравнения. | постоянная |
| a_uniq.insert(t) | pair‹iterator, bool› | вставляет t, если и только если в контейнере нет элемента с ключом, равным ключу t. Компонент bool возвращенной пары показывает, происходит ли вставка, а компонент пары iterator указывает на элемент с ключом, равным ключу t. | логарифмическая |
| a_eq.insert(t) | iterator | вставляет t и возвращает итератор, указывающий на вновь вставленный элемент. | логарифмическая |
| a.insert(p, t) | iterator | вставляет t, если и только если в контейнерах с уникальными ключами нет элемента с ключом, равным ключу t; всегда вставляет t в контейнеры с дубликатами. всегда возвращает итератор, указывающий на элемент с ключом, равным ключу t. итератор p - подсказка, указывающая, где вставка должна начать поиск. | вообще логарифмическая, но сводится к постоянной, если t вставлен прямо перед p. |
| a.insert(i, j) | результат не используется | вставляет в контейнер элементы из диапазона [i, j); | вообще Nlog(size+N) (N - расстояние от i до j); линейная, если [i, j) отсортирован согласно value_comp |
| a.erase(k) | size_type | стирает все элементы в контейнере с ключом, равным k. возвращает число уничтоженных элементов. | log(size) + count(k) |
| a.erase(q) | результат не используется | стирает элемент, указанный q. | сводится к постоянной |
| a.erase(ql, q2) | результат не используется | стирает все элементы в диапазоне [ql, q2). | log(size)+ N, где N - расстояние от ql до q2. |
| a.find(k) | iterator; const_iterator для константы a | возвращает итератор, указывающий на элемент с ключом, равным k, или a.end, если такой элемент не найден. | логарифмическая |
| a.count(k) | size_type | возвращает число элементов с ключом, равным k. | log(size) + count(k) |
| a.lower_bound(k) | iterator; const_iterator для константы a | возвращает итератор, указывающий на первый элемент с ключом не меньше, чем k. | логарифмическая |
| a.upper_bound(k) | iterator; const_iterator для константы a | возвращает итератор, указывающий на первый элемент с ключом больше, чем k. | логарифмическая |
| a.equal_range(k) | pair‹iterator, itеrator›; pair‹const_iterator, const_iterator› для константы a | эквивалент make_pair(lower_bound(k), upper_bound(k)). | логарифмическая |