26 Containers library [containers]

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

Все требования к сложности в этом разделе указаны исключительно в терминах количества операций с содержащимися объектами. [  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.

Записи, отмеченные «(Примечание 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​::​value allocator_­traits<allocator_­type>​::​propagate_­on_­container_­swap​::​value true get_­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.

Если не указано иное (см [associative.reqmts.except], [unord.req.except], [deque.modifiers], и [vector.modifiers]) все типы контейнеров определено в настоящем пункте встречаются следующие дополнительные требования:

• (11.1)

  если исключение вызывается функциейinsert() или emplace()при вставке одного элемента, эта функция не имеет никакого эффекта.

• (11.2)

  если исключение брошенное push_­back(), push_­front(), emplace_­back()или emplace_­front() функция, что функция не имеет никакого эффекта.

• (11.3)

  нет erase(), clear(), pop_­back() или pop_­front() функция вызывает исключение.

• (11.4)

  ни один конструктор копирования или оператор присваивания возвращаемого итератора не вызывает исключение.

• (11.5)

  ни одна swap() функция не вызывает исключение.

• (11.6)

  никакая swap() функция не делает недействительными любые ссылки, указатели или итераторы, относящиеся к элементам заменяемых контейнеров. [ Итератора не относится к любому элементу, так что она может быть признана недействительной. ]  Note: end()  — end note 

Если не указано иное (явно или путем определения функции в терминах других функций), вызов функции-члена контейнера или передача контейнера в качестве аргумента библиотечной функции не должны аннулировать итераторы или изменять значения объектов в этом контейнере. .

A contiguous container - это контейнер, который поддерживает random access iterators и чьи типы членов iterator и const_­iterator являются contiguous iterators.

В таблице 85 перечислены операции, которые предусмотрены для одних типов контейнеров, но не для других. Те контейнеры, для которых предусмотрены перечисленные операции, должны реализовывать семантику, описанную в таблице, 85 если не указано иное.

[  Note: Алгоритм lexicographical_­compare() определен в п [algorithms]. ] — end note 

Все контейнеры, определенные в этом разделе и за [basic.string] исключением, array соответствуют дополнительным требованиям к контейнеру, поддерживающему распределитель, как описано в таблице 86.

Для данного типа распределителя A и данного типа контейнера, X имеющего value_­type идентичный T и allocator_­type идентичный, allocator_­traits<A>​::​rebind_­alloc<T> и заданного lvalue m типа A, указателя p типа T*, выражения v типа (возможно const) Tи rvalue rv типа T, определены следующие термины. Если X не известно о распределителе, приведенные ниже термины определены как если бы A были allocator<T> - не нужно создавать объект распределителя и allocator<T> не создавать экземпляры пользовательских специализаций :

• (15.1)

  T это DefaultInsertable into X означает , что следующее выражение хорошо сформировано:

  allocator_traits<A>::construct(m, p)

• (15.2)

  Элемент X is, default-inserted если он инициализируется вычислением выражения

  allocator_traits<A>::construct(m, p)

  где p - адрес неинициализированного хранилища для выделенного внутри элемента X.

• (15.3)

  T это MoveInsertable into X означает , что следующее выражение хорошо сформировано:

  allocator_traits<A>::construct(m, p, rv)

  и его оценка вызывает выполнение следующего постусловия: значение *p эквивалентно значению rv до оценки. [  Note: rv остается действующим объектом. Его состояние не указано ]  — end note 

• (15.4)

  T это CopyInsertable into X означает , что, в дополнение к T быть MoveInsertable в Xследующее выражение хорошо сформированы:

  allocator_traits<A>::construct(m, p, v)

  и его оценка вызывает выполнение следующего постусловия: значение v не изменяется и эквивалентно *p.

• (15.5)

  T это EmplaceConstructible into X from args, ноль или более аргументов args, означает , что следующее выражение хорошо сформированные:

  allocator_traits<A>::construct(m, p, args)

• (15.6)

  T это Erasable from X означает , что следующее выражение хорошо сформировано:

  allocator_traits<A>::destroy(m, p)

[  Note: Контейнер вызывает allocator_­traits<A>​::​construct(m, p, args) создание элемента при p использовании args, with m == get_­allocator(). По умолчанию construct in allocator будет вызывать ​::​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.

Поведение определенных функций-членов контейнера и руководств по выводам зависит от того, квалифицируются ли типы как итераторы ввода или распределители. Степень, в которой реализация определяет, что тип не может быть итератором ввода, не определена, за исключением того, что как минимум целочисленные типы не должны квалифицироваться как итераторы ввода. Аналогично, степень, в которой реализация определяет, что тип не может быть распределителем, не указана, за исключением того, что, как минимум, тип A не должен считаться распределителем, если он не удовлетворяет обоим из следующих условий:

• (17.1)

  qualified-id A​::​value_­type Является действительным , и обозначает тип ([temp.deduct]).

• (17.2)

  Выражение declval<A&>().allocate(size_­t{}) правильно сформировано, когда рассматривается как неоцененный операнд.

Для целей avoiding data races, реализации должны учитывать следующие функции будут const: begin, end, rbegin, rend, front, back, data, find, lower_­bound, upper_­bound, equal_­range, at и, кроме ассоциативных или неупорядоченных ассоциативных контейнеров operator[].

Тем не менее [res.on.data.races], реализации требуются, чтобы избежать гонки за данными, когда содержимое содержащегося объекта в разных элементах в одном и том же контейнере, за исключением vector<bool>, изменяется одновременно.

[  Note: Для a vector<int> x с размером больше единицы x[1] = 5 и *x.begin() = 10 может выполняться одновременно без гонки данных, но x[0] = 5 и *x.begin() = 10 выполняться одновременно может привести к гонке данных. В качестве исключения из общего правила, для vector<bool> y, y[0] = true может мчаться с y[1] = true. ] — end note 

Контейнер последовательности организует конечный набор объектов одного типа в строго линейную структуру. Библиотека обеспечивает четыре основных видов контейнеров последовательности: vector, forward_­list, list, и deque. Кроме того, array предоставляется как контейнер последовательности, который обеспечивает ограниченные операции последовательности, поскольку он имеет фиксированное количество элементов. Библиотека также предоставляет адаптеры контейнеров, которые упрощают создание абстрактных типов данных, таких как stacks или queues, из основных типов контейнеров последовательностей (или из других типов контейнеров последовательностей, которые может определить пользователь).

Контейнеры последовательностей предлагают программисту различные компромиссы сложности и должны использоваться соответственно. vector или array - это тип контейнера последовательности, который следует использовать по умолчанию. list или forward_­list должен использоваться, когда есть частые вставки и удаления из середины последовательности. deque - это предпочтительная структура данных, когда большинство вставок и удалений происходит в начале или в конце последовательности.

В таблицах 87 и 88, X обозначает класс контейнера последовательности, a обозначает значение типа , X содержащего элементы типа T, u обозначает имя переменной объявляется, A означает , X​::​allocator_­type если qualified-id X​::​allocator_­type является действительным , и обозначает тип ([temp.deduct]) , а allocator<T> не тогда , когда это произойдет, i и j обозначают итераторы удовлетворение требований входного итератора и ссылка на элементы, неявно конвертируемые в value_­type, [i, j) обозначает допустимый диапазон, il обозначает объект типа initializer_­list<value_­type>, n обозначает значение типа X​::​size_­type, p обозначает допустимый итератор константы для a, q обозначает допустимый разыменовываемый итератор константы a, [q1, q2) обозначает допустимый диапазон констант итераторы в a, t обозначает lvalue или const rvalue для X​::​value_­typeи rv обозначает неконстантное rvalue для X​::​value_­type. Args обозначает пакет параметров шаблона; args обозначает пакет параметров функции с шаблоном Args&&.

Сложность выражений зависит от последовательности.

Итератор вернулся из a.insert(p, t) точек в копию, t вставленную в a.

Итератор вернулся из a.insert(p, rv) точек в копию, rv вставленную в a.

Итератор вернулся из a.insert(p, n, t) точек в копию первого вставленного элемента a, или p if n == 0.

Итератор вернулся из a.insert(p, i, j) точек в копию первого вставленного элемента a, или p if i == j.

Итератор вернулся из a.insert(p, il) точек в копию первого вставленного элемента aили p если il он пуст.

Итератор вернулся из a.emplace(p, args) точек в новый элемент, созданный из args в a.

Итератор вернулся из a.erase(q) точек в элемент, следующий непосредственно за q стираемым элементом. Если такого элемента не существует, a.end() возвращается.

Итератор, возвращаемый a.erase(q1, q2) точкой, указывает элемент, на который указывает q2 до того, как какие-либо элементы будут удалены. Если такого элемента не существует, a.end() возвращается.

Для каждого контейнера последовательности, определенного в этом Пункте и Пункте [strings]:

• (13.1)

  Если конструктор

  template <class InputIterator>
    X(InputIterator first, InputIterator last,
      const allocator_type& alloc = allocator_type());

  вызывается с типом InputIterator , который не квалифицируется как итератор ввода, то конструктор не должен участвовать в разрешении перегрузки.

• (13.2)

  Если функции-члены форм:

  template <class InputIterator>
    return-type F(const_iterator p,
                  InputIterator first, InputIterator last);       // such as insert
  
  template <class InputIterator>
    return-type F(InputIterator first, InputIterator last);       // such as append, assign
  
  template <class InputIterator>
    return-type F(const_iterator i1, const_iterator i2,
                  InputIterator first, InputIterator last);       // such as replace
  

  вызываются с типом InputIterator , который не квалифицируется как итератор ввода, то эти функции не должны участвовать в разрешении перегрузки.

• (13.3)

  Руководство по дедукции для контейнера последовательности не должно участвовать в разрешении перегрузки, если у него есть InputIterator параметр шаблона и для этого параметра выводится тип, который не квалифицируется как итератор ввода, или если у него есть Allocator параметр шаблона и тип, который не соответствует требованиям. как распределитель для этого параметра.

В таблице 88 перечислены операции, которые предусмотрены для одних типов контейнеров последовательностей, но не для других. Реализация должна обеспечивать эти операции для всех типов контейнеров, показанных в столбце «контейнер», и должна реализовывать их так, чтобы использовать амортизированное постоянное время.

Функция-член at() обеспечивает доступ к элементам контейнера с проверкой границ. at() кидает out_­of_­range если n >= a.size().

Ассоциативные контейнеры с уникальными ключами и неупорядоченные контейнеры с уникальными ключами имеют функцию-член, insert которая возвращает вложенный тип insert_­return_­type. Этот возвращаемый тип является специализацией типа, указанного в этом подпункте.

template <class Iterator, class NodeType>
struct INSERT_RETURN_TYPE
{
  Iterator position;
  bool     inserted;
  NodeType node;
};

Название INSERT_­RETURN_­TYPE только экспозиция. INSERT_­RETURN_­TYPE имеет параметры шаблона, элементы данных и специальные элементы, указанные выше. У него нет других базовых классов или членов, кроме указанных.

Ассоциативные контейнеры обеспечивают быстрый поиск данных на основе ключей. Библиотека обеспечивает четыре основных вида ассоциативных контейнеров: set, multiset, map и multimap.

Каждый ассоциативный контейнер параметризован Key и имеет отношение упорядочения, Compare которое индуцирует a strict weak ordering на элементах Key. Кроме того, map и multimap связать произвольный файл mapped type T с расширениемKey. Объект типа Compare называется comparison object контейнером.

Фраза «эквивалентность ключей» означает отношение эквивалентности, налагаемое сравнением и not включением operator== ключей. То есть, два ключа k1 и k2 считаются эквивалентными , если для объекта сравнения comp, comp(k1, k2) == false && comp(k2, k1) == false. Для любых двух ключей k1 и k2 в том же контейнере, вызывающий comp(k1, k2) должен всегда возвращает то же значение.

Ассоциативный контейнер поддерживает, unique keys если он может содержать не более одного элемента для каждого ключа. В противном случае поддерживает equivalent keys. set И map классы поддерживают уникальные ключи; multiset и multimap классы поддержки эквивалентных ключей. Для multiset и multimap, insert, emplaceи erase сохранить относительный порядок эквивалентных элементов.

Для set и multiset тип значения совпадает с типом ключа. Ибо map и multimap он равен pair<const Key, T>.

iterator ассоциативного контейнера относится к категории двунаправленных итераторов. Для ассоциативных контейнеров, у которых тип значения совпадает с типом ключа, оба iterator и const_­iterator являются постоянными итераторами. Не определено ли или нет iterator и const_­iterator того же типа. [  Note: iterator и const_­iterator в этом случае имеют идентичную семантику и iterator могут быть преобразованы в const_­iterator. Пользователи могут избежать нарушения правила одного определения, всегда используя const_­iterator в своих списках параметров функций. ]  — end note 

Ассоциативные контейнеры соответствуют всем требованиям Allocator-aware контейнеров, за исключением map и multimap, требования, указанные value_­type в таблице, 83 применяются вместо key_­type и mapped_­type. [  Note: Например, в некоторых случаях key_­type и mapped_­type требуется, чтобы он был, CopyAssignable даже если связанный value_­type, pair<const key_­type, mapped_­type>не является CopyAssignable. ]  — end note 

В таблице 90, X обозначает ассоциативный класс контейнера, a обозначает значение типа X, a2 обозначает значение типа с узлами , совместимыми с типом X (таблица 89), b обозначает возможно , const значение типа X, u обозначает имя переменного объявляется, a_­uniq обозначает значение type, X когда X поддерживает уникальные ключи, a_­eq обозначает значение типа, X когда X поддерживает несколько ключей, a_­tran обозначает возможное const значение типа, X когда qualified-id X​::​key_­compare​::​is_­transparent является допустимым, и обозначает тип ([temp.deduct]), i и j удовлетворяет требованиям входного итератора и ссылается на элементы, неявно конвертируемые в value_­type, [i, j) обозначает допустимый диапазон , p обозначает допустимый итератор константы для a, q обозначает действительный итератор константы, для которого разыменовывается a, r обозначает действительный итератор, допускающий разыменование a, [q1, q2) обозначает допустимый диапазон итераторов констант в a, il обозначает объект типа initializer_­list<value_­type>, t обозначает значение типа X​::​value_­type, k обозначает значение типа X​::​key_­type и c обозначает возможное const значение типа X​::​key_­compare; kl это значение таким образом, что a это partitioned with respect to c(r, kl), с r ключевым значением , e и e в a; ku - такое значение, которое a разделено относительно !c(ku, r); ke - это такое значение, которое a разделено относительно c(r, ke) и !c(ke, r), с c(r, ke) подразумеваемым !c(ke, r). A обозначает распределитель памяти, используемый X, если он есть, или allocator<X​::​value_­type> иначе, m обозначает распределитель типа, в который можно преобразовать A, и nh обозначает неконстантное rvalue типа X​::​node_­type.

Члены insert и emplace не должны влиять на действительность итераторов и ссылок на контейнер, а erase члены должны аннулировать только итераторы и ссылки на удаленные элементы.

Эти extract члены недействительной только итераторы для удаленного элемента; указатели и ссылки на удаленный элемент остаются в силе. Однако доступ к элементу через такие указатели и ссылки, когда элемент принадлежит a, node_­type является неопределенным поведением. Ссылки и указатели на элемент, полученные, когда он принадлежит a, node_­type становятся недействительными, если элемент успешно вставлен.

Фундаментальным свойством итераторов ассоциативных контейнеров является то, что они перебирают контейнеры в неубывающем порядке ключей, где неубывающий порядок определяется сравнением, которое использовалось для их создания. Для любых двух разыменяемых итераторов i и j таких, что расстояние от i до j положительно, выполняется следующее условие:

value_comp(*j, *i) == false

Для ассоциативных контейнеров с уникальными ключами выполняется более сильное условие:

value_comp(*i, *j) != false

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

Шаблоны функций - членов find, count, lower_­bound, upper_­bound, и equal_­range не должен участвовать в разрешении перегрузки , если qualified-id Compare​::​is_­transparent не является действительным , и обозначает тип ([temp.deduct]).

Руководство по дедукции для ассоциативного контейнера не должно участвовать в разрешении перегрузки, если выполняется одно из следующих условий:

• (15.1)

  У него есть InputIterator параметр шаблона, и для этого параметра выводится тип, который не квалифицируется как итератор ввода.

• (15.2)

  У него есть Allocator параметр шаблона, и для этого параметра выводится тип, который не квалифицируется как распределитель.

• (15.3)

  У него есть Compare параметр шаблона, и для этого параметра выводится тип, который квалифицируется как распределитель.

Неупорядоченные ассоциативные контейнеры обеспечивают возможность быстрого извлечения данных на основе ключей. Сложность наихудшего случая для большинства операций является линейной, но средний случай намного быстрее. Библиотека предоставляет четыре неупорядоченные ассоциативные контейнеры: unordered_­set, unordered_­map, unordered_­multiset, и unordered_­multimap.

Неупорядоченные ассоциативные контейнеры соответствуют requirements for Containers, за исключением того, что выражения a == b и a != b имеют другую семантику, чем для других типов контейнеров.

Каждый неупорядоченный ассоциативный контейнер параметризуется Keyтипом объекта функции, Hash который соответствует Hash requirements и действует как хэш-функция для значений аргументов типа Key, а также двоичным предикатом, Pred который индуцирует отношение эквивалентности для значений типа Key. Кроме того, unordered_­map и unordered_­multimap связать произвольный файл mapped type T с расширением Key.

Тип объекта контейнера, Hash обозначаемый значком, hash называется объектом hash function контейнера. Тип объекта контейнера, Pred обозначаемый значком, pred называется объектомkey equality predicate контейнера.

Два значения k1 и k2 типа Key считаются эквивалентными, если предикат равенства ключей контейнера возвращается true при передаче этих значений. Если k1 и k2 эквивалентны, хеш-функция контейнера должна возвращать одинаковое значение для обоих. [  Note: Таким образом, когда неупорядоченный ассоциативный контейнер создается с Pred параметром, не являющимся параметром по умолчанию, ему обычно также требуется параметр, не являющийся Hash параметром по умолчанию . ] Для любых двух ключей в одном и том же контейнере вызов всегда должен возвращать одно и то же значение. Для любого ключа в контейнере вызов всегда должен возвращать одно и то же значение.  — end note  k1 k2 pred(k1, k2) k hash(k)

Неупорядоченный ассоциативный контейнер поддерживает, unique keys если он может содержать не более одного элемента для каждого ключа. В противном случае поддерживает equivalent keys. unordered_­set и unordered_­map поддерживают уникальные ключи. unordered_­multiset и unordered_­multimap поддержка эквивалентных ключей. В контейнерах, поддерживающих эквивалентные ключи, элементы с эквивалентными ключами соседствуют друг с другом в порядке итерации контейнера. Таким образом, хотя абсолютный порядок элементов в неупорядоченном контейнере не указан, его элементы сгруппированы так equivalent-key groups , что все элементы каждой группы имеют эквивалентные ключи. Операции мутации над неупорядоченными контейнерами должны сохранять относительный порядок элементов в каждой группе эквивалентных ключей, если не указано иное.

Для unordered_­set и unordered_­multiset тип значения совпадает с типом ключа. Ибо так unordered_­map и unordered_­multimap есть pair<const Key, T>.

Для неупорядоченных контейнеров, у которых тип значения совпадает с типом ключа, оба iterator и const_­iterator являются постоянными итераторами. Не определено ли или нет iterator и const_­iterator того же типа. [  Note: iterator и const_­iterator в этом случае имеют идентичную семантику и iterator могут быть преобразованы в const_­iterator. Пользователи могут избежать нарушения правила одного определения, всегда используя const_­iterator в своих списках параметров функций. ] — end note 

Элементы неупорядоченного ассоциативного контейнера организованы в buckets. Ключи с одинаковым хэш-кодом появляются в одном сегменте. Количество сегментов автоматически увеличивается по мере добавления элементов в неупорядоченный ассоциативный контейнер, поэтому среднее количество элементов в сегменте остается ниже установленного предела. Повторное хеширование делает недействительными итераторы, изменяет порядок между элементами и изменяет элементы сегментов, но не делает недействительными указатели или ссылки на элементы. Для unordered_­multiset и unordered_­multimapповторное хеширование сохраняет относительный порядок эквивалентных элементов.

Неупорядоченные ассоциативные контейнеры соответствуют всем требованиям Allocator-aware containers, за исключением unordered_­map и unordered_­multimap, требования, указанные value_­type в таблице, 83 применяются вместо key_­type и mapped_­type. [  Note: Например, key_­type и mapped_­type иногда требуется, чтобы он был, CopyAssignable даже если связанный value_­type, pair<const key_­type, mapped_­type>не является CopyAssignable. ]  — end note 

В таблице 91: X обозначает неупорядоченный ассоциативный контейнерный класс, a обозначает значение типа X, a2 обозначает значение типа с узлами, совместимыми с типом X (таблица 89), b обозначает возможное значение типа const X, a_­uniq обозначает значение типа, X когда X поддерживает уникальные ключи, a_­eq обозначает значение типа, X когда X поддерживает эквивалентные ключи, i и j обозначает итераторы ввода, на которые ссылаются value_­type, [i, j) обозначает допустимый диапазон p и q2 обозначает допустимые итераторы констант для a, q и q1 обозначает допустимые разыменяемые итераторы констант для a, r обозначает допустимый разыменяемый итератор для a, [q1, q2) обозначает допустимый диапазон в a, il обозначает значение типа initializer_­list<value_­type>, t обозначает значение типа X​::​value_­type, k обозначает значение типа key_­type, hf обозначает возможное значение типа const hasher, eq обозначает возможное значение типа const key_­equal, n обозначает значение типа size_­type, z обозначает значение типа floatи nh обозначает не -const r значение типа X​::​node_­type.

Два неупорядоченных контейнера a и b сравнение равны, если a.size() == b.size() и для каждой[Ea1, Ea2) полученной группы с a.equal_­range(Ea1)эквивалентным ключом существует группа с эквивалентным ключом, [Eb1, Eb2) полученная из b.equal_­range(Ea1), такая, что is_­permutation(Ea1, Ea2, Eb1, Eb2) возвращает true. Для unordered_­set и unordered_­mapсложность operator== (т. Е. Количество вызовов == оператора value_­type, предиката, возвращаемого key_­eq()функцией, и хешера, возвращаемого функцией hash_­function()) пропорциональна N в среднем случае и $N^2$ в худшем случае, где N - a. размер(). Для unordered_­multiset и unordered_­multimapсложность operator== пропорциональна $\sum E_i^2$ в среднем случае и $N^2$ в худшем случае, где N есть a.size(), и $E_i$ - размер группы $i^{\text{th}}$ эквивалентных ключей в a. Однако, если соответствующие элементы каждой соответствующей пары групп эквивалентных ключей $E{a}_i$ и $E{b}_i$ расположены в одном и том же порядке (как это обычно бывает, например, если a и b являются неизмененными копиями одного и того же контейнера), то средняя сложность для unordered_­multiset и unordered_­multimap становится пропорциональным N (но сохраняется сложность наихудшего случая $O\left(N^2\right)$, например, для патологически плохой хеш-функции). Поведение программы, которая использует operator== или operator!= на неупорядоченных контейнерах, не определено, если объекты функции Hash и Pred соответственно не имеют одинакового поведения для обоих контейнеров, а функция сравнения на равенство для Key является уточнением257 разделения на группы с эквивалентными ключами, созданными с помощью Pred.

Типы итераторов iterator и const_­iterator неупорядоченного ассоциативного контейнера относятся как минимум к категории прямого итератора. Для неупорядоченных ассоциативных контейнеров , где тип ключа и тип значения являются такими же, как iterator и const_­iterator постоянные итераторы.

Члены insert и emplace не должны влиять на действительность ссылок на элементы контейнера, но могут сделать недействительными все итераторы контейнера. В erase членах аннулируют только итераторы и ссылки на стертых элементы, и сохранить относительный порядок элементов, которые не стирается.

Члены insert и emplace не должны влиять на допустимость итераторов, если (N+n) <= z * B, где N - количество элементов в контейнере до операции вставки, n - количество вставленных элементов, B - количество z контейнеров и максимальный коэффициент загрузки контейнера.

Эти extract члены недействительной только итераторы для удаленного элемента, и сохранить относительный порядок элементов, которые не стерты; указатели и ссылки на удаленный элемент остаются в силе. Однако доступ к элементу через такие указатели и ссылки, когда элемент принадлежит a, node_­type является неопределенным поведением. Ссылки и указатели на элемент, полученные, когда он принадлежит a, node_­type становятся недействительными, если элемент успешно вставлен.

Руководство по дедукции для неупорядоченного ассоциативного контейнера не должно участвовать в разрешении перегрузки, если выполняется одно из следующих условий:

• (17.1)

  У него есть InputIterator параметр шаблона, и для этого параметра выводится тип, который не квалифицируется как итератор ввода.

• (17.2)

  У него есть Allocator параметр шаблона, и для этого параметра выводится тип, который не квалифицируется как распределитель.

• (17.3)

  У него есть Hash параметр шаблона, и для этого параметра выводится целочисленный тип или тип, который квалифицируется как распределитель.

• (17.4)

  У него есть Pred параметр шаблона, и для этого параметра выводится тип, который квалифицируется как распределитель.