Ordenando std::map usando valor

8 minutos de lectura

Ordenando stdmap usando valor
usuario619237

necesito ordenar un std::map por valor en lugar de por clave. ¿Hay una manera fácil de hacerlo?

Obtuve una solución del siguiente hilo:
std::map ordenar por datos?
¿Hay una solución mejor?

map<long, double> testMap;
// some code to generate the values in the map.

sort(testMap.begin(), testMap.end());  // is there any function like this to sort the map?

  • ¿Por qué necesita el mapa ordenado de esa manera? ¿Está tratando de mejorar el tiempo de búsqueda o desea recorrerlo de cierta manera?

    –Matt Curtis

    20 de febrero de 2011 a las 11:18

  • Puede cambiar la clave con el valor.

    – Pawel Zubrycki

    20 de febrero de 2011 a las 13:17

  • Posible duplicado del mapa STL–> ¿ordenar por valor?

    – Ciro Santilli Путлер Капут 六四事

    1 de enero de 2017 a las 14:20

Ordenando stdmap usando valor
Oliver Charlesworth

Aunque ya se han publicado las respuestas correctas, pensé en agregar una demostración de cómo puede hacer esto limpiamente:

template<typename A, typename B>
std::pair<B,A> flip_pair(const std::pair<A,B> &p)
{
    return std::pair<B,A>(p.second, p.first);
}

template<typename A, typename B>
std::multimap<B,A> flip_map(const std::map<A,B> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()), 
                   flip_pair<A,B>);
    return dst;
}

int main(void)
{
    std::map<int, double> src;

    ...    

    std::multimap<double, int> dst = flip_map(src);
    // dst is now sorted by what used to be the value in src!
}

Fuente asociativa genérica (requiere C++11)

Si está utilizando una alternativa a std::map para el contenedor asociativo de origen (como std::unordered_map), podría codificar una sobrecarga separada, pero al final la acción sigue siendo la misma, por lo que se puede usar un contenedor asociativo generalizado que usa plantillas variadas para cualquiera construcción de mapeo:

// flips an associative container of A,B pairs to B,A pairs
template<typename A, typename B, template<class,class,class...> class M, class... Args>
std::multimap<B,A> flip_map(const M<A,B,Args...> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(),
                   std::inserter(dst, dst.begin()),
                   flip_pair<A,B>);
    return dst;
}

Esto funcionará para ambos std::map y std::unordered_map como la fuente del flip.

  • gracias por el código de muestra. me ayudó a generalizar la solución. ahora puedo filtrar cualquier mapa fácilmente.

    – usuario619237

    21 de febrero de 2011 a las 20:00

  • +1 para la solución limpia. Sin embargo, sería mejor si el mapa de destino fuera un mapa múltiple, para evitar colisiones con las mismas claves de “valor”.

    – teosema

    10 de abril de 2013 a las 12:27

  • Si varios valores tienen el mismo valor, esta solución no funciona, ya que el mapa invertido no puede tener dos pares con la misma clave. Por un valor único en el mapa original, ¡esta solución funciona!

    –Jim Huang

    5 de noviembre de 2013 a las 6:58

  • editado esto para que el resultado sea un mapa múltiple, como lo sugiere theosem.

    – ecotasa

    24 de abril de 2014 a las 11:02

  • apéndice agregado para incluir soporte para contenedor asociativo genérico en lugar de solo std::map. Buena respuesta, por cierto, Oliver.

    – WhozCraig

    31 mayo 2015 a las 19:39


1646958008 336 Ordenando stdmap usando valor
nielw

Necesitaba algo similar, pero el mapa invertido no funcionaría para mí. Simplemente copié mi mapa (frecuencia a continuación) en un vector de pares, luego clasifiqué los pares como 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;
}
);

  • lo que hace el [=] medio en parte

    – Tanner Summers

    9 de abril de 2016 a las 8:58

  • @TannerSummers Es parte de la expresión lambda. es.cppreference.com/w/cpp/language/lambda

    – NielW

    10 de abril de 2016 a las 3:11

  • Esta es una respuesta maravillosa. La función de ordenación se puede hacer aún más modular pasando un objeto Función con la sobrecarga de operator() adecuada para la lógica de ordenación deseada. Sin embargo, buen uso de la lógica lambda.

    – h0r53

    19 mayo 2016 a las 18:58

  • Estoy usando este código, compila bien en gcc 4.9.x, pero no compila en 4.8.x; sin embargo, especificando const frente a ambos argumentos de la lambda lo arregla. ¿Podría ser un error de gcc 4.8.x, o hicieron que gcc 4.9.x fuera más permisivo de lo que requiere el estándar?

    -Keiji

    14 de junio de 2016 a las 8:46

  • @Keiji Buena pregunta. Se agregó compatibilidad con Lambda en C++ 0x (ahora 11). Si agrega el indicador C++ 11, debería funcionar. stackoverflow.com/questions/16886591/how-do-i-enable-c11-in-gcc

    – NielW

    15 de junio de 2016 a las 16:57

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

  • +1: Esta (o variantes de la misma, como crear un mapa “inverso”) es la respuesta correcta.

    –Oliver Charlesworth

    20 de febrero de 2011 a las 11:25

  • si hago esto entonces pierdo la relación entre la clave y los valores. digamos, tengo map id2Score. contiene toda la identificación (donde la identificación no es 0..n, puede ser como 1, 5, 13, etc.) y la puntuación. entonces, si creo un vector con puntaje y ordeno, perderé la información sobre qué identificación está asociada con qué puntaje.

    – usuario619237

    21 de febrero de 2011 a las 19:58

  • @ user619237: no realmente. Puede ordenar el vector. Obtenga el valor máximo o mínimo o cualquier valor que necesite. Luego interactúe a través del mapa original y busque una coincidencia con ese valor en los valores del mapa (“it->second” ).

    – hacknrock

    6 de septiembre de 2013 a las 7:32

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 del tipo multimapa. Otro es volcar src en un vector y ordenar el vector. El primero requiere modificaciones menores a la respuesta de Oli, y el último se puede implementar utilizando la copia STL de manera concisa.

#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;
};

Ordenando stdmap usando valor
ericgrosse

Para construir sobre la solución de Oli (https://stackoverflow.com/a/5056797/2472351) usando mapas múltiples, puede reemplazar las dos funciones de plantilla que usó con lo siguiente:

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 cambio.

#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:

ingrese la descripción de la imagen aquí

  • Solución portátil: también funciona con vs’s anteriores. También huella digital más pequeña en código.

    – TarmoPikaro

    24/01/2016 a las 21:50

No puedes ordenar un std::map de esta manera, porque las entradas en el mapa están ordenadas por clave. Si desea ordenar por valor, debe crear una nueva std::map con clave y 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 claves dobles deben ser únicas en testMap2 o usar std::multimap.

  • Solución portátil: también funciona con vs’s anteriores. También huella digital más pequeña en código.

    – TarmoPikaro

    24/01/2016 a las 21:50

1646958010 799 Ordenando stdmap usando valor
Comunidad

A std::map ordenados por su valor es en esencia un std::set. Con mucho, 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.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad