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

158

Lo que quiero decir es que sabemos que los std::mapelementos están ordenados según las claves. Entonces, digamos que las claves son enteros. Si iterate de std::map::begin()que std::map::end()el uso de un for, hace la garantía estándar que voy a iterar por consiguiente, a través de los elementos con claves, 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;
}

¿Se garantiza que se imprima 234o se define su implementación?


Razón de la vida real: tengo una std::mapcon intllaves. En situaciones muy raras, me gustaría recorrer todos los elementos, con clave, mayor que un intvalor concreto . Sí, parece std::vectorque sería la mejor opción, pero observe mis "situaciones muy raras".


EDITAR : Sé que los elementos de std::mapestá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.

Kiril Kirov
fuente
66
En caso de que no lo supieras: en tu vida real puedes usar map::upper_boundpara encontrar el punto para comenzar a iterar.
Steve Jessop
Sé esto y sé el lugar exacto donde comenzaría a iterar. Solo me pregunté si el pedido está garantizado.
Kiril Kirov el
Un vector disperso no sería sensato si sus claves (índices numéricos) varían enormemente en todos los ámbitos. Estoy usando una solución similar para la cual el índice numérico representa una coordenada y cartesiana en un espacio tridimensional. Usar un vector en este escenario aumentaría mi huella de memoria en gigabytes. Así que no creo que el vector sea una panacea aquí, ni mucho menos.
Jonathan Neufeld
No entiendo la pregunta, y explicaré por qué a través de un experimento mental. Si ya sabe que los elementos están ordenados, ¿cómo podría no ser la iteración? ¿Qué significa incluso ordenar, si no se aplica a la iteración? ¿Qué otros casos hay donde el orden importa, es detectable, etc.? (La respuesta fue dada por Konstantin .)
underscore_d

Respuestas:

176

Si, eso está garantizado. Por otra parte, *begin()le da el más pequeño y *rbegin()el elemento más grande, según lo determinado por el operador de comparación, y dos valores clave ay bpara los que 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 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 iguales (según la regla anterior) y para realizar una búsqueda eficiente (esencialmente un binario búsqueda, que tiene complejidad logarítmica en el número de elementos).

Kerrek SB
fuente
std :: map se implementa utilizando árboles binarios, por lo que técnicamente no se realiza ninguna búsqueda binaria.
jupp0r
11
@ jupp0r: Estructurar un rango como un árbol de búsqueda binario es un método particular para implementar la búsqueda binaria a través del rango. La "búsqueda binaria" es un concepto abstracto más que una implementación particular. No importa si salta los desplazamientos a una matriz o sigue los nodos de enlace; esas son solo formas específicas de "dividir el rango".
Kerrek SB
1
Sé que esta es una publicación antigua, pero para ser claros, la "búsqueda eficiente" es relativa. Técnicamente std::unordered_maptiene un tiempo de búsqueda más eficiente de O (1). La ventaja de std::mapestá en el orden de las claves, pero no en la búsqueda.
Adam Johnston
42

Esto está garantizado por los requisitos de contenedor asociativo en el estándar C ++. Por ejemplo, ver 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 claves donde
no descendente se define por la comparación que se utilizó para construirlos.
Para cualquiera de los dos iteradores desreferenciables i y j tal que la distancia de i a j
positivo,
  value_comp (* j, * i) == falso

y 23.2.4 / 11

Para contenedores asociativos con claves únicas, la condición más fuerte es
  value_comp (* i, * j)! = falso.
Konstantin Oznobihin
fuente
32

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

En la mayoría de los idiomas, a mapes simplemente un Contenedor Asociativo: asigna una clave a un valor. En los idiomas "más nuevos", esto generalmente se logra utilizando un mapa hash, por lo que no se garantiza ningún orden.

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

  • std::mapes un contenedor asociativo ordenado
  • std::unordered_map es un contenedor asociativo basado en tablas hash introducido en C ++ 11

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

En C ++ 03:

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

En C ++ 11:

  • std::set, std::multiset, std::mapY std::multimapestán garantizados para ser ordenados de acuerdo a las teclas (y el criterio suministrado)
  • en std::multisety std::multimap, el Estándar impone que los elementos equivalentes (aquellos que comparan iguales) se ordenan de acuerdo con su orden de inserción (primero se inserta primero)
  • std::unordered_*Los contenedores, como su nombre lo indica, no están ordenados. En particular, el orden de los elementos puede cambiar cuando se modifica el contenedor (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
  • cuando itera en reversa, ve los elementos en el orden opuesto

Espero que esto aclare cualquier confusión.

Matthieu M.
fuente
Esto no tiene nada que ver con mi pregunta, lo siento :) Sé cuáles están ordenados y cuáles no. Y estoy pidiendo el orden cuando estoy iterando a través de los elementos.
Kiril Kirov el
10
@KirilKirov: bueno, la definición de un contenedor asociativo ordenado es que al iterar a través de él, los elementos se ordenan.
Matthieu M.
Bueno, supongo que tienes razón, pero no lo sabía y eso es exactamente lo que estaba preguntando :)
Kiril Kirov
4

¿Se garantiza que esto imprima 234 o su implementación definida?

Sí, std::mapes un contenedor ordenado, ordenado por el Keycon el suministrado Comparator. Entonces está garantizado.

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

Eso seguramente es posible.

jpalecek
fuente
3

Sí ... los elementos en un std::maptienen 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 la igualdad se determina mediante la prueba en cualquier dos teclas A y B, que si la tecla A no es menor que la tecla B y B no es menor que A, entonces la tecla A es igual a la tecla B.

Dicho esto, no puede ordenar adecuadamente los elementos de a std::mapsi el orden débil para ese tipo es ambiguo (en su caso, donde está utilizando enteros como tipo de clave, 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 una propiedad donde A puede no ser comparable a B. Lo que sucederá normalmente en este escenario es que podrá insertar los pares clave / valor, pero puede terminar con pares clave / valor duplicados si recorre todo el mapa y / o detecta "falta" pares clave / valor cuando intenta realizar un std::map::find()par de clave / valor específico en el mapa.

Jason
fuente
Como las otras respuestas, esto en realidad no responde a mi pregunta, gracias de todos modos.
Kiril Kirov
-3

begin () puede dar el elemento más pequeño. Pero su implementación dependía. ¿Se especifica en el estándar C ++? Si no, entonces es peligroso hacer esta suposición.

Pyang
fuente