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

выражение	возвращаемый тип	утверждение/примечание состояние до/после	сложность
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)).	логарифмическая