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

Question

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

Por ejemplo, tengo un mapa m:

map<int, int> m; 
m[1] = 10; 
m[2] = 5; 
m[4] = 6; 
m[6] = 1; 

me gustaría para ordenar ese mapa por m 's valor. Por lo tanto, si puedo imprimir 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?

Answer 1

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.

Answer 2

Me pregunto cómo puedo implementar el ordenamiento de mapas STL por valor.

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

Answer 3

Debe usar Boost.Bimap para este tipo de cosas.

Answer 4

volcar todos los pares de valores clave en un set<pair<K, V> > primera, donde el set se construye con un menos-que funtor que compara segundo valor de la pareja solamente. De esta forma, su código aún funciona incluso si sus valores no son todos distintos.

O voltee los pares clave-valor en un vector<pair<K, V> >, luego ordene ese vector con el mismo funcionador menos que después.

Answer 5

Crear otro mapa, proporcionar una función menos() basado en el valor no clave, y la función debe devolver verdadero si el valor 1 < = valor2 (no estrictamente <). En este caso, también se pueden ordenar los elementos con valores no definidos.

Answer 6

Acabo de hacer una pregunta similar en mi libro de C++. La respuesta que se me ocurrió podría no ser muy eficiente, aunque:

int main() 
{ 
    string s; 
    map<string, int> 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<string, int>::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<string, int> 
int smallest_map_value(const map<string, int>& m) 
{ 
    map<string, int>::const_iterator it = m.begin(); 
    int lowest = it->second; 
    for(map<string, int>::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<string, int> 
int largest_map_value(const map<string, int>& m) 
{ 
    map<string, int>::const_iterator it = m.begin(); 
    int highest = it->second; 
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it) 
    { 
     if(it->second > highest) 
      highest = it->second; 
    } 
    return highest; 
} 

Answer 7

Sobre la base de la idea de @ swegi, he implementado una solución en c++11 utilizando un multimap:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}}; 
multimap<int, int> 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. 

Code on 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, que proporcionará una lambda expression como funtor comparación:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}}; 
using mypair = pair<int, int>; 

vector<mypair> 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; 

Code on Ideone

La primera solución es más compacto, pero ambas soluciones debería tener más o menos el mismo rendimiento.Inserción en un multimap es de O (log n), pero esto tiene que ser hecho para n entradas, resultando en 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 no se insertará el segundo par, ya que ambos pares se consideran idénticos por ese conjunto. Puede ver ese efecto here on Ideone.