Контейнеры
Контейнеры
Контейнеры - это объекты, которые содержат другие объекты. Они управляют размещением в памяти и свобождением этих объектов через конструкторы, деструкторы, операции вставки и удаления.
В следующей таблице мы полагаем, что X - контейнерный класс, содержащий объекты типа T, a и b - значения X, u - идентификатор, r - значение X&.
Таблица 8. Требования контейнеров
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после сложность X::value_type Т - - время компиляции X::reference - - - время компиляции X::const_reference - - - время компиляции X::pointer тип указателя, указывающий на X::reference - указатель на T в модели памяти, используемой контейнером время компиляции X::iterator тип итератора, указывающий на X::reference - итератор любой категории, кроме итератора вывода. время компиляции X::const_iterator тип итератора, указывающий на 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()) == - это отношение эквивалентности. примечание: equal определяется в разделе алгоритмов. линейная 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 ‹= b обратимый в 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‹iterator, value_type, reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹iterator, value_type, reference, difference_type› для двунаправленного итератора время компиляции X::const_reverse_iterator - reverse_iterator‹const_iterator, value_type, const_reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹const_iterator, value_type, const_reference, difference_type› для двунаправленного итератора. время компиляции a.rbegin() reverse_iterator; const_reverse_iterator для постоянного a reverse_iterator(end()) постоянная a.rend() reverse_iterator; const_reverse_iterator для постоянного a reverse_iterator(begin()) постоянная