Контейнеры - это объекты, в которых хранятся другие объекты. Они контролируют выделение и освобождение этих объектов с помощью конструкторов, деструкторов, операций вставки и стирания.
Все требования к сложности в этом разделе указаны исключительно в терминах количества операций с содержащимися объектами. [ Example: Конструктор копирования типа vector<vector<int>> имеет линейную сложность, хотя сложность копирования каждого содержащегося в нем элемента vector<int> является линейной. ] — end example
Для компонентов, затронутых этим подпунктом, которые объявляютallocator_type, объекты, хранящиеся в этих компонентах, должны быть построены с использованием функции allocator_traits<allocator_type>::rebind_traits<U>::construct и уничтожены с помощью функции allocator_traits<allocator_type>::rebind_traits<U>::destroy, гдеU либоallocator_type::value_type внутренний тип, либо внутренний тип, используемый контейнером. Эти функции вызываются только для типа элемента контейнера, а не для внутренних типов, используемых контейнером. [ Note: Это означает, например, что контейнер на основе узлов может нуждаться в создании узлов, содержащих выровненные буферы, и вызовеconstruct для помещения элемента в буфер. ] — end note
В таблицах83, 84и 85 X обозначает контейнерный класс, содержащий объекты типа T,a иb обозначают значения типаX,u обозначает идентификатор,r обозначает неконстантное значение типаXиrv обозначает неконстантное rvalue типаX.
Выражение | Тип возврата | Оперативный | Утверждение / примечание | Сложность |
семантика | до / после состояния | |||
X::value_type | T | Requires: T этоErasable отX (см[container.requirements.general], ниже) | время компиляции | |
X::reference | T& | время компиляции | ||
X::const_reference | const T& | время компиляции | ||
X::iterator | тип итератора, тип значения которогоT | любая категория итераторов, отвечающая требованиям прямого итератора. конвертируемый вX::const_iterator. | время компиляции | |
X::const_iterator | постоянный тип итератора, тип значения которогоT | любая категория итераторов, отвечающая требованиям прямого итератора. | время компиляции | |
X::difference_type | знаковый целочисленный тип | идентичен типу разницыX::iterator иX::const_iterator | время компиляции | |
X::size_type | беззнаковый целочисленный тип | size_type может представлять любое неотрицательное значениеdifference_type | время компиляции | |
X u; | Postconditions:u.empty() | постоянный | ||
X() | Postconditions:X().empty() | постоянный | ||
X(a) |
Requires:T находитсяCopyInsertable
вX (см. ниже). Postconditions:a == X(a). | линейный | ||
X u(a); X u = a; |
Requires:T находитсяCopyInsertable
вX (см. ниже). Postconditions:u == a | линейный | ||
X u(rv); X u = rv; | Postconditions:u будет равняться значению, котороеrv имело до этого строительства | (Примечание B) | ||
a = rv | X& | Все существующие элементыa либо перемещаются, либо уничтожаются. | a должно быть равно значению, котороеrv имело до этого присвоения | линейный |
(&a)->~X() | void | деструктор применяется к каждому элементуa; любая полученная память освобождается. | линейный | |
a.begin() | iterator;const_iterator для постоянногоa | постоянный | ||
a.end() | iterator;const_iterator для постоянногоa | постоянный | ||
a.cbegin() | const_iterator | const_cast<X const&>(a).begin(); | постоянный | |
a.cend() | const_iterator | const_cast<X const&>(a).end(); | постоянный | |
a == b | конвертируемый вbool | == является отношением эквивалентности. equal(a.begin(), a.end(), b.begin(), b.end()) | Requires: T являетсяEqualityComparable | Постоянно, еслиa.size() != b.size(), линейно в противном случае |
a != b | конвертируемый вbool | Эквивалентно!(a == b) | линейный | |
a.swap(b) | void | обменивается содержимымa иb | (Примечание А) | |
swap(a, b) | void | a.swap(b) | (Примечание А) | |
r = a | X& | Postconditions:r == a. | линейный | |
a.size() | size_type | distance(a.begin(), a.end()) | постоянный | |
a.max_size() | size_type | distance(begin(), end()) для максимально возможного контейнера | постоянный | |
a.empty() | конвертируемый вbool | a.begin() == a.end() | постоянный |
Записи, отмеченные «(Примечание A)» или «(Примечание B)», имеют линейную сложностьarray и постоянную сложность для всех других стандартных контейнеров. [ Note: Алгоритмequal() определен в п[algorithms]. ] — end note
Функция-членsize() возвращает количество элементов в контейнере. Количество элементов определяется правилами конструкторов, вставок и стираний.
begin() возвращает итератор, ссылающийся на первый элемент в контейнере. end() возвращает итератор, который является последним значением для контейнера. Если емкость пуста, то begin() == end().
В выражениях
i == j i != j i < j i <= j i >= j i > j i - j
гдеi иj обозначают объекты типа контейнераiterator , один или оба могут быть заменены объектом типа контейнера, const_iterator относящимся к тому же элементу без изменения семантики.
Если не указано иное, все контейнеры, определенные в этом пункте, получают память с помощью распределителя (см[allocator.requirements]. Раздел "Ресурсы" ). [ Note: В частности, контейнеры и итераторы не хранят ссылки на выделенные элементы, кроме как через тип указателя распределителя, то есть как объекты типаP или pointer_traits<P>::template rebind<unspecified>, гдеP естьallocator_traits<allocator_type>::pointer. ] Конструкторы копирования для этих типов контейнеров получают распределитель, вызывая распределитель, принадлежащий копируемому контейнеру. Конструкторы перемещения получают распределитель, перемещая конструкцию из распределителя, принадлежащего перемещаемому контейнеру. Такая конструкция перемещения распределителя не должна завершаться через исключение. Все остальные конструкторы для этих типов контейнеров принимают аргумент. [ Если при вызове конструктора используется значение по умолчанию необязательного аргумента распределителя, то тип должен поддерживать инициализацию значения. ] Копия этого распределителя используется для любого выделения памяти и построения элементов, выполняемых этими конструкторами и всеми функциями-членами, в течение жизненного цикла каждого объекта-контейнера или до тех пор, пока распределитель не будет заменен. Распределитель может быть заменен только через присвоение или . Замена распределителя выполняется путем присваивания копии, присваивания перемещения или замены распределителя только в том случае , если , или находится в рамках реализации соответствующей операции контейнера. Во всех типах контейнеров, определенных в этом разделе, член возвращает копию распределителя, использованного для создания контейнера, или, если этот распределитель был заменен, копию самой последней замены. — end note allocator_traits<allocator_type>::select_on_container_copy_constructionconst allocator_type& Note: Allocator — end note swap()allocator_traits<allocator_type>::propagate_on_container_copy_assignment::valueallocator_traits<allocator_type>::propagate_on_container_move_assignment::valueallocator_traits<allocator_type>::propagate_on_container_swap::value trueget_allocator()
Выражениеa.swap(b)для контейнеровa иb стандартного типа контейнера, отличного отarray, должно обмениваться значениямиa и b без вызова каких-либо операций перемещения, копирования или обмена для отдельных элементов контейнера. L-значения любогоCompare,PredилиHash типов, принадлежащихa иb должны быть взаимозаменяемыми и должны быть обменены путем вызова,swap как описано в[swappable.requirements]. Если allocator_traits<allocator_type>::propagate_on_container_swap::value есть true, то lvalues типаallocator_type должны быть заменены , а распределителиa иb также должны обмениваться посредством вызова,swap как описано в[swappable.requirements]. В противном случае распределители не должны меняться местами, и поведение не определено, если толькоa.get_allocator() == b.get_allocator(). Каждый итератор, ссылающийся на элемент в одном контейнере до обмена, должен ссылаться на тот же элемент в другом контейнере после обмена. Не указано, будет ли итератор со значениемa.end() до обмена иметь значениеb.end() после обмена.
Если тип итератора контейнера принадлежит к двунаправленному или произвольному доступуiterator categories, контейнер вызывается reversible и удовлетворяет дополнительным требованиям в таблице84.
Выражение | Тип возврата | Утверждение / примечание | Сложность |
до / после состояния | |||
X::reverse_iterator | тип итератора, тип значения которогоT | reverse_iterator<iterator> | время компиляции |
X::const_reverse_iterator | постоянный тип итератора, тип значения которогоT | reverse_iterator<const_iterator> | время компиляции |
a.rbegin() | reverse_iterator; const_reverse_iterator для постоянногоa | reverse_iterator(end()) | постоянный |
a.rend() | reverse_iterator; const_reverse_iterator для постоянногоa | reverse_iterator(begin()) | постоянный |
a.crbegin() | const_reverse_iterator | const_cast<X const&>(a).rbegin() | постоянный |
a.crend() | const_reverse_iterator | const_cast<X const&>(a).rend() | постоянный |
Если не указано иное (см[associative.reqmts.except],[unord.req.except],[deque.modifiers], и [vector.modifiers]) все типы контейнеров определено в настоящем пункте встречаются следующие дополнительные требования:
если исключение вызывается функциейinsert() илиemplace()при вставке одного элемента, эта функция не имеет никакого эффекта.
если исключение брошенное push_back(), push_front(), emplace_back()илиemplace_front() функция, что функция не имеет никакого эффекта.
нет erase(), clear(), pop_back() или pop_front() функция вызывает исключение.
ни один конструктор копирования или оператор присваивания возвращаемого итератора не вызывает исключение.
ни одна swap() функция не вызывает исключение.
никакая swap() функция не делает недействительными любые ссылки, указатели или итераторы, относящиеся к элементам заменяемых контейнеров. [ Итератора не относится к любому элементу, так что она может быть признана недействительной. ] Note: end() — end note
Если не указано иное (явно или путем определения функции в терминах других функций), вызов функции-члена контейнера или передача контейнера в качестве аргумента библиотечной функции не должны аннулировать итераторы или изменять значения объектов в этом контейнере. .
Acontiguous container - это контейнер, который поддерживаетrandom access iterators и чьи типы членовiterator иconst_iterator являютсяcontiguous iterators.
В таблице85 перечислены операции, которые предусмотрены для одних типов контейнеров, но не для других. Те контейнеры, для которых предусмотрены перечисленные операции, должны реализовывать семантику, описанную в таблице,85 если не указано иное.
Выражение | Тип возврата | Оперативный | Утверждение / примечание | Сложность |
семантика | до / после состояния | |||
a < b | конвертируемый вbool | lexicographical_compare( a.begin(), a.end(), b.begin(), b.end()) | Requires:< определяется для значенийT.< это отношения полного порядка. | линейный |
a > b | конвертируемый вbool | b < a | линейный | |
a <= b | конвертируемый вbool | !(a > b) | линейный | |
a >= b | конвертируемый вbool | !(a < b) | линейный |
[ Note: Алгоритмlexicographical_compare() определен в п[algorithms]. ] — end note
Все контейнеры, определенные в этом разделе и за[basic.string] исключением,array соответствуют дополнительным требованиям к контейнеру, поддерживающему распределитель, как описано в таблице86.
Для данного типа распределителяA и данного типа контейнера,X имеющегоvalue_type идентичныйT иallocator_type идентичный,allocator_traits<A>::rebind_alloc<T> и заданного lvaluem типаA, указателяp типаT*, выраженияv типа (возможноconst)Tи rvaluerv типаT, определены следующие термины. ЕслиX не известно о распределителе, приведенные ниже термины определены как если быA были allocator<T> - не нужно создавать объект распределителя иallocator<T> не создавать экземпляры пользовательских специализаций :
T этоDefaultInsertable into X означает , что следующее выражение хорошо сформировано:
allocator_traits<A>::construct(m, p)
ЭлементX is,default-inserted если он инициализируется вычислением выражения
allocator_traits<A>::construct(m, p)
гдеp - адрес неинициализированного хранилища для выделенного внутри элементаX.
T этоMoveInsertable into X означает , что следующее выражение хорошо сформировано:
allocator_traits<A>::construct(m, p, rv)
и его оценка вызывает выполнение следующего постусловия: значение*p эквивалентно значениюrv до оценки. [ Note:rv остается действующим объектом. Его состояние не указано ] — end note
T этоCopyInsertable into X означает , что, в дополнение кT бытьMoveInsertable в Xследующее выражение хорошо сформированы:
allocator_traits<A>::construct(m, p, v)
и его оценка вызывает выполнение следующего постусловия: значениеv не изменяется и эквивалентно*p.
T это EmplaceConstructible into X from args, ноль или более аргументовargs, означает , что следующее выражение хорошо сформированные:
allocator_traits<A>::construct(m, p, args)
T это Erasable from X означает , что следующее выражение хорошо сформировано:
allocator_traits<A>::destroy(m, p)
[ Note: Контейнер вызываетallocator_traits<A>::construct(m, p, args) создание элемента приp использованииargs, withm == get_allocator(). По умолчаниюconstruct inallocator будет вызывать::new((void*)p) T(args), но специализированные распределители могут выбрать другое определение. ] — end note
В таблице86,X обозначает распределитель-Aware класса контейнера сvalue_type изT помощью аллокатора типаA,u обозначает переменный, a иb обозначает неконстантную lvalues типаX, t обозначает именующее выражение или константный RValue типаX,rv обозначает неконстантную RValue типаX, иm является значением типаA.
Выражение | Тип возврата | Утверждение / примечание | Сложность |
до / после состояния | |||
allocator_type | A | Requires:allocator_type::value_type то же самое, что иX::value_type. | время компиляции |
get_-allocator() | A | постоянный | |
X() X u; |
Requires: A естьDefaultConstructible. Postconditions:u.empty() возвращаетсяtrue, u.get_allocator() == A() | постоянный | |
X(m) | Postconditions:u.empty() возвращаетсяtrue, | постоянный | |
X u(m); | u.get_allocator() == m | ||
X(t, m) X u(t, m); |
Requires: T находитсяCopyInsertable вX. Postconditions:u == t,u.get_allocator() == m | линейный | |
X(rv) X u(rv); | Postconditions:u должен иметь те же элементы, чтоrv и до этого строительства; значениеu.get_allocator() должно быть таким же, как значениеrv.get_allocator() до этого строительства. | постоянный | |
X(rv, m) X u(rv, m); |
Requires: T находится
MoveInsertable вX. Postconditions:u должны иметь те же элементы или копии элементов, которыеrv были до этого строительства,u.get_allocator() == m | постоянная, еслиm ==rv.get_allocator(), в противном случае линейная | |
a = t | X& |
Requires: T находится
CopyInsertable вX
иCopyAssignable. Postconditions:a == t | линейный |
a = rv | X& |
Requires: Если есть , это
в и
. Все существующие элементы
либо передаются, либо уничтожаются. будет равно значению, которое имело до этого присвоения. allocator_- traits<allocator_type> ::propagate_on_container_- move_assignment::value falseT MoveInsertable X MoveAssignablea Postconditions:a rv | линейный |
a.swap(b) | void | обменивается содержимымa иb | постоянный |
Поведение определенных функций-членов контейнера и руководств по выводам зависит от того, квалифицируются ли типы как итераторы ввода или распределители. Степень, в которой реализация определяет, что тип не может быть итератором ввода, не определена, за исключением того, что как минимум целочисленные типы не должны квалифицироваться как итераторы ввода. Аналогично, степень, в которой реализация определяет, что тип не может быть распределителем, не указана, за исключением того, что, как минимум, типA не должен считаться распределителем, если он не удовлетворяет обоим из следующих условий:
qualified-idA::value_type Является действительным , и обозначает тип ([temp.deduct]).
Выражениеdeclval<A&>().allocate(size_t{}) правильно сформировано, когда рассматривается как неоцененный операнд.