Ассоциативные контейнеры обеспечивают быстрый поиск данных на основе ключей. Библиотека обеспечивает четыре основных вида ассоциативных контейнеров: set, multiset, map и multimap.
Каждый ассоциативный контейнер параметризован Key и имеет отношение упорядочения, Compare которое индуцирует astrict 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.
| Выражение | Тип возврата | Утверждение / примечание | Сложность |
| до / после состояния | |||
| X::key_type | Key | время компиляции | |
| X::mapped_type (map иmultimap только) | T | время компиляции | |
| X::value_type (set иmultiset только) | Key | Requires: value_type этоErasable изX | время компиляции |
| X::value_type (map иmultimap только) | pair<const Key, T> | Requires: value_type этоErasable изX | время компиляции |
| X::key_compare | Compare | Requires: key_compare естьCopyConstructible. | время компиляции |
| X::value_compare | бинарный тип предиката | то же самое, что иkey_compare дляset и multiset; является отношением порядка на парах, индуцированным первой компонентой (т. е.Key) дляmap иmultimap. | время компиляции |
| X::node_type | специализацияnode_handle шаблона класса, так что общедоступные вложенные типы являются теми же типами, что и соответствующие типы вX. | видеть[container.node] | время компиляции |
| X(c) X u(c); | Effects: Создает пустой контейнер. Использует копиюc как объект сравнения. | постоянный | |
| X() X u; |
Requires: key_compare естьDefaultConstructible. Effects: Создает пустой контейнер. ИспользуетсяCompare() как объект сравнения | постоянный | |
| X(i,j,c) X u(i,j,c); |
Requires: value_type находитсяEmplaceConstructible вX от*i. Effects: Создает пустой контейнер и вставляет в него элементы из диапазона[i, j) ; используетсяc как объект сравнения. | NlogN в общем, гдеN имеет значениеdistance(i, j); линейный, если[i, j) отсортировано с помощьюvalue_comp() | |
| X(i,j) X u(i,j); |
Requires: key_compare естьDefaultConstructible.
value_type находитсяEmplaceConstructible вX от*i. Effects: То же, что и выше, но используетсяCompare() как объект сравнения. | то же, что и выше | |
| X(il) | такой же какX(il.begin(), il.end()) | такой же какX(il.begin(), il.end()) | |
| X(il,c) | такой же какX(il.begin(), il.end(), c) | такой же какX(il.begin(), il.end(), c) | |
| a = il | X& |
Requires: value_type находится
CopyInsertable вX
иCopyAssignable. Effects: Назначает диапазон[il.begin(), il.end()) вa. Все существующие элементыa либо присваиваются, либо уничтожаются. | NlogN в общем, гдеN имеет значениеil.size() + a.size(); линейный, если[il.begin(), il.end()) отсортировано с помощьюvalue_comp() |
| b.key_comp() | X::key_compare | возвращает объект сравнения, из которогоb был построен. | постоянный |
| b.value_comp() | X::value_compare | возвращает объект,value_compare созданный из объекта сравнения | постоянный |
| a_uniq.emplace(args) | pair<iterator, bool> |
Requires: value_type должен бытьEmplaceConstructible вX отargs. Effects: Вставляетvalue_type объект,t созданный с помощью std::forward<Args>(args)... if и только если в контейнере нет элемента с ключом, эквивалентным ключуt.bool Компонент возвращаемой парыtrue тогда и только тогда , когда имеет место вставка, а итератор компонент из точек пары к элементу с ключом , эквивалентным ключомt. | логарифмический |
| a_eq.emplace(args) | iterator |
Requires: value_type должен бытьEmplaceConstructible вX отargs. Effects: Вставляетvalue_type объект, созданныйt с помощью, std::forward<Args>(args)... и возвращает итератор, указывающий на вновь вставленный элемент. Если диапазон, содержащий элементы, эквивалентныеt существующим вa_eq, t вставляется в конец этого диапазона. | логарифмический |
| a.emplace_hint(p, args) | iterator | эквивалентноa.emplace(std::forward<Args>(args)...). Возвращаемое значение - это итератор, указывающий на элемент с ключом, эквивалентным вновь вставленному элементу. Элемент вставляется как можно ближе к позиции непосредственно передp. | логарифмическая в целом, но амортизированная константа, если элемент вставлен прямо передp |
| a_uniq.insert(t) | pair<iterator, bool> |
Requires: Еслиt - неконстантное выражение rvalue,value_type должно быть
MoveInsertable вX; в противном случаеvalue_type будет
CopyInsertable вX. Effects: Вставляетt тогда и только тогда, когда в контейнере нет элемента с ключом, эквивалентным ключуt.bool Компонент возвращаемой парыtrue тогда и только тогда , когда имеет место вставки, иiterator компонент точек пары к элементу с ключом , эквивалентным ключомt. | логарифмический |
| a_eq.insert(t) | iterator |
Requires: Еслиt - неконстантное выражение rvalue,value_type должно быть
MoveInsertable вX; в противном случаеvalue_type будет
CopyInsertable вX. Effects: Вставляетt и возвращает итератор, указывающий на вновь вставленный элемент. Если диапазон, содержащий элементы, эквивалентные t существующим вa_eq,t вставляется в конец этого диапазона. | логарифмический |
| a.insert(p, t) | iterator |
Requires: Еслиt - неконстантное выражение rvalue,value_type должно быть
MoveInsertable вX; в противном случаеvalue_type будет
CopyInsertable вX. Effects: Вставляет,t если и только если нет элемента с ключом, эквивалентным ключуt в контейнерах с уникальными ключами; всегда вставляетt в контейнеры с эквивалентными ключами. Всегда возвращает итератор, указывающий на элемент с ключом, эквивалентным ключуt.t вставляется как можно ближе к позиции непосредственно передp. | логарифмическая в целом, но амортизированная константа, еслиt вставлена прямо перед нейp. |
| a.insert(i, j) | void |
Requires: value_type должен бытьEmplaceConstructible вX от*i. Requires:i,j не являются итераторами вa. вставляет каждый элемент из диапазона[i, j) тогда и только тогда, когда нет элемента с ключом, эквивалентным ключу этого элемента, в контейнерах с уникальными ключами; всегда вставляет этот элемент в контейнеры с эквивалентными ключами. | Nlog(a.size()+N), гдеN имеет значениеdistance(i, j) |
| a.insert(il) | void | эквивалентноa.insert(il.begin(), il.end()) | |
| a_uniq.insert(nh) | insert_return_type |
Requires:nh пусто или
a_uniq.get_allocator() == nh.get_allocator(). Effects: Еслиnh пусто, не действует. В противном случае вставляет элемент, владельцем которого является,nh тогда и только тогда, когда в контейнере нет элемента с ключом, эквивалентнымnh.key(). Postconditions: Еслиnh пусто,inserted естьfalse, position естьend()иnode пусто. В противном случае, если вставка имела место,inserted istrue, position указывает на вставленный элемент иnode является пустым; если вставка не удалась,inserted этоfalse, node имеет предыдущее значениеnh, иposition указывает на элемент с ключом , эквивалентнымnh.key(). | логарифмический |
| a_eq.insert(nh) | iterator |
Requires:nh пусто или
a_eq.get_allocator() == nh.get_allocator(). Effects: Еслиnh пусто, не действует и возвращаетсяa_eq.end(). В противном случае вставляет элемент, которым владеет,nh и возвращает итератор, указывающий на вновь вставленный элемент. Если диапазон, содержащий элементы с ключами, эквивалентными,nh.key() существует вa_eq, элемент вставляется в конец этого диапазона. Postconditions:nh пустой. | логарифмический |
| a.insert(p, nh) | iterator |
Requires:nh пусто или
a.get_allocator() == nh.get_allocator(). Effects: Еслиnh пусто, не действует и возвращаетсяa.end(). В противном случае вставляет элемент, принадлежащий пользователюnh тогда и только тогда, когда нет элемента с ключом, эквивалентнымnh.key() в контейнерах с уникальными ключами; всегда вставляет элемент, которым владеет,nh в контейнеры с эквивалентными ключами. Всегда возвращает итератор, указывающий на элемент с ключом, эквивалентнымnh.key(). Элемент вставляется как можно ближе к позиции непосредственно передp. Postconditions:nh пусто, если вставка прошла успешно, не изменяется, если вставка не удалась. | логарифмическая в общем случае, но амортизированная константа, если элемент вставлен прямо перед нимp. |
| a.extract(k) | node_type | удаляет первый элемент в контейнере с ключом, эквивалентнымk. Возвращает элемент,node_type владеющий элементом, если он найден, в противном случае - пустой node_type. | log(a.size()) |
| a.extract(q) | node_type | удаляет элемент, на который указываетq. Возвращаетnode_type владение этим элементом. | амортизированная постоянная |
| a.merge(a2) | void |
Requires:a.get_allocator() == a2.get_allocator(). Пытается извлечь каждый элементa2 и вставить его сa помощью объекта сравненияa. В контейнерах с уникальными ключами, если есть элементa с ключом, эквивалентным ключу элемента изa2, то этот элемент не извлекается изa2. Postconditions: Указатели и ссылки на переданные элементыa2 относятся к тем же элементам, но как членамa. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы вa, а не вa2. Throws: Ничего, если объект сравнения не выбрасывает. | Nlog(a.size()+N), гдеN имеет значениеa2.size(). |
| a.erase(k) | size_type | стирает все элементы в контейнере с ключом, эквивалентным k. возвращает количество стертых элементов. | log(a.size())+a.count(k) |
| a.erase(q) | iterator | стирает элемент, на который указываетq. Возвращает итератор, указывающий на элемент, следующий сразу заq стираемым элементом. Если такого элемента нет, возвращаетсяa.end(). | амортизированная постоянная |
| a.erase(r) | iterator | стирает элемент, на который указываетr. Возвращает итератор, указывающий на элемент, следующий сразу заr стираемым элементом. Если такого элемента нет, возвращаетсяa.end(). | амортизированная постоянная |
| a.erase( q1, q2) | iterator | стирает все элементы в диапазоне[q1, q2). Возвращает итератор, указывающий на элемент, на который указывает доq2 стирания каких-либо элементов. Если такого элемента не существует,a.end() возвращается. | log(a.size())+N, гдеN имеет значениеdistance(q1, q2). |
| a.clear() | void |
a.erase(a.begin(),a.end()) Postconditions:a.empty() возвращаетсяtrue. | линейно вa.size(). |
| b.find(k) | iterator;const_iterator для постоянногоb. | возвращает итератор, указывающий на элемент с ключом, эквивалентнымk, илиb.end() если такой элемент не найден | логарифмический |
| a_tran. find(ke) | iterator;const_iterator для постоянногоa_tran. | возвращает итератор, указывающий на элемент сr таким ключом , что !c(r, ke) && !c(ke, r), илиa_tran.end() если такой элемент не найден | логарифмический |
| b.count(k) | size_type | возвращает количество элементов с ключом, эквивалентнымk | log(b.size())+b.count(k) |
| a_tran. count(ke) | size_type | возвращает количество элементов сr таким ключом , что !c(r, ke) && !c(ke, r) | log(a_tran.size())+a_tran.count(ke) |
| b.lower_bound(k) | iterator;const_iterator для постоянногоb. | возвращает итератор, указывающий на первый элемент с ключом не меньше чемk, илиb.end() если такой элемент не найден. | логарифмический |
| a_tran. lower_bound(kl) | iterator;const_iterator для постоянногоa_tran. | возвращает итератор, указывающий на первый элемент сr таким ключом , что!c(r, kl)или,a_tran.end() если такой элемент не найден. | логарифмический |
| b.upper_bound(k) | iterator;const_iterator для постоянногоb. | возвращает итератор, указывающий на первый элемент с ключом больше чемk, илиb.end() если такой элемент не найден. | логарифмический |
| a_tran. upper_bound(ku) | iterator;const_iterator для постоянногоa_tran. | возвращает итератор, указывающий на первый элемент сr таким ключом , чтоc(ku, r)или,a_tran.end() если такой элемент не найден. | логарифмический |
| b.equal_range(k) | pair<iterator, iterator>; pair<const_iterator, const_iterator> для постоянногоb. | эквивалентноmake_pair(b.lower_bound(k), b.upper_bound(k)). | логарифмический |
| a_tran. equal_range(ke) | pair<iterator, iterator>; pair<const_iterator, const_iterator> для постоянногоa_tran. |
эквивалентно . make_pair( a_tran.lower_bound(ke), a_tran.upper_bound(ke)) | логарифмический |
Члены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-idCompare::is_transparent не является действительным , и обозначает тип ([temp.deduct]).
Руководство по дедукции для ассоциативного контейнера не должно участвовать в разрешении перегрузки, если выполняется одно из следующих условий:
У него естьInputIterator параметр шаблона, и для этого параметра выводится тип, который не квалифицируется как итератор ввода.
У него естьAllocator параметр шаблона, и для этого параметра выводится тип, который не квалифицируется как распределитель.
У него естьCompare параметр шаблона, и для этого параметра выводится тип, который квалифицируется как распределитель.
Для ассоциативных контейнеров ни однаclear() функция не генерирует исключение. erase(k) не генерирует исключение, если это исключение не вызваноCompare объектом контейнера (если есть).
Для ассоциативных контейнеров, если какая-либо операция из функцииinsert или,emplace вставляющая один элемент, вызывает исключение, вставка не имеет никакого эффекта.