¿Cómo puedo ordenar un mapa STL por valor?

¿Cómo puedo implementar la clasificación de mapas STL por valor?

Por ejemplo, tengo un mapa m :

 map m; m[1] = 10; m[2] = 5; m[4] = 6; m[6] = 1; 

Me gustaría ordenar ese mapa por el valor de m . Entonces, si imprimo el mapa, me gustaría obtener el resultado de la siguiente manera:

 m[6] = 1 m[2] = 5 m[4] = 6 m[1] = 10 

¿Cómo puedo ordenar el mapa de esta manera? ¿Hay alguna forma de que pueda manejar la clave y el valor con los valores ordenados?

Puede construir un segundo mapa, con los valores del primer mapa como claves y las claves del primer mapa como valores.

Esto funciona solo si todos los valores son distintos. Si no puedes asumir esto, entonces necesitas construir un multimap en lugar de un mapa.

Deseche todos los pares clave-valor en un set > primero, donde el set se construye con un functor menor que solo el segundo valor del par. De esta forma, su código aún funciona incluso si sus valores no son todos distintos.

O vierta los pares clave-valor en un vector > , luego clasifique ese vector con el mismo funcionador menos que luego.

Me pregunto cómo puedo implementar el mapa STL clasificando por valor.

No puedes, por definición . Un mapa es una estructura de datos que ordena su elemento por clave.

Deberías usar Boost.Bimap para este tipo de cosas.

Acabo de hacer una pregunta similar en mi libro de c ++. La respuesta que surgió podría no ser muy eficiente:

 int main() { string s; map counters; while(cin >> s) ++counters[s]; //Get the largest and smallest values from map int beginPos = smallest_map_value(counters); int endPos = largest_map_value(counters); //Increment through smallest value to largest values found for(int i = beginPos; i <= endPos; ++i) { //For each increment, go through the map... for(map::const_iterator it = counters.begin(); it != counters.end(); ++it) { //...and print out any pairs with matching values if(it->second == i) { cout << it->first << "\t" << it->second << endl; } } } return 0; } //Find the smallest value for a map int smallest_map_value(const map& m) { map::const_iterator it = m.begin(); int lowest = it->second; for(map::const_iterator it = m.begin(); it != m.end(); ++it) { if(it->second < lowest) lowest = it->second; } return lowest; } //Find the largest value for a map int largest_map_value(const map& m) { map::const_iterator it = m.begin(); int highest = it->second; for(map::const_iterator it = m.begin(); it != m.end(); ++it) { if(it->second > highest) highest = it->second; } return highest; } 

Cree otro mapa, proporcione una función less () basada en la clave value not AND, y la función debería devolver true si value1 <= value2 (no estrictamente <). En este caso, también se pueden ordenar los elementos con valores no definidos.

Basado en la idea de @ swegi, implementé una solución en c ++ 11 usando un multimap :

 map m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}}; multimap mm; for(auto const &kv : m) mm.insert(make_pair(kv.second, kv.first)); // Flip the pairs. for(auto const &kv : mm) cout << "m[" << kv.second << "] = " << kv.first << endl; // Flip the pairs again. 

Código en Ideone

También implementé una solución C ++ 11 basada en la idea de @Chris usando un vector de pares. Para la clasificación correcta, proporciono una expresión lambda como functor de comparación:

 map m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}}; using mypair = pair; vector v(begin(m), end(m)); sort(begin(v), end(v), [](const mypair& a, const mypair& b) { return a.second < b.second; }); for(auto const &p : v) cout << "m[" << p.first << "] = " << p.second << endl; 

Código en Ideone

La primera solución es más compacta, pero ambas soluciones deberían tener aproximadamente el mismo rendimiento. La inserción en un multimap es de O (log n) , pero esto tiene que hacerse para n entradas, lo que da como resultado O (n log n) . La clasificación del vector en la segunda solución también da como resultado O (n log n) .

También probé la idea de @Chris de utilizar un conjunto de pares. Sin embargo, no funcionará si los valores no son todos distintos. Usar un functor que compara solo el segundo elemento de la pareja no ayuda. Si inserta primero make_pair(1, 1) en el conjunto y luego intenta insertar make_pair(2, 1) , entonces el segundo par no se insertará, ya que ambos pares se consideran idénticos en ese conjunto. Puedes ver ese efecto aquí en Ideone .