Как я могу напечатать значения ключа в отсортированном порядке в мультикарте

Question

Мне нужно спроектировать структуру данных, которая в основном хранит пары ключ-значение, где ключ является целым числом, а его значение - строкой

Условие 1: может быть несколько значений, связанных с ключом.

Условие 2: мне нужно распечатать все ключи, хранящиеся на этой карте, в порядке убывания.

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

Пример ввода:

78 Eve                                      
99 Bob                                       
78 Alice                                    

Ожидаемый результат:

99 Bob
78 Alice
78 Eve

Обратите внимание, что ключи расположены в порядке убывания, а значения - в порядке возрастания.

Для этого я придумал следующий код на C++:

#include <iostream>
#include <map>

using namespace std;

int main()
{
    int N;
    string name;
    int marks;
    multimap<int, string, greater<int>> studMap;
    multimap<int, string, greater<int>>::iterator itBeg, itEnd;
    typedef multimap<int, string, greater<int>>::iterator mapIter;

    cin >> N;   // total no. of key-value pairs input by user

    while (N--)
    {
        cin >> name >> marks;  // pairs of value-key input by user - N times
        studMap.insert(pair<int, string>(marks, name));
    }

    for (itBeg = studMap.begin(); itBeg != studMap.end(); itBeg = itEnd)
    {
        marks = itBeg->first;

        pair<mapIter, mapIter> keyRange = studMap.equal_range(marks);

        for (itEnd = keyRange.first; itEnd != keyRange.second; ++itEnd)
        {
            cout << marks << " " << itEnd->second << endl;
        }
    }  
    return 0;
}

Но я получаю вывод, как показано ниже:

99 Bob
78 Eve 
78 Alice

в то время как мне нужно, чтобы пара (78, Алиса) была напечатана раньше (78, Ева)

Answer 1

Я бы не использовал мультикарту. Я бы использовал map<int, set<string>>, Причина в том, что вам нужны ваши ключи и значения отсортированы. Мультикарта только собирается сортировать ключи. Используя карту наборов, карта будет сортироваться по ключам, а набор будет сортироваться по значениям (при условии, что вы дадите ему правильный компаратор).

Answer 2

Если вы хотите отсортировать пары ключ-значение как по ключу, так и по значению, то вам не нужна мультикарта, которая не позволяет сортировать значения по одному и тому же ключу. Вам нужен набор пар с пользовательской функцией сравнения, которая сортирует их в нужном вам порядке. Примерно так (предупреждение, код написан на макушке, не проверено):

using KeyValue = std::pair<int, std::string>;

struct CompareKeyValue {
    bool operator()(const KeyValue& lhs, const KeyValue& rhs) const {
        if (lhs.first != rhs.first)
            return lhs.first > rhs.first; // Reverse order
        else
            return lhs.second < rhs.second;
    }
};

std::set<KeyValue, CompareKeyValue> my_data;