How can I print values of a key in sorted order in a multimap

Question

I need to design a data structure that basically stores key-value pairs with key being an integer and its value a string.

Condition 1: There could be multiple values associated with a Key.

Condition 2: I need to print all the keys stored in this map in descending order.

Condition 3: Though the Keys(integers) are printed in Descending order, their corresponding values(strings) must be printed in lexicographic(sorted in ascending) order.

Sample Input:

78 Eve                                      
99 Bob                                       
78 Alice                                    

Expected Output:

99 Bob
78 Alice
78 Eve

Notice the keys are in descending order, while the values are in ascending order.

To do this I have come up with below code in 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;
}

But I am getting output as shown below:

99 Bob
78 Eve 
78 Alice

whereas I need pair(78, Alice) to be printed before (78, Eve)

Answer 1

I wouldn't use multimap. I'd use a map<int, set<string>>. The reason is you need both your keys and values sorted. A multimap is only going to sort the keys. By using a map of sets, the map will sort by keys and the set will sort by values (assuming you give it the right comparator).

Answer 2

If you want to sort key-value pairs by both the key and the value, then you don't want a multimap, which doesn't provide any way to sort on values with the same key. You want a set of pairs, with a custom comparison function that sorts them in the order you want. Something like this (warning, code written off the top of my head, not tested):

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;