Контейнеры
Как уже было отмечено, под контейнером понимают объект, содержащий другие (однотипные) объекты, называемые элементами контейнера. Стандартная библиотека С++ предоставляет типичные контейнеры, такие как: список, вектор, очередь, карта, множество и др.Доступ к элементам контейнера осуществляется через итераторы.
К контейнерам выдвигается ряд общих требований. Это осуществляется для того, чтобы использование контейнеров было одинаковым, независимо от его реализации. Соответственно, часто контейнеры бывают взаимозаменяемы.
Требования контейнеров
X::value_type
Т
X::reference
T&
X::const_refe rence
const T&
X::pointer
тип указателя, указывающий на X::reference
указатель на T в модели памяти, используемой контейнером
X::iterator
тип итратора, указывающий на X::reference
итератор любой категории, кроме итератора вывода.
X::const_iter ator
тип итератора, указывающий на X:: const_reference
постоянный итератор любой категории, кроме итератора вывода.
X::difference _type
знаковый целочисленный тип
идентичен типу расстояния X::iterator и X::const_iterator
X::size_type
беззнаковый целочисленный тип
size_type может представлять любое неотрицательное значение difference_type
X u;
конструктор по умолчанию. после: u.size() == 0.
X()
конструктор по умолчанию. X().size() == 0.
X(a)
конструктор копирования. a == X(a).
X u(a); X u = a;
конструктор копирования. после: u = a.
(&a)->~X()
результат не используется
после: a.size() == 0. примечание: деструктор применяется к каждому элементу a, и вся память возвращается.
a.begin()
iterator; const_iterator для постоянного a
итератор, указывающий на первый элемент
a.end()
iterator; const_iterator для постоянного a
итератор, указывающий на конец контейнера
a == b
обратимый в bool
== - это отношение эквивалентности. примечание: equal определяется в разделе алгоритмов.
a != b
обратимый в bool
r = a
X&
после: r == a.
a.size()
size_type
количество элементов в контейнере
a.max_size()
size_type
size() самого большого возможного контейнера.
a.empty()
обратимый в bool
a < b
обратимый в bool
до: < определён для значений T. < - отношение полного упорядочения. lexicographical _compare определяется в разделе алгоритмов.
a > b
обратимый в bool
a <= b
обратимый в bool
a >= b
обратимый в bool
a.swap(b)
void
Последовательные контейнеры
Последовательные контейнеры хранят свои элементы в строго линейном порядке. К последовательным контейнерам относятся хорошо известные структуры данных вектор (vector), список (list), очередь (deque), а также строка символов (string). Существуют также некоторые последовательные контейнеры, которые могут отсутствовать в стандартной библиотеке С++: стек (stack) и массив (array).
В таблице 7 указаны требования к последовательным контейнерам (обязательные операции).
Таблица 7 Требования последовательностей (в дополнение к контейнерам)
X(n, t) X a(n, t);
после: size() == n. создаёт последовательность с n копиями t.
X(i, j) X a(i, j);
после: size() == расстоянию между i и j. создаёт последовательность, равную диапазону [i, j).
a.insert(p, t)
iterator
вставляет копию t перед p. возвращаемое значение указывает на вставленную копию.
a.insert(p, n, t)
результат не используется
вставляет n копий t перед p.
a.insert(p, i, j)
результат не используется
вставляет копии элементов из диапазона [i, j) перед p.
a.erase(q)
результат не используется
удаляет элемент, указываемый q.
a.erase(ql, q2)
результат не используется
удаляет элементы в диапазоне [ql, q2).
В таблице 8 указаны операции, которые выражаются через обязательные операции контейнеров. В различных типах контейнеров эти опреации могут отсутствовать, например, у контейнера типа вектор нет возможности вставлять элементы в начало контейнера.
Таблица 8 Необязательные операции последовательностей
a.front()
reference; const_reference для постоянного a
*a.begin()
vector, list, deque
a.back()
reference; const_reference для постоянного a
*(--a. end())
vector, list, deque
a.push_front(t)
void
a.insert(a.begin(), t)
list, deque
a.push_back(t)
void
a.insert(a.end(), t)
vector, list, deque
a.pop_front ()
void
a.erase(a.begin())
list, deque
a.pop_back ()
void
a.erase(-- a.end())
vector, list, deque
a[n]
reference; const_reference для постоянного a
*(a.begin() + n)
vector, deque
Каждый последовательный контейнер имеет свои преимущества и недостатки, поэтому выбор того или иного контейнера для использования должен диктоваться задачей. Например, список обладает быстрым способом вставки новых элементов в любую позицию (за константное время), а у архитектура вектора определяет быстрый доступ к элементам (за константное время).
Ассоциативные контейнеры
Таблица 9 Требования ассоциативных контейнеров (в дополнение к контейнерам)
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); использует с как объект сравнения.
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 - подсказка, указывающая, где вставка должна начать поиск.
a.insert(i, j)
результат не используется
вставляет в контейнер элементы из диапазона [i, j);
a.erase(k)
size_type
стирает все элементы в контейнере с ключом, равным k. возвращает число уничтоженных элементов.
a.erase(q)
результат не используется
стирает элемент, указанный q.
a.erase(ql, q2)
результат не используется
стирает все элементы в диапазоне [ql, q2).
a.find(k)
iterator; const_iterator для константы a
возвращает итератор, указывающий на элемент с ключом, равным k, или a.end(), если такой элемент не найден.
a.count(k)
size_type
возвращает число элементов с ключом, равным 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)).
Last updated