Ассоциативные контейнеры (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 - значение X::value_type и k - значение X::key_type.

Таблица 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.

Множество (Set)

     set - это ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск ключей.

template <class Key, class Compare = less<Key>,
	template <class U> class Allocator = allocator> 
class set { 
public:

// typedefs:

	typedef Key key_type;
	typedef Key value_type;
	typedef Allocator<Key>::pointer pointer;
	typedef Allocator<Key>::reference reference;
	typedef Allocator<Key>::const_reference const_reference;
	typedef Compare key_compare;
	typedef Compare value_compare;
	typedef iterator;
	typedef iterator const_iterator;
	typedef size_type;
	typedef difference_type;
	typedef reverse_iterator;
	typedef const_reverse_iterator;

// allocation/deallocation:

	set(const Compare& comp = Compare());
	template <class InputIterator> 
	set(InputIterator first, InputIterator last,
		const Compare& comp = Compare());
	set(const set<Key, Compare, Allocator>& x);
	~set();
	set<Key, Compare, Allocator>& operator=(const set<Key, Compare,
		Allocator>& x);
	void swap(set<Key, Compare, Allocator>& x);

// accessors:

	key_compare key_comp() const;
	value_compare value_comp() const;
	iterator begin() const;
	iterator end() const;
	reverse_iterator rbegin() const;
	reverse_iterator rend() const;
	bool empty() const;
	size_type size() const;
	size_type max_size() const;

// insert/erase

	pair<iterator, bool> insert(const value_type& x);
	iterator insert(iterator position, const value_type& x);
	template <class InputIterator>
	void insert(InputIterator first, InputIterator last);
	void erase(iterator position);
	size_type erase(const key_type& x);
	void erase(iterator first, iterator last);

// set operations:

	iterator find(const key_type& x) const;
	size_type count(const key_type& x) const;
	iterator lower_bound(const key_type& x) const;
	iterator upper_bound(const key_type& x) const;
	pair<iterator, iterator> equal_range(const key_type& x) const;
};

template <class Key, class Compare, class Allocator> 
bool operator==(const set<Key, Compare, Allocator>& x,
	 const set<Key, Compare, Allocator>& y);

template <class Key, class Compare, class Allocator> 
bool operator<(const set<Key, Compare, Allocator>& x, 
	const set<Key, Compare, Allocator>& y);

     iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator.

     сonst_iterator - тот же самый тип, что и iterator.

     size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

     difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

Множество с дубликатами (Multiset)

     multiset - это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.

template <class Key, class Compare = less<Key>,
		template <class U> class Allocator = allocator>
class multiset { 
public:

// typedefs:

	typedef Key key_type;
	typedef Key value_type;
	typedef Allocator<Key>::pointer pointer;
	typedef Aliocator<Key>::reference reference;
	typedef Allocator<Key>::const_reference const_reference;
	typedef Compare key_compare;
	typedef Compare value_compare;
	typedef iterator;
	typedef iterator const_iterator;
	typedef size_type;
	typedef difference_type;
	typedef reverse_iterator;
	typedef const_reverse_iterator;

// allocation/deallocation:

	multiset(const Compare& comp = Compare());
	template <class InputIterator>
	multiset(InputIterator first, InputIterator last,
		const Compare& comp == Compare());
	multiset(const multiset<Key, Compare, Allocator>& x);
	~multiset();
	multiset<Key, Compare, Allocator>& operator=(const multiset<Key,
			Compare, Allocator>& x);
	void swap(multiset<Key, Compare, Allocator>& x);

// accessors:

	key_compare key_comp() const;
	value_compare value_comp() const;
	iterator begin() const;
	iterator end() const;
	reverse_iterator rbegin();
	revferse_iterator rend();
	bool empty() const;
	size_type size() const;
	size_type max_size() const;

// insert/erase:

	iterator insert(const value_type& x);
	iterator insert(iterator position, const value_type& x);
	template <class InputIterator>
	void insert(InputIterator first, InputIterator last);
	void erase(iterator position);
	size_type erase(const key_type& x);
	void erase(iterator first, iterator last);

// multiset operations:

	iterator find(const key_type& x) const;
	size_type count(const key_type& x) const;
	iterator lower_bound(const key_type& x) const;
	iterator upper_bound(const key_type& x) const;
	pair<iterator, iterator> equal_range(const key_type& x) const;
};

template <class Key, class Compare, class Allocator> 
bool operator==(const multiset<Key, Compare, Allocator>& x, 
		const multiset<Key, Compare, Allocator>& y);

template <class Key, class Compare, class Allocator>
bool operator<(const multiset<Key, Compare, Allocator>& x,
		const multiset<Key, Compare, Allocator>& y);

     iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator.

     сonst_iterator - тот же самый тип, что и iterator.

     size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

     difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

Словарь (Map)

     map - ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.

template <class Key, class T, class Compare = less<Key>,
		template <class U> class Allocator = allocator>
class map { 
public:

// typedefs:

	typedef Key key_type;
	typedef pair<const Key, T> value_type;
	typedef Compare key_compare;
	class value_compare
		: public binary_function<value_type, value_type, bool> {
	friend class map;
	protected:
		Compare comp;
		value_compare(Compare c) : comp(c) {} 
	public:
		bool operator()(const value_type& x, const value_type& y) {
			return comp(x.first, y.first);
		}
	};
	typedef iterator;
	typedef const_iterator;
	typedef Allocator<value_type>::pointer pointer;
	typedef Allocator<value_type>::reference reference;
	typedef Allocator<value_type>::const_reference const_reference;
	typedef size_type;
	typedef difference_type;
	typedef reverse_iterator;
	typedef const_reverse_iterator;

// allocation/deallocation:

	map(const Compare& comp = Compare());
	template <class InputIterator>
	map(InputIterator first, InputIterator last,
		const Compare& comp = Compare());
	map(const map<Key, T, Compare,  Allocator>& x);
	~map();
	map<Key, T, Compare, Allocator>&
		operator=(const map<Key, T, Compare, Allocator>& x);
	void swap(map<Key, T, Compare, Allocator>& x);

// accessors:

	key_compare key_comp() const;
	value_compare value_comp() const;
	iterator begin()
	const_iterator begin() const;
	iterator end();
	const_iterator end() const;
	reverse_iterator rbegin();
	const_reverse_iterator rbegin();
	reverse_iterator rend();
	const_reverse_iterator rend();
	bool empty() const;
	size_type size() const;
	size_type max_size() const;
	Allocator<T>::reference operator[](const key_type& x);

// insert/erase:

	pair<iterator, bool> insert(const value_type& x);
	iterator insert(iterator position, const value_type& x);
	template <class InputIterator>
	void insert(InputIterator first, InputIterator last);
	void erase(iterator position);
	size_type erase(const key_type& x);
	void erase(iterator first, iterator last);

// map operations:

	iterator find(const key_type& x);
	const_iterator find(const key_type& x) const;
	size_type count(const key_type& x) const;
	iterator lower_bound(const key_type& x);
	const_iterator lower_bound(const key_type& x) const;
	iterator upper_bound(const key_type& x);
	const_iterator upper_bound(const key_type& x) const;
	pair<iterator, iterator> equal_range(const key_type& x);
	pair<const_iterator, const_iterator> equal_range(const key_type& x)const;
};

template <class Key, class T, class Compare, class Allocator>
bool operator==(const map<Key, T, Compare, Allocator>& x, 
		const map<Key, T, Compare, Allocator>& y);

template <class Key, class T, class Compare, class Allocator>
bool operator<(const mapr<Key, T, Compare, Allocator>& x, 
		const map<Key, T, Compare, Allocator>& y);

     iterator - двунаправленный итератор, указывающий на value_type. Точный тип зависит от реализации и определяется в Allocator.

     const_iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

     size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

     difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

     В дополнение к стандартному набору методов ассоциативных контейнеров, map обеспечивает операцию Allocator::reference operator[](const key_type&). Для словаря m и ключа k запись m[k] семантически эквивалентна (*((m.insert(make_pair(k, T()))).first)).second.

Словарь с дубликатами (Multimар)

     multimар - ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.

template <class Key, class T, class Compare = less<Key>,
		template <class U> class Allocator = allocator>
class multimap { 
public:

// typedefs:

	typedef Key key_type;
	typedef pair<const Key, T> value_type;
	typedef Compare key_compare;
	class value_compare
		: public binary_function<value_type, value_type, bool> {
	friend class multimap;
	protected:
		Compare comp;
		value_compare(Compare c) : comp(c) {}
	public:
		bool operator()(const value_type& x, const value_type& y) {
			return comp(x.first, y.first);
		}
	};
	typedef iterator;
	typedef const_iterator;
	typedef Allocator<value_type>::pointer pointer;
	typedef Allocator<value_type>::reference reference;
	typedef Allocator<value_type>::const_reference const_reference;
	typedef size_type;
	typedef difference_type;
	typedef reverse_iterator;
	typedef const_reverse_iterator;

// allocation/deallocation:

	multimap(const Compare& comp = Compare());
	template <class InputIterator>
	multimap(InputIterator first, InputIterator last,
		const Compare& comp = Compare());
	multimap(const multimap<Key, T, Compare, Allocator>& x);
	~multimap();
	multimap<Key, T, Compare, Allocator>&
		operator=(const multimap<Key, T, Compare, Allocator>& x);
	void swap(multimap<Key, T, Compare, Allocator>& x);

// accessors:

	key_compare key_comp() const;
	value_compare value_comp() const;
	iterator begin();
	const_iterator begin() const;
	iterator end();
	const_iterator end() const;
	reverse_iterator rbegin();
	const_reverse_iterator rbegin();
	reverse_iterator rend()
	const_reverse_iterator rend();
	bool empty() const;
	size_type size() const;
	size_type max_size() const;

// insert/erase:

	iterator insert(const value_type& x);
	iterator insert(iterator position, const value_type& x);
	template <class InputIterator>
	void insert(InputIterator first, InputIterator	last);
	void erase(iterator position);
	size_type erase(const key_type& x);
	void erase(iterator first, iterator last);

// multimap operations:

	iterator find(const key_type& x);
	const_iterator find(const key_type& x) const;
	size_type count(const key_type& x) const;
	iterator lower_bound(const key_type& x);
	const_iterator lower_bound(const key_type& x) const;
	iterator upper_bound(const key_type& x);
	const_iterator upper_bound(const key_type& x) const;
	pair<iterator, iterator> equal_range(const key_type& x);
	pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
};

template <class Key, class T, class Compare, class Allocator>
bool operator==(const multimap<Key, T, Compare, Allocator>& x,
	 	const multimap<Key, T, Compare, Allocator>& y);

template <class Key, class T, class Compare, class Allocator>
bool operator<(const multimap<Key, T, Compare, Allocator>& x,
	 	const multimap<Key, T, Compare, Allocator>& y);

     iterator - двунаправленный итератор, указывающий на value_type. Точный тип зависит от реализации и определяется в Allocator.

     const_iterator - постоянный двунаправленный итератор, указывающий на value_type. Точный тип зависит от реализации и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

     size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

     difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.