Руководство по стандартной библиотеке шаблонов STL

         

Контейнеры


Контейнеры - это объекты, которые содержат другие объекты. Они управляют размещением в памяти и свобождением этих объектов через конструкторы, деструкторы, операции вставки и удаления.



    В следующей таблице мы полагаем, что X - контейнерный класс, содержащий объекты типа T, a и b - значения X, u - идентификатор, r - значение X&.

Таблица 8. Требования контейнеров
выражение возвращаемый тип семантика исполнения утверждение/примечание
состояние до/после
сложность
X::value_type Т . . время компиляции
X::reference . . . время компиляции
X::const_refe
rence
. . . время компиляции
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;
. X u; 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 a.size() ==
b.size() &&
equal(a.begin(),
a.end(),
b.begin())
== - это отношение эквивалентности.
примечание: eqial определяется в разделе алгоритмов.
линейная
a != b обратимый в bool !(a == b) . линейная
r = a X& if(&r != &a) {
 (&r)-> X::~X();
 new (&r) X(a);
 return r; }
после: r == a. линейнaя
a.size() size_type size_type n = 0;
distance
(a.begin(),
a.end(), n);
return n;
. постоянная
a.max_size() size_type . size() самого большого возможного контейнера. постоянная
a.empty() обратимый в bool a.size() == 0 . постоянная
a < b обратимый в bool lexicographical
_compare
(a.begin(), a.end(),
b.begin(), b.end())
до: определён для значений T.
- отношение полного упорядочения.
lexicographical
_compare определяется в разделе алгоритмов.
линейная
a > b обратимый в bool b < a . линейнaя
a обратимый в bool !(a > b) . линейная
a >= b обратимый в bool !(a < b) . линейная
a.swap(b) void swap(a, b) . постоянная

    Функция-член size() возвращает число элементов в контейнере. Её семантика определяется правилами конструкторов, вставок и удалений.

    begin() возвращает итератор, ссылающийся на первый элемент в контейнере. end() возвращает итератор, который является законечным.

    Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым) и удовлетворяет следующим дополнительным требованиям:

Таблица 9. Требования обратимых контейнеров (в дополнение к контейнерам)
выражение возвращаемый тип семантика исполнения сложность
X::reverse
_iterator
. reverse_iterator
для итератора произвольного доступа.
reverse_bidirectional_iteratoriterator, value_type, reference, difference_type>
для двунаправленного итератора
время компиляции
X::const_r
everse_ite
rator
. reverse_iterator
для итератора произвольного доступа.
reverse_bidirectional_iteratorconst_iterator, value_type, const_reference, difference_type>
для двунаправленного итератора.
время компиляции
a.rbegin() reverse_iterator;
const_reverse_iter
ator для постоянного a
reverse_iterator(end()) постоянная
a.rend() reverse_iterator;
const_reverse_iter
ator для постоянного a
reverse_iterator(begin()) постоянная


Содержание раздела