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

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 realizo iteraciones desde std::map::begin() a std::map::end() usando a for , ¿el estándar garantiza que voy a iterar en consecuencia a través de los elementos con claves, ordenados en orden ascendente?


Ejemplo:

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

¿Está garantizado que se imprima 234 o está definida su implementación?


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


EDITAR : Sé que los elementos de std::map están ordenados … no es necesario 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.

    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 cierto se consideran iguales. La función de comparación predeterminada es std::less .

    El orden no es una característica de bonificación afortunada, sino que es un aspecto fundamental de la estructura de datos, ya que el orden se utiliza para determinar cuándo dos claves son las mismas (según la regla anterior) y para realizar una búsqueda eficiente (esencialmente una binaria búsqueda, que tiene una complejidad logarítmica en la cantidad de elementos).

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

     La propiedad fundamental de los iteradores de contenedores asociativos es que
     iterar a través de los contenedores en el orden no descendente de las teclas donde
     No descendente se define por la comparación que se utilizó para construirlos.
     Para dos iteradores sin referencias i y j tales que la distancia de i a j es
     positivo,
       value_comp (* j, * i) == falso
    

    y 23.2.4 / 11

     Para contenedores asociativos con claves únicas, la condición más fuerte se mantiene,
       value_comp (* i, * j)! = falso.
    

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

    En la mayoría de los idiomas, un 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 un contenedor asociativo ordenado
    • std::unordered_map es un contenedor asociativo basado en hash-table introducido en C ++ 11

    Entonces, para aclarar las garantías en el pedido.

    En C ++ 03:

    • std::set , std::multiset , std::map y std::multimap se garantiza que se ordenan de acuerdo con las claves (y el criterio proporcionado)
    • en std::multiset y std::multimap , la norma no impone ninguna garantía de orden en elementos equivalentes (es decir, aquellos que se comparan por igual)

    En C ++ 11:

    • std::set , std::multiset , std::map y std::multimap se garantiza que se ordenan de acuerdo con las claves (y el criterio proporcionado)
    • en std::multiset y std::multimap , el estándar impone que los elementos equivalentes (los que se comparan por igual) se ordenan según su orden de inserción (primero insertado primero)
    • std::unordered_* contenedores son, como su nombre implica, no ordenados. En particular, el orden de los elementos puede cambiar cuando el contenedor se modifica (tras la inserción / eliminación).

    Cuando el Estándar dice que los elementos están ordenados de alguna manera, significa que:

    • al iterar, verá los elementos en el orden definido
    • al iterar en reversa, ves los elementos en el orden opuesto

    Espero que esto aclare cualquier confusión.

    ¿Está garantizado que esto imprima 234 o su implementación está definida?

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

    Me gustaría ir a iterar a través de todos los elementos, con la clave, mayor que un valor int concreto.

    Eso es seguramente posible.

    Sí … los elementos en un std::map tienen un orden débil estricto, lo que significa que los elementos estarán compuestos de un conjunto (es decir, no habrá repeticiones de claves que sean “iguales”), y se determine la igualdad probando en cualquiera de las dos teclas A y B, que si la clave A no es menor que la clave B, y B no es menor que A, entonces la clave A es igual a la clave B.

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