Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11642
Последний выпуск: 19.06.2015

Ассоциативные контейнеры (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.

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог