std :: map, как отсортировать по значению, затем по ключу

Question

Мне нужно отсортировать карту по значению, а затем по ключу. У меня есть карта с содержанием, как это ...

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

Мне нужно получить значение в порядке, но кикер, что ключи должны быть в алфавитном порядке после того, как значения в порядке. Каков наилучший способ сделать это?

Answer 1

std::map будет сортировать свои элементы по keys. При сортировке он не заботится о values.

Вы можете использовать std::vector<std::pair<K,V>> затем отсортировать его с помощью std::sort с последующим std::stable_sort:

std::vector<std::pair<K,V>> 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); 

Первый сорт должен использовать std::sort, так как это nlog(n), а затем использовать std::stable_sort, который находится в самом худшем случае n(log(n))^2.

Обратите внимание, что в то время как std::sort выбран по соображениям удобства, std::stable_sort необходим для правильного заказа, так как вы хотите сохранить заказ по значению.

---

@gsf отметил в комментарии, вы могли бы использовать толькоstd::sort, если вы выбираете компаратор, который сравнивает values первый, и если они равны, сортировать keys.

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

Это должно быть эффективным.

Но подождите, есть лучший подход: магазин std::pair<V,K> вместо std::pair<K,V> и тогда вам не нужно делать компаратор на всех — стандарт Comparer для std::pair будет достаточно, так как он сравнивает first (который V) первый тогда second который K:

std::vector<std::pair<V,K>> items; 
//... 
std::sort(items.begin(), items.end()); 

это должно отлично работать.

Answer 2

std::map уже сортирует значения, используя предикат, который вы определяете, или std::less, если вы его не предоставили. std::set также будет хранить элементы в порядке определения компаратора. Однако ни набор, ни карта не позволяют вам иметь несколько ключей. Я бы предложил определить std::map<int,std::set<string>, если вы хотите выполнить это, используя только свою структуру данных. Вы также должны понимать, что std::less для строки сортирует лексикографически не в алфавитном порядке.

Answer 3

РЕДАКТИРОВАТЬ: Остальные два ответа хорошо подходят. Я предполагаю, что вы хотите заказать их в какую-то другую структуру или распечатать их.

«Лучший» может означать несколько разных вещей. Вы имеете в виду «самый простой», «самый быстрый», «самый эффективный», «наименьший код», «самый читаемый»?

Наиболее очевидным подходом является цикл в два раза.На первом проходе, порядок значения:

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

Затем на втором проходе, в алфавитном порядке слова, но только тогда, когда матч их значения.

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

Строго говоря, это «пузырьковой сортировки», который медленно, потому что каждый раз, когда вы делаете своп, вы должны начать все сначала. Один «проход» завершается, когда вы просматриваете весь список без каких-либо свопов.

Существуют и другие алгоритмы сортировки, но принцип будет таким же: порядок по значению, затем алфавит.

Answer 4

Вы можете использовать std::set вместо std::map.

Вы можете хранить как ключ и значение в std::pair и тип контейнера будет выглядеть следующим образом:

std::set< std::pair<int, std::string> > items; 

std::set сортирует это значения как на оригинальные ключи и значения, которые были сохранены в std::map.