Como posso classificar um mapa STL por valor?

Como posso implementar a sorting de mapas STL por valor?

Por exemplo, eu tenho um mapa m :

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

Eu gostaria de classificar esse mapa pelo valor de m . Então, se eu imprimir o mapa, gostaria de obter o resultado da seguinte forma:

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

Como posso classificar o mapa dessa maneira? Existe alguma maneira que eu possa lidar com a chave e valor com valores classificados?

Você pode criar um segundo mapa, com os valores do primeiro mapa como chaves e as chaves do primeiro mapa como valores.

Isso funciona apenas se todos os valores forem distintos. Se você não pode assumir isso, então você precisa construir um multimap em vez de um mapa.

Despeje todos os pares de valores-chave em um set > primeiro, onde o set é construído com um funtor menor que compara o segundo valor do par. Dessa forma, seu código ainda funciona mesmo que seus valores não sejam todos distintos.

Ou despeje os pares de valores-chave em um vector > , em seguida, classifique esse vetor com o mesmo menor que o functor.

Gostaria de saber como posso implementar a sorting do mapa STL por valor.

Você não pode, por definição . Um mapa é uma estrutura de dados que classifica seu elemento por chave.

Você deve usar o Boost.Bimap para esse tipo de coisa.

Acabei de fazer uma pergunta semelhante no meu livro em c ++. A resposta que eu tirei pode não ser muito eficiente:

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

Crie outro mapa, forneça uma function less () com base no valor não chave, E a function deve retornar true se o valor1 <= valor2 (não estritamente <). Nesse caso, elementos com valores não distintos também podem ser classificados.

Com base na ideia do @ swegi, implementei uma solução em c ++ 11 usando um multimap :

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

Código no Idéia

Eu também implementei uma solução C ++ 11 baseada na idéia do @Chris usando um vetor de pares. Para ordenação correta, eu forneço uma expressão lambda como function de comparação:

 map m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}}; using mypair = pair; vector 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; 

Código no Idéia

A primeira solução é mais compacta, mas ambas as soluções devem ter aproximadamente o mesmo desempenho. A inserção em um multimap é de O (log n) , mas isso deve ser feito para n inputs, resultando em O (n log n) . Classificar o vetor na segunda solução também resulta em O (n log n) .

Eu também tentei a ideia do @Chris em usar um conjunto de pares. No entanto, não funcionará se os valores não forem todos distintos. Usar um functor que compara apenas o segundo elemento do par não ajuda. Se você inserir primeiro make_pair(1, 1) no conjunto e, em seguida, tentar inserir make_pair(2, 1) , o segundo par não será inserido, porque ambos os pares são vistos como idênticos por esse conjunto. Você pode ver esse efeito aqui no Ideone .