» Главная
eXcode.ru » Статьи » С / С++
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 14





Контейнеры библиотеки STL (продолжение)




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

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. время компиляции
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 вставляет 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;
pairator, 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 ,
	template  class Allocator = allocator> 
class set { 
public:

// typedefs:

	typedef Key key_type;
	typedef Key value_type;
	typedef Allocator::pointer pointer;
	typedef Allocator::reference reference;
	typedef Allocator::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  
	set(InputIterator first, InputIterator last,
		const Compare& comp = Compare());
	set(const set& x);
	~set();
	set& operator=(const set& x);
	void swap(set& 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 insert(const value_type& x);
	iterator insert(iterator position, const value_type& x);
	template 
	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 equal_range(const key_type& x) const;
};

template  
bool operator==(const set& x,
	 const set& y);

template  
bool operator<(const set& x, 
	const set& y);

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

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

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

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

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

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

template ,
		template  class Allocator = allocator>
class multiset { 
public:

// typedefs:

	typedef Key key_type;
	typedef Key value_type;
	typedef Allocator::pointer pointer;
	typedef Aliocator::reference reference;
	typedef Allocator::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 
	multiset(InputIterator first, InputIterator last,
		const Compare& comp == Compare());
	multiset(const multiset& x);
	~multiset();
	multiset& operator=(const multiset& x);
	void swap(multiset& 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 
	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 equal_range(const key_type& x) const;
};

template  
bool operator==(const multiset& x, 
		const multiset& y);

template 
bool operator<(const multiset& x,
		const multiset& y);

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

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

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

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

Словарь (Map)

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

template ,
		template  class Allocator = allocator>
class map { 
public:

// typedefs:

	typedef Key key_type;
	typedef pair value_type;
	typedef Compare key_compare;
	class value_compare
		: public binary_function {
	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::pointer pointer;
	typedef Allocator::reference reference;
	typedef Allocator::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 
	map(InputIterator first, InputIterator last,
		const Compare& comp = Compare());
	map(const map& x);
	~map();
	map&
		operator=(const map& x);
	void swap(map& 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::reference operator[](const key_type& x);

// insert/erase:

	pair insert(const value_type& x);
	iterator insert(iterator position, const value_type& x);
	template 
	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 equal_range(const key_type& x);
	pair equal_range(const key_type& x)const;
};

template 
bool operator==(const map& x, 
		const map& y);

template 
bool operator<(const mapr& x, 
		const map& 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 ,
		template  class Allocator = allocator>
class multimap { 
public:

// typedefs:

	typedef Key key_type;
	typedef pair value_type;
	typedef Compare key_compare;
	class value_compare
		: public binary_function {
	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::pointer pointer;
	typedef Allocator::reference reference;
	typedef Allocator::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 
	multimap(InputIterator first, InputIterator last,
		const Compare& comp = Compare());
	multimap(const multimap& x);
	~multimap();
	multimap&
		operator=(const multimap& x);
	void swap(multimap& 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 
	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 equal_range(const key_type& x);
	pair equal_range(const key_type& x) const;
};

template 
bool operator==(const multimap& x,
	 	const multimap& y);

template 
bool operator<(const multimap& x,
	 	const multimap& y);

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

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

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

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

К началу статьи





Добавил: LedWormДата публикации: 2006-03-14 10:12:58
Рейтинг статьи:3.33 [Голосов 6]Кол-во просмотров: 11351

Комментарии читателей

Всего комментариев: 0
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Каким ICQ-клиентом вы пользуетесь?
Стандартным ICQ - клиентом.
11% (23)
Miranda 'ой
13% (29)
крысой - &RQ
5% (10)
Своим собственным :)
4% (8)
Не пользуюсь, так как сижу на модеме :(
1% (3)
Не пользуюсь, мне и так хорошо ...
6% (13)
Qip'ом
56% (121)
Другим
4% (8)

Проголосовало: 215
Молодая программистка с маленькими скриптами ищет солидного провайдера, способного поддержать ее сайт. Вульгарный хостинг не предлагать.
Рейтинг: 6/10 (3)
Посмотреть все анекдоты