std :: map, como classificar por valor e, em seguida, por chave

Eu preciso classificar um mapa por valor e, em seguida, por chave. Eu tenho um mapa com conteúdos como este …

1 realistically 8 really 4 reason 3 reasonable 1 reasonably 1 reassemble 1 reassembled 2 recognize 92 record 48 records 7 recs 

Eu preciso colocar os valores em ordem, mas o kicker é que as chaves precisam estar em ordem alfabética após os valores estarem em ordem. Qual é a melhor maneira de fazer isso?

std::map irá classificar seus elementos por keys . Não se importa com os values ao classificar.

Você pode usar std::vector> depois classificá-lo usando std::sort seguido por std::stable_sort :

 std::vector> items; //fill items //sort by value using std::sort std::sort(items.begin(), items.end(), value_comparer); //sort by key using std::stable_sort std::stable_sort(items.begin(), items.end(), key_comparer); 

A primeira ordenação deve usar std::sort já que é nlog(n) , e então usa std::stable_sort que é n(log(n))^2 no pior caso.

Note que, enquanto std::sort é escolhido por motivo de performance, std::stable_sort é necessário para ordenação correta, já que você deseja que o order-by-value seja preservado.


@gsf anotado no comentário, você poderia usar apenas std::sort se você escolher um comparador que compara os values primeiro, e se eles forem iguais, classifique as keys .

 auto cmp = [](std::pair const & a, std::pair const & b) { return a.second != b.second? a.second < b.second : a.first < b.first; }; std::sort(items.begin(), items.end(), cmp); 

Isso deve ser eficiente.

Mas espere, há uma abordagem melhor: armazene std::pair invés de std::pair e então você não precisa de nenhum comparador - o comparador padrão para std::pair seria suficiente, pois compara first (que é V ) primeiro e depois second que é K :

 std::vector> items; //... std::sort(items.begin(), items.end()); 

Isso deve funcionar muito bem.

Você pode usar std::set vez de std::map .

Você pode armazenar a chave e o valor em std::pair e o tipo de contêiner ficará assim:

 std::set< std::pair > items; 

std::set irá ordenar seus valores por chaves e valores originais que foram armazenados em std::map .

std::map já classifica os valores usando um predicado que você define ou std::less se você não fornecer um. std::set também armazenará itens na ordem de um comparador de definição. No entanto, nem o conjunto nem o mapa permitem que você tenha várias chaves. Eu sugeriria definir um std::map se você quiser realizar isso usando apenas sua estrutura de dados. Você também deve perceber que std::less para string irá ordenar lexicograficamente não alfabeticamente.

EDIT: As outras duas respostas fazem um bom ponto. Eu estou supondo que você quer encomendá-los em alguma outra estrutura, ou para imprimi-los.

“Melhor” pode significar várias coisas diferentes. Você quer dizer “mais fácil”, “mais rápido”, “mais eficiente”, “menos código”, “mais legível?”

A abordagem mais óbvia é percorrer duas vezes. Na primeira passagem, peça os valores:

 if(current_value > examined_value) { current_value = examined_value (and then swap them, however you like) } 

Em seguida, na segunda passagem, coloque em ordem alfabética as palavras, mas apenas se os valores deles corresponderem.

 if(current_value == examined_value) { (alphabetize the two) } 

Estritamente falando, este é um tipo de bolha que é lento, porque toda vez que você faz uma troca, você tem que começar de novo. Um “passe” é concluído quando você passar pela lista inteira sem fazer nenhuma troca.

Existem outros algoritmos de ordenação, mas o princípio seria o mesmo: ordem por valor, depois alfabetizar.