Requisitos denominados de C++: AssociativeContainer
De cppreference.com
Un contenedor asociativo (AssociativeContainer) es un contenedor (Container) ordenado que proporciona una búsqueda rápida de objetos basada en claves.
Un contenedor asociativo admite claves únicas si puede contener como máximo un elemento por cada clave. En otro caso, admite claves equivalentes.
Contenido |
[editar] Requisitos
Leyenda | |
X
|
Una clase contenedor asociativo |
T
|
El tipo de elemento de X
|
A
|
El tipo de asignador de X: X::allocator_type si existe, en otro caso std::allocator<X::value_type>
|
| a | Un valor de tipo X
|
| a2 | Un valor de un tipo Y cuyo identificadores de nodo son compatibles con X
|
| b | Un valor de tipo X o const X
|
| u | El nombre de una variable que se declara |
| a_uniq | Un valor de tipo X cuando X soporta claves únicas
|
| a_eq | Un valor de tipo X cuando X soporta claves equivalentes
|
| a_tran | Un valor de tipo X o const X cuando existe el tipo X::key_compare::is_transparent
|
| i, j | InputIterator referidos a elementos implícitamente convertible a X::value_type
|
[i, j)
|
Un rango válido |
| rg (desde C++23) |
Un valor de un tipo R que modela container-compatible-range<value_type>
|
| p | Un iterador constante válido a a |
| q | Un iterador constante desreferenciable válido a a |
| r | Un iterador desreferenciable válido a a |
| q1, q2 | Un rango válido de iteradores contantes en a |
| il | Un objeto de tipo std::initializer_list<X::value_type> |
| t | Un valor de tipo X::value_type
|
| k | Un valor de tipo X::key_type
|
| c | Un valor de tipo X::key_compare o const X::key_compare
|
| kl | Un valor tal que a está particionado con respecto a c(x, kl), con x como valor de clave de e y e en a |
| ku | Un valor tal que a está particionado con respecto a !c(ku, x), con x como valor de clave de e y e en a |
| ke | Un valor tal que a está particionado con respecto a c(x, ke) y !c(ke, x), con c(x, ke) implicando !c(ke, x) y con x como valor de clave de e y e en a |
| kx (desde C++23) |
Un valor tal que:
|
| m | Un asignador de un tipo convertible a A
|
| nh | Un r-valor no constante de tipo X::node_type
|
El tipo X satisface AssociativeContainer si
- El tipo
Xsatisface Container (hasta C++11)AllocatorAwareContainer (desde C++11), - Está parametrizado en la
Clavey una relación de ordenaciónCompareque induce un ordenamiento débil estricto en loa elementos deClave, y- Además, std::map y std::multimap asocian un tipo mapeado arbitrario
Tcon laClave. - El objeto de tipo
Comparese denomina objeto de comparación de un contenedor de tipoX.
- Además, std::map y std::multimap asocian un tipo mapeado arbitrario
- Las siguientes expresiones deben ser válidas y tener sus efectos especificados para todos los contenedores asociativos:
[editar] Tipos
| Nombre | Tipo | Requisitos |
|---|---|---|
key_type
|
Clave
|
|
mapped_type
|
T (solamente para std::map y std::multimap)
|
|
value_type
|
|
Erasable a partir de X
|
key_compare
|
Compare
|
CopyConstructible |
value_compare
|
|
BinaryPredicate |
node_type
|
Una especialización de la plantilla de clase de identificador de nodo, tal que los tipos anidados públicos son los mismo tipos que los tipos correspondientes en X.
|
[editar] Funciones miembro y operadores
| Expresión | Resultado | Precondiciones | Efectos | Retorno | Complejidad |
|---|---|---|---|---|---|
| X(c) | Construye un contenedor vacío. Usa una copia de c como objeto de comparación | Constante | |||
| X u = X(); X u; |
key_compare cumple con los requisitos DefaultConstructible
|
Construye un contenedor vacío. Usa Compare() como un objeto de comparación | Constante | ||
| X(i, j, c) | value_type es EmplaceConstructible en X a partir de *i
|
Construye un contenedor vacío e inserta elementos del rango [i, j) en el; usa c como un objeto de comparación
|
En general N·log(N), donde N tiene el valor std::distance(i, j); lineal si [i, j) está ordenado con respecto a value_comp()
| ||
| X(i, j) | key_compare cumple los requisitos DefaultConstructible. value_type es EmplaceConstructible en X a partir de *i
|
Construye un contenedor vacío e inserta elementos del rango [i, j) en el; usa Compare() como un objeto de comparación
|
|||
| X(from_range, rg, c) (desde C++23) |
value_type es EmplaceConstructibleen X a partir de *ranges::begin(rg)
|
Construye un contenedor vacío e inserta cada elemento de rg en el. Usa c como el objeto de comparación | En general N·log(N), donde N tiene el valor ranges::distance(rg); lineal si rg está ordenado con respecto a value_comp()
| ||
| X(from_range, rg) (desde C++23) |
key_compare cumple los requisitos de DefaultConstructible. value_type es EmplaceConstructible en X a partir de *ranges::begin(rg)
|
Construye un contenedor vacío e inserta cada elemento de rg en el. Usa Compare() como objeto de comparación | |||
| X(il, c) | X(il.begin(), il.end(), c) | ||||
| X(il) | X(il.begin(), il.end()) | ||||
| a = il | X& | value_type es CopyInsertable en X y CopyAssignable
|
Asigna el rango [il.begin(), il.end()) a a. Todos los elementos existentes en a se asignan o se destruyen
|
En general N·log(N), donde N tiene el valor il.size() + a.size(); lineal si [il.begin(), il.end()) está ordenado con respecto a value_comp()
| |
| b.key_comp() | X::key_compare
|
El objeto de comparación a partir del cual se construyó b | Constante | ||
| b.value_comp() | X::value_compare
|
Un objeto de value_compare construido a partir del objeto de comparación
|
Constante | ||
| a_uniq.emplace(args) | std::pair< iterator, bool> |
value_type es EmplaceConstructible en X a partir de args
|
Inserta un objeto value_type t construido con std::forward<Args>(args)... si y solo si no hay ningún elemento en el contenedor con una clave equivalente a la clave de t
|
El componente bool del par devuelto es true si y solo si se lleva a cabo la inserción, y el componente iterador del par apunta al elemento con clave equivalente a la clave de t | Logarítmica |
| a_eq.emplace(args) | iterator
|
value_type es EmplaceConstructible en X a partir de args
|
Inserta un objeto value_type t construido con std::forward<Args>(args).... Si existe un rango que contiene elementos equivalentes a t en a_eq, t se inseta al final de ese rango
|
Un iterador apuntando al nuevo elemento insertado | Logarítmica |
| a.emplace_hint(p, args) | iterator
|
Equivalente a
a.emplace( |
Un iterador apuntando al elemento con la clave equivalente al nuevo elemento insertado | En general logarítmica, pero se amortiza constante si el elemento se inserta justo antes de p | |
| a_uniq.insert(t) | std::pair< iterator, bool> |
Si t es un rvalor no constane, value_type es MoveInsertable en X; en otro caso, value_type es CopyInsertable en X
|
Inserta t si y solo si no hay ningún elemento en el contenedor con la clave equivalente a la clave de t | El componente bool del par devuelto es true si y solo si tuvo lugar la inserción, y el componente iterator del par apunta al elemento con la clave equivalente a la clave de t
|
Logarítmica |
| a_eq.insert(t) | iterator
|
Si t es un rvalor no constante, value_type es MoveInsertable en X; en otro caso, value_type es CopyInsertable en X
|
Inserta t y devuelve el iterador apuntando al nuevo elemento insertado. Si existe un rango que contiene elementos equivalentes a t en a_eq, t se inserta al final de esta rango | Logarítmica | |
| a.insert(p, t) | iterator
|
Si t es un rvalor no constante, value_type es MoveInsertable en X; en otro caso, value_type es CopyInsertable en X
|
Inserta t si y solo si no hay ningún elemento con clave equivalente a la clave de t en contenedores con clave única; siempre inserta t en contenedores con claves equivalentes. t se inserta tan cerca como sea posible de la posición justo anterior as p | Un iterador apuntado al elemento con la clave equivalente a la clave de t | En general logarítmica, pero se amortiza constante si t se inserta justo antes de p |
| a.insert(i, j) | void | value_type es EmplaceConstructible en X a partir de *i. Ni i ni j son iteradores en a
|
Inserta cada elemento del rango [i, j) si y solo si no hay ningún elemento con clave equivalente a la clave de este elemento en contenedores con claves únicas; siempre inserta este elemento en contenedores con claves equivalentes
|
N·log(a.size() + N), donde N tiene el valor std::distance(i, j)
| |
| a.insert_range(rg) (desde C++23) |
void | value_type es EmplaceConstructible en X a partir de *ranges::begin(rg). rg y a no se solapan
|
Inserta cada elemento de rg si y solo si no hay ningún elemento con clave equivalente a la clave de este elemento para contenedores de clave única; siempre inserta este elemento en contenedores de clave equivalente | N·log(a.size() + N), done N tiene el valor ranges::distance(rg)
| |
| a.insert(il) | a.insert(il.begin(), il.end()) | ||||
| a_uniq.insert(nh) | insert_return_type
|
nh esta vacío o
a_uniq.get_allocator() |
Si nh está vacío, no tiene efecto. En otro caso, inserta los elementos pertenecientes a nh si y solo si no hay ningún elemento en el contenedor con una clave equivalente a nh.key() | Si nh está vacío, inserted es false, position es end(), y node está vacío. En otro caso si la inserción tiene lugar, inserted es true, position apunta al elemento insertado, y node está vacío; si la inserción falla, inserted es false, node tiene el valor anterior de nh, y position apunta a un elemento con clave equivalente a nh.key()
|
Logarítmica |
| a_eq.insert(nh) | iterator
|
nh está vacío o
a_eq.get_allocator() |
Si nh está vacío, no tiene efecto y devuelve a_eq.end(). En otro caso, inserta el elemento de nh y devuelve un iterador apuntando al nuevo elemento insertado. Si existe un rango que contiene elementos con claves equivalentes a nh.key() en a_eq, el elemento se inserta al final del rango. Asegura: nh está vacío | Logarítmica | |
| a.insert(p, nh) | iterator
|
nh esta vacía o
a.get_allocator() |
Si nh está vacío, no tiene efecto y devuelves a.end(). En otro caso, inserta el elemento de nh si y solo si no hay ningún elemento con una clave equivalente a nh.key() en contenedores con clave única; siempre inserta el elemento de nh en contenedores con claves equivalentes. El elemento se inserta tan cerca como sea posible a la posición justo anterior a p. Garantiza: nh está vacía si la inserción tiene lugar, sin cambios si la inserción falla | Un iterador apuntando al elemento con clave equivalente a nh.key() | En general logarítmica, pero se amortiza constante si el elemento se inserta justo antes de p |
| a.extract(k) | node_type
|
Elimina el primer elemento en el contenedor con clave equivalente a k | Un node_type con el elemento si se encuentra, en otro caso un node_type vacío
|
log(a.size()) | |
| a_tran.extract(kx) (desde C++23) |
node_type
|
Elimina el primer elemento en el contenedor con clave r tal que !c(r, kx) && !c(kx, r) es true | Un node_type con el elemento si se encuentra, en otro caso un node_type vacío
|
log(a_tran.size()) | |
| a.extract(q) | node_type
|
Elimina el elemento apuntado por q | Un node_type que tiene ese elemento
|
Amortizado constante | |
| a.merge(a2) | void | a.get_allocator() == a2.get_allocator() |
Intenta extraer cada elemento de a2 e inserta en a usando el objeto de comparación de a. En contenedores con claves únicas, si hay un elemento en a con clave equivalente a la clave de un elemento de a2, entonces este elemento no se extrae de a2. Garantiza: Los punteros y las referencias a los elementos transferidos de a2 hacen referencia a esos mismos elementos pero como miembros de a. Los iteradores que hacen referencia a los elementos transferidos seguirán haciendo referencia a sus elementos, pero ahora se comportan como iteradores en a, no en a2. Excepciones: Nada a menos que el objeto de comparación lance una excepción | N·log(a.size() + N), donde N tiene el valor a2.size()
| |
| a.erase(k) | size_type
|
Elimina todos los elementos en el contenedor con clave equivalente a k | El número de elementos eliminados | log(a.size()) + a.count(k) | |
| a_tran.erase(kx) (desde C++23) |
size_type
|
Elimina todos los elementos en el contenedor con clave r tal que !c(r, kx) && !c(kx, r) es true | El número de elementos eliminados | log(a_tran.size()) + a_tran.count(kx) | |
| a.erase(q) | iterator
|
Elimina el elemento apuntado por q | Un iterador que apunta al elemento inmediatamente posterior a q antes de borrar el elemento. Si dicho elemento no existe, devuelve a.end() | Amortizado constante | |
| a.erase(r) | iterator
|
Elimina el elemento apuntado por r | Un iterador apuntado al elemento inmediatamente posterior a r antes de eliminar el elemento. Si dicho elemento no existe, devuelve a.end() | Amortizado constante | |
| a.erase(q1, q2) | iterator
|
Elimina todos los elementos en el rango[q1, q2)
|
Un iterador apuntando al elemento apuntado por q2 antes de eliminar cualquier elemento. Si dicho elemento no existe, se devuelve a.end() | log(a.size()) + N, donde N tiene el valor std::distance(q1, q2)
| |
| a.clear() | a.erase(a.begin(), a.end()). Asegura: a.empty() es true | Lineal en a.size() | |||
| b.find(k) | iterator; const_iterator para b constante
|
Un iterador que apunta a un elemento cuya clave es equivalente a k, o b.end() si dicho elemento no se encuentra | Logarítmica | ||
| a_tran.find(ke) | iterator; const_iterator para a_tran constante
|
Un iterador apuntando a un elemento con clave r tal que
!c(r, ke) && |
Logarítmica | ||
| b.count(k) | size_type
|
El número de elementos con clave equivalente a k | log(b.size()) + b.count(k) | ||
| a_tran.count(ke) | size_type
|
El número de elementos con clave r tal que
!c(r, ke) && |
log(a_tran.size()) + a_tran.count(ke) | ||
| b.contains(k) | bool | return b.find(k) != b.end(); | |||
| a_tran.contains(ke) | bool |
return |
|||
| b.lower_bound(k) | iterator; const_iterator para b constante
|
Un iterador apuntando al primer elemento con clave no menor que k, o b.end() si dicho elemento no se encuentra | Logarítmica | ||
| a_tran.lower_bound(kl) | iterator; const_iterator para a_tran constante
|
Un iterador apuntando al primer elemento con clave r tal que !c(r, kl), o a_tran.end() si dicho elemento no se encuentra | Logarítmica | ||
| b.upper_bound(k) | iterator; const_iterator para b constante
|
Un iterador apuntando al primer elemento con una clave mayor que k, o b.end() si dicho elemento no se encuentra | Logarítmica | ||
| a_tran.upper_bound(ku) | iterator; const_iterator para a_tran constante
|
Un iterador apuntado al primer elemento con clave r tal que c(ku, r), o a_tran.end() si dicho elemento no se encuentra | Logarítmica | ||
| b.equal_range(k) | std::pair< iterator, iterator>; std::pair< |
Equivalente a:
return |
Logarítmica | ||
| a_tran.equal_range(ke) | std::pair< iterator, iterator>; std::pair< |
Equivalente a:
return |
Logarítmica |
[editar] Iteradores
Los iteradores de contenedores asociativos satisfacen los requisitos de BidirectionalIterator.
Para contenedores asociativos donde value_type es el mismo que key_type, iterator y const_iterator son iteradores constantes. No se especifica si iterator y const_iterator son del mismo tipo.
Los iteradores de contenedores asociativos iteran a través de los contenedores en el orden no descendente de claves, donde no descendente se define por la comparación que se usó para construir los contenedores. Es decir, dado
- a, un contenedor asociativo
- i y j, iteradores desreferenciables a a.
Si la distancia de i a j es positiva, entonces a.value_comp()(*j, *i) == false. Además, si a es un contenedor asociativo con claves únicas, se cumple la condición más fuerte a.value_comp()(*i, *j) != false.
| Esta sección está incompleta Razón: Requisitos finales. |
[editar] Contenedores asociativos en la biblioteca estándar
| Colección de claves, ordenada por claves, donde las claves son únicas. (plantilla de clase) | |
| Colección de claves, ordenada por claves. (plantilla de clase) | |
| Colección de pares de clave y valor, ordenados por claves, donde las claves son únicas. (plantilla de clase) | |
| Colección de pares de clave y valor, ordenados por claves. (plantilla de clase) |
[editar] Informes de defectos
Los siguientes informes de defectos de cambio de comportamiento se aplicaron de manera retroactiva a los estándares de C++ publicados anteriormente.
| ID | Aplicado a | Comportamiento según lo publicado | Comportamiento correcto |
|---|---|---|---|
| LWG 354 | C++98 | lower_bound y upper_bound no devolvíanel iterador end si no se encuentra el elemento |
se devuelve el iterador end en este caso |
| LWG 589 | C++98 | los elementos a los que hacen referencia i y j tenían el tipo X::value_type
|
los elementos son convertibles implícitamente a X::value_type
|
