Ordenar std:: mapa usando valor

Necesitaba algo similar, pero el mapa volteado no funcionaría para mí. Simplemente copié mi mapa (freq a continuación) en un vector de pares, luego ordené los pares sin embargo quería.

std::vector<std::pair<int, int>> pairs;
for (auto itr = freq.begin(); itr != freq.end(); ++itr)
    pairs.push_back(*itr);

sort(pairs.begin(), pairs.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b)
{
    return a.second < b.second;
}
);

Si desea presentar los valores en un mapa en orden ordenado, copie los valores del mapa al vector y ordene el vector.

Me gusta la respuesta de Oli (voltear un mapa), pero parece que tiene un problema: el mapa contenedor no permite dos elementos con la misma clave.

Una solución es hacer que dst sea el tipo multimap. Otra es volcar src en un vector y ordenar el vector. El primero requiere modificaciones menores a la respuesta de Oli, y el segundo puede implementarse usando STL copy concisamente

#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  map<int, int> m;
  m[11] = 1;
  m[22] = 2;
  m[33] = 3;

  vector<pair<int, int> > v;
  copy(m.begin(),
       m.end(),
       back_inserter<vector<pair<int, int> > >(v));

  for (size_t i = 0; i < v.size(); ++i) {
    cout << v[i].first << " , " << v[i].second << "\n";
  }

  return 0;
};

No puede ordenar a std::map de esta manera, porque a las entradas en el mapa están ordenadas por la clave. Si desea ordenar por valor, debe crear un nuevo std::map con la clave y el valor intercambiados.

map<long, double> testMap;
map<double, long> testMap2;

// Insert values from testMap to testMap2
// The values in testMap2 are sorted by the double value

Recuerde que las teclas dobles deben ser únicas en testMap2 o usar std::multimap.

Para construir sobre la solución de Oli ( https://stackoverflow.com/a/5056797/2472351 ) usando multimaps, puede reemplazar las dos funciones de plantilla que usó con las siguientes:

template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {

    multimap<B,A> dst;

    for(map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));

    return dst;
}

Aquí hay un programa de ejemplo que muestra todos los pares clave-valor que se conservan después de realizar el flip.

#include <iostream>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {

    multimap<B,A> dst;

    for(typename map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));

    return dst;
}

int main() {

    map<string, int> test;
    test["word"] = 1;
    test["spark"] = 15;
    test["the"] = 2;
    test["mail"] = 3;
    test["info"] = 3;
    test["sandwich"] = 15;

    cout << "Contents of original map:\n" << endl;
    for(map<string, int>::const_iterator it = test.begin(); it != test.end(); ++it)
        cout << it -> first << " " << it -> second << endl; 

    multimap<int, string> reverseTest = flip_map(test);

    cout << "\nContents of flipped map in descending order:\n" << endl;
    for(multimap<int, string>::const_reverse_iterator it = reverseTest.rbegin(); it != reverseTest.rend(); ++it)
        cout << it -> first << " " << it -> second << endl; 

    cout << endl;
}

Resultado:

A std::map ordenado por su valor es en esencia a std::set. De lejos, la forma más fácil es copiar todas las entradas en el mapa a un conjunto (tomado y adaptado de aquí)

template <typename M, typename S> 
void MapToSet( const  M & m, S & s )
{
    typename M::const_iterator end = m.end();
    for( typename M::const_iterator it = m.begin(); it != end ; ++it )
    {
        s.insert( it->second );
    }
}

Una advertencia: si el mapa contiene diferentes claves con el mismo valor, no se insertarán en el conjunto y se perderán.

En el siguiente código de ejemplo, escribí una manera simple de generar las palabras principales en un mapa word_map donde la clave es string (word) y el valor es unsigned int (word occurrence).

La idea es simple, encontrar la palabra superior actual y eliminarla del mapa. No está optimizado, pero funciona bien cuando el mapa no es grande y solo necesitamos generar las N palabras superiores, en lugar de ordenar todo el mapa.

const int NUMBER_OF_TOP_WORDS = 300;
for (int i = 1; i <= NUMBER_OF_TOP_WORDS; i++) {
  if (word_map.empty())
    break;
  // Go through the map and find the max item.
  int max_value = 0;
  string max_word = "";
  for (const auto& kv : word_map) {
    if (kv.second > max_value) {
      max_value = kv.second;
      max_word = kv.first;
    }
  }
  // Erase this entry and print.
  word_map.erase(max_word);
  cout << "Top:" << i << " Count:" << max_value << " Word:<" << max_word << ">" <<     endl;
}

La estructura invertida puede no ser ya un mapa sino más bien un multimap, por lo que en el ejemplo flip_map anterior no todos los elementos de B aparecerán necesariamente en la estructura de datos resultante.

Puede considerar usar boost:: bimap que podría darle la sensación de que el mapa está ordenado por clave y por valores simultáneamente (esto no es lo que realmente sucede, sin embargo)