std :: map, cómo ordenar por valor, luego por clave

Necesito ordenar un mapa por valor, luego por clave. Tengo un mapa con contenidos como este …

1 realistically 8 really 4 reason 3 reasonable 1 reasonably 1 reassemble 1 reassembled 2 recognize 92 record 48 records 7 recs 

Necesito poner los valores en orden, pero el truco es que las claves deben estar en orden alfabético después de que los valores estén en orden. ¿Cuál es la mejor manera de hacerlo?

std::map clasificará sus elementos por keys . No le importan los values al ordenar.

Puede usar std::vector> luego ordenarlo usando std::sort seguido de std::stable_sort :

 std::vector> items; //fill items //sort by value using std::sort std::sort(items.begin(), items.end(), value_comparer); //sort by key using std::stable_sort std::stable_sort(items.begin(), items.end(), key_comparer); 

La primera clase debería usar std::sort ya que es nlog(n) , y luego usar std::stable_sort que es n(log(n))^2 en el peor de los casos.

Tenga en cuenta que, si bien std::sort se elige por razones de rendimiento, std::stable_sort es necesario para realizar un pedido correcto, ya que desea conservar el orden por valor.


@gsf anotó en el comentario, puede usar std::sort si elige un comparador que compare primero los values , y SI son iguales, clasifique las keys .

 auto cmp = [](std::pair const & a, std::pair const & b) { return a.second != b.second? a.second < b.second : a.first < b.first; }; std::sort(items.begin(), items.end(), cmp); 

Eso debería ser eficiente.

Pero espere, hay un mejor enfoque: store std::pair lugar de std::pair y luego no necesita ningún comparador - el comparador estándar para std::pair sería suficiente, ya que compara first (que es V ) primero y luego el second que es K :

 std::vector> items; //... std::sort(items.begin(), items.end()); 

Eso debería funcionar bien.

Puede usar std::set lugar de std::map .

Puede almacenar clave y valor en std::pair y el tipo de contenedor se verá así:

 std::set< std::pair > items; 

std::set clasificará sus valores tanto por las claves originales como por los valores almacenados en std::map .

std::map ya ordena los valores usando un predicado que defina o std::less si no proporciona uno. std::set también almacenará elementos en orden de los de un comparador de definición. Sin embargo, ni el conjunto ni el mapa te permiten tener varias claves. Sugeriría definir un std::map si quiere lograr esto usando solo su estructura de datos. También debe tener en cuenta que std::less para string ordenará lexicográficamente no alfabéticamente.

EDITAR: Las otras dos respuestas son un buen punto. Supongo que desea ordenarlos en otra estructura o imprimirlos.

“Lo mejor” puede significar varias cosas diferentes. ¿Quiere decir “más fácil”, “más rápido”, “más eficiente”, “menos código”, “más legible”?

El enfoque más obvio es repetir dos veces. En el primer pase, ordene los valores:

 if(current_value > examined_value) { current_value = examined_value (and then swap them, however you like) } 

Luego, en el segundo pase, alfabetiza las palabras, pero solo si sus valores coinciden.

 if(current_value == examined_value) { (alphabetize the two) } 

Estrictamente hablando, este es un “tipo burbuja” que es lento porque cada vez que realizas un intercambio, debes comenzar de nuevo. Un “pase” finaliza cuando completa toda la lista sin realizar ningún intercambio.

Existen otros algoritmos de clasificación, pero el principio sería el mismo: ordenar por valor, luego alfabetizar.