Ассоциативные контейнеры (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
Словарь с дубликатами (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.