ejemplo - set c++

¿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 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<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;
}

¿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.

Answer 1

¿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.

Answer 2

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.

Answer 3

Esto está garantizado por los requisitos de contenedor asociativo en el estándar C ++. Ej. Vea 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.

Answer 4

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.

Answer 5

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<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 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).