Come posso ordinare una mappa STL in base al valore?

Question

Come posso implementare l'ordinamento della mappa STL in base al valore?

Ad esempio, ho una mappa m:

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

mi piacerebbe ordinare quella mappa per valore m s'. Quindi, se stampare la mappa, mi piacerebbe ottenere il risultato come segue:

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

Come posso ordinare la mappa in questo modo? C'è un modo in cui posso gestire la chiave e il valore con valori ordinati?

Answer 1

È possibile creare una seconda mappa, con i valori della prima mappa come chiavi e le chiavi della prima mappa come valori.

Questo funziona solo se tutti i valori sono distinti. Se non puoi assumere questo, allora hai bisogno di costruire un multimap invece di una mappa.

Answer 2

Mi chiedo come è possibile implementare l'ordinamento della mappa STL in base al valore.

Non è possibile, per definizione. Una mappa è una struttura dati che ordina il suo elemento per chiave.

Answer 3

È necessario utilizzare Boost.Bimap per questo genere di cose.

Answer 4

Escludere prima tutte le coppie chiave-valore in set<pair<K, V> >, dove il set è costruito con un functor minore che confronta solo il secondo valore della coppia. In questo modo, il tuo codice funziona ancora anche se i tuoi valori non sono tutti distinti.

Oppure scaricare le coppie chiave-valore in un vector<pair<K, V> >, quindi ordinare quel vettore con lo stesso minore in seguito.

Answer 5

Creare un'altra mappa, fornire una funzione meno() in base al valore non chiave, e la funzione deve restituire true se la valore1 < = value2 (non strettamente <). In questo caso, anche gli elementi con valori non distinti possono essere ordinati.

Answer 6

Ho appena fatto una domanda simile nel mio libro C++. La risposta mi è venuta potrebbe non essere molto efficiente, anche se:

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

Sulla base di un'idea di @ swegi, ho implementato una soluzione in c++11 utilizzando 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

anche io implementato una soluzione C++ 11 basata sull'idea di @Chris utilizzando un vettore di coppie. Per il corretto smistamento, ho fornire un lambda expression come confronto functor:

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 prima soluzione è più compatta, ma entrambe le soluzioni devono avere all'incirca le stesse prestazioni.L'inserimento in un multimap è di O (log n), ma questo deve essere fatto per n voci, con conseguente O (n log n). L'ordinamento del vettore nella seconda soluzione comporta inoltre O (n log n).

Ho anche provato l'idea di @Chris sull'utilizzo di un set di coppie. Tuttavia, non funzionerà se i valori non sono tutti distinti. L'uso di un functor che confronta solo il secondo elemento della coppia non aiuta. Se prima inserisci make_pair(1, 1) nel set e poi provi a inserire make_pair(2, 1), la seconda coppia non verrà inserita, poiché entrambe le coppie sono identiche a quella serie. Puoi vedere quell'effetto here on Ideone.