Руководство по стандартной библиотеке шаблонов STL


Ассоциативные контейнеры (Associative containers) - часть 2



Таблица 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_iter
ator, const_iterator> для константы a
эквивалент make_pair(lower_boud(k), upper_bound (k)). логарифмическая

     Основным свойством итераторов ассоциативных контейнеров является то, что они выполняют итерации через контейнеры в порядке неубывания ключей, где неубывание определено сравнением, которое использовалось для их создания. Для любых двух разыменованных итераторов i и j таких, что расстояние от i до j является положительным, value_comp (*j, *i) == false. Для ассоциативных контейнеров с уникальными ключами выдерживается более сильное условие value_comp (*i, *j) == true.




Начало  Назад  Вперед



Книжный магазин