¿El orden de iteración a través de std :: map es conocido (y está garantizado por el estándar)?

Question

Lo que quiero decir es que sabemos que los elementos de std::map están ordenados según las claves. Entonces, digamos que las claves son enteros. Si repito desde std::map::begin() a std::map::end() usando un for, ¿el estándar garantiza que voy a iterar en consecuencia a través de los elementos con las claves, ordenados en orden ascendente?

---

Ejemplo:

std::map<int, int> map_; 
map_[1] = 2; 
map_[2] = 3; 
map_[3] = 4; 
for(std::map<int, int>::iterator iter = map_.begin(); 
    iter != map_.end(); 
    ++iter) 
{ 
    std::cout << iter->second; 
} 

¿Es esta garantizada para imprimir 234 o se trata de implantación definidos?

---

razón la vida real: Tengo un std::map con int llaves. En situaciones muy raras, me gustaría iterar a través de todos los elementos, con clave, más que un valor concreto de int. Sí, parece que std::vector sería la mejor opción, pero fíjate en "situaciones muy raras".

---

EDITAR: Yo sé, que los elementos de std::map están ordenados .. no hay necesidad de señalarlo (para la mayoría de las respuestas aquí). Incluso lo escribí en mi pregunta.
Estaba preguntando sobre los iteradores y el orden cuando estoy iterando a través de un contenedor. Gracias @Kerrek SB por la respuesta.

Answer 1

Sí, eso está garantizado.Además, *begin() le da el elemento más pequeño y *rbegin() el más grande, según lo determinado por el operador de comparación, y dos valores clave a y b para los cuales la expresión !compare(a,b) && !compare(b,a) es verdadera se consideran iguales. La función de comparación predeterminada es std::less<K>.

El pedido no es una característica extra de la suerte, sino un aspecto fundamental de la estructura de datos, ya que el orden se utiliza para determinar cuándo dos claves son iguales (según la regla anterior) y para realizar búsquedas eficaces (esencialmente una búsqueda binaria, que tiene una complejidad logarítmica en el número de elementos).

Answer 2

¿Está esto garantizado para imprimir 234 o su implementación está definida?

Sí, std::map es un contenedor ordenada, ordenada por el Key con el Comparator suministrado. Por lo tanto, está garantizado.

Me gustaría ir a recorrer todos los elementos, con la clave, mayor que un valor int concreto.

Eso es seguramente posible.

Answer 3

Sí ... los elementos en un std::map tienen un orden débil estricto, lo que significa que los elementos se componen de un conjunto (es decir, no habrá repeticiones de teclas que son "iguales"), y la igualdad es determinado al probar cualquiera de dos claves A y B, que si la clave A no es inferior a la clave B, y B no es inferior a A, entonces la clave A es igual a la clave B.

Dicho esto, no se puede correctamente ordene los elementos de un std::map si el orden débil para ese tipo es ambiguo (en su caso, donde está usando números enteros como clave-tipo, eso no es un problema). Debe poder definir una operación que defina un pedido total en el tipo que está utilizando para las claves en su std::map; de lo contrario, solo tendrá un pedido parcial de sus elementos, o poset, que tiene una propiedad donde A puede no ser comparable a B. Lo que típicamente sucederá en este escenario es que podrá insertar los pares de clave/valor, pero puede terminar con pares duplicados de clave/valor si recorre todo el mapa y/o detecta "falta" "pares clave/valor" cuando intenta realizar un std::map::find() de un par clave/valor específico en el mapa.

Answer 4

Creo que hay una confusión en las estructuras de datos.

En la mayoría de los idiomas, map es simplemente un contenedor asociativo: asigna una clave a un valor. En los idiomas "más nuevos", esto generalmente se logra usando un mapa hash, por lo tanto, no se garantiza ninguna orden.

En C++, sin embargo, esto no es así:

• std::map es una ordenados contenedor asociativo
• std::unordered_map es un contenedor asociativo basado tabla hash introducido en C++ 11

Por lo tanto, para aclarar las garantías en el pedido.

En C++ 03:

• std::set, std::multiset, std::map y std::multimap están garantizados para ser ordenados de acuerdo a las teclas (y el criterio suministrado)
• en std::multiset y std::multimap, la norma no impone ninguna orden de garantía en elementos equivalentes (es decir, aquellos que se comparan por igual)

En C++ 11:

• std::set, std::multiset, std::map y std::multimap están garantizados para ser ordenados de acuerdo a las teclas (y el criterio suministrado)
• en std::multiset y std::multimap, la Norma impone que los elementos equivalentes (los que se comparan iguales) se ordenan de acuerdo con su orden de inserción (primero se inserta primero)
• std::unordered_* Los contenedores son, como su nombre implica, no ordenados. En particular, el orden de los elementos puede cambiar cuando se modifique el contenedor (tras la inserción/eliminación).

cuando la norma dice que los elementos se ordenan de una manera, esto significa que:

• cuando se repite, que ver los elementos en el orden definido
• cuando se repite a la inversa, se ve la elementos en el orden opuesto

Espero que esto borre cualquier confusión.

Answer 5

Esto está garantizado por los requisitos de contenedor asociativo en el estándar C++. P.ej. ver 23.2.4/10 en C++ 11:

 
The fundamental property of iterators of associative containers is that they 
iterate through the containers in the non-descending order of keys where 
non-descending is defined by the comparison that was used to construct them. 
For any two dereferenceable iterators i and j such that distance from i to j is 
positive, 
    value_comp(*j, *i) == false 

y 23.2.4/11

 
For associative containers with unique keys the stronger condition holds, 
    value_comp(*i, *j) != false.