Comment trier une carte STL par valeur ?

Question

Comment puis-je mettre en œuvre le tri par valeur d'une carte STL ?

Par exemple, j'ai une carte m :

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

J'aimerais trier cette carte par m de la valeur de la carte. Ainsi, si j'imprime la carte, j'aimerais obtenir le résultat suivant :

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

Comment puis-je trier la carte de cette manière ? Existe-t-il un moyen de traiter la clé et la valeur avec des valeurs triées ?

Answer 1

Déchargez toutes les paires clé-valeur dans un fichier de type set<pair<K, V> > d'abord, où le set est construit avec un foncteur less-than qui compare uniquement la deuxième valeur de la paire. De cette façon, votre code fonctionne même si vos valeurs ne sont pas toutes distinctes.

Ou vider les paires clé-valeur dans un vector<pair<K, V> > puis trier ce vecteur avec le même foncteur moins que par la suite.

Answer 2

Vous pouvez construire une deuxième carte, avec les valeurs de la première carte comme clés et les clés de la première carte comme valeurs.

Cela ne fonctionne que si toutes les valeurs sont distinctes. Si vous ne pouvez pas le supposer, vous devez alors construire une multimap au lieu d'une map.

Answer 3

Je me demande comment je peux mettre en œuvre le tri par valeur de la carte STL.

Tu ne peux pas, par définition . Une carte est une structure de données qui classe ses éléments par clé.

Answer 4

Vous devez utiliser Boost.Bimap pour ce genre de choses.

Answer 5

Je viens de répondre à une question similaire dans mon livre sur le c++. La réponse que j'ai trouvée n'est peut-être pas très efficace :

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