¿Cómo asegurar que se ordena un std :: map?

Usando un std::map ¿cómo puedo asegurarme de insertar al momento que la iteración sobre él se llevará a cabo en orden ascendente de la clave entera?

No tienes que hacer nada. El mapa estará en orden ascendente según los valores de la clave.

Internamente, el mapa realiza una comparación entre teclas para ordenar sus elementos. Por defecto, usa std::less , que es equivalente a bool operator<(int, int) para enteros. Para los tipos definidos por el usuario, tienes las opciones:

  1. Implemente un bool operator<(const MyType&, const MyType&) implementando una comparación estricta y débil entre sus tipos definidos por el usuario. Use esto si su tipo tiene un orden natural

  2. Proporcione un functor binario que implemente un ordenamiento débil estricto, que pueda pasar como el parámetro de la 3ª plantilla al mapa. Use esto si su tipo no tiene un orden natural, o si desea construir el mapa con un orden diferente al utilizado por std::less través del bool operator<(...) desde el punto 1.

Lo que sucede típicamente detrás de la escena es que el mapa se implementa como un árbol binario de auto equilibrio, y el ordenamiento estricto y débil se usa para colocar nuevos elementos en el mapa y para determinar si dos elementos son iguales. Aparte, la misma lógica se aplica a std::set , donde la clave y el valor son uno y el mismo.

std::map hace eso mismo. No tienes que hacer nada.

Por defecto, ordena las teclas en orden creciente. Si desea que se ordene en orden decreciente, entonces pase std::greater como tercer argumento de plantilla a std::map .

 std::map m1; //sorts key in increasing order std::map> m2; //sorts key in decreasing order std::map> m3; //sorts key in increasing order 

El argumento predeterminado para el tercer parámetro de plantilla es std::less , por lo que, por encima de m1 y m3 son los mismos tipos!

Manifestación:

 #include  #include  #include  int main() { std::cout << "\nkeys are in increasing order: \n"; std::map m1; m1[5] = "first insertion but higher key"; m1[1] = "second insertion but lower key"; for(auto const & item : m1) std::cout << "{" << item.first <<"," << item.second << "}\n"; std::cout << "\nkeys are in decreasing order: \n"; std::map > m2; m2[1] = "first insertion but lower key"; m2[2] = "second insertion but higher key"; for(auto const & item : m2) std::cout << "{" << item.first <<"," << item.second << "}\n"; } 

Salida:

 keys are in increasing order: {1,second insertion but lower key} {5,first insertion but higher key} keys are in decreasing order: {2,second insertion but higher key} {1,first insertion but lower key} 

Tenga en cuenta que en ambos casos los artículos se ordenan según lo especificado por el tercer argumento de plantilla de std::map . La salida no depende del orden de inserción, sino del orden de las teclas.

Demo en vivo

También hay std::unordered_map que no ordena elementos.

map se implementa generalmente como un árbol de búsqueda binario , por lo tanto, los iteradores ya le darán claves ordenadas.

Si no te importa el orden, puedes usar unordered_map (de c ++ 11 o boost) que te dará cierta velocidad en el intercambio de la orden.