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

Ответ 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>, а затем вам вообще не нужен какой-либо компаратор — стандартного сравнения для std::pair было бы достаточно, так как сначала он сравнивает first (который является V), а затем second, который равен K:

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

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

Ответ 2

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

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

Как объяснено в ответе Наваза, вы не можете сортировать свою карту по мере необходимости, поскольку std::map сортирует свои элементы только на основе ключей. Итак, вам нужен другой контейнер, но если вам нужно придерживаться вашей карты, то вы все равно можете скопировать (временно) его содержимое в другую структуру данных.

Я думаю, лучшим решением является использование std::set хранящий перевернутые пары ключ-значение, как представлено в ks1322 в ответ. std::set отсортирован по умолчанию, и порядок пар точно такой, как вам нужен:

3) Если lhs.first<rhs.first, возвращает true. В противном случае, если rhs.first<lhs.first, возвращает false. В противном случае, если lhs.second<rhs.second, возвращает true. В противном случае возвращает false.

Таким образом, вам не нужен дополнительный шаг сортировки, а полученный код довольно короткий:

std::map<std::string, int> m;  // Your original map.
m["realistically"] = 1;
m["really"]        = 8;
m["reason"]        = 4;
m["reasonable"]    = 3;
m["reasonably"]    = 1;
m["reassemble"]    = 1;
m["reassembled"]   = 1;
m["recognize"]     = 2;
m["record"]        = 92;
m["records"]       = 48;
m["recs"]          = 7;

std::set<std::pair<int, std::string>> s;  // The new (temporary) container.

for (auto const &kv : m)
    s.emplace(kv.second, kv.first);  // Flip the pairs.

for (auto const &vk : s)
    std::cout << std::setw(3) << vk.first << std::setw(15) << vk.second << std::endl;

Выход:

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

Код на Ideone

Примечание. Начиная с С++ 17, вы можете использовать циклический поиск для циклов вместе со структурированными привязками для итерации по карте. В результате код для копирования вашей карты становится еще короче и более читабельным:

for (auto const &[k, v] : m)
    s.emplace(v, k);  // Flip the pairs.