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

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

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

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

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

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

78 Eve                                      
99 Bob                                       
78 Alice

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

99 Bob
78 Alice
78 Eve

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

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

#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, Ева)


c++ sorting stl multimap equal-range
person Mohammed Raqeeb    schedule 24.06.2015    source источник
comment
Вам нужно поддерживать поиск по ключу или только операции, описанные выше? Кроме того, существуют ли какие-либо временные рамки того, насколько эффективно вы должны быть в состоянии сделать это?   -  person templatetypedef    schedule 25.06.2015
comment
@templatetypedef Нам нужно искать по ключу ... чем он эффективнее, тем лучше.   -  person Mohammed Raqeeb    schedule 25.06.2015

Ответы (2)


arrow_upward
2
arrow_downward

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

person Gabe Sechan    schedule 24.06.2015
comment
это, вероятно, проще всего, но мультикарта с пользовательским сравнением тоже подойдет... - person mark; 25.06.2015
comment
Нет, не будет. Функция сравнения просто передает два ключа для сравнения, а не ключи и значения. Если вы предлагаете сравнить, посмотрите значения - ewww, это было бы ужасной производительностью. Или в зависимости от реализации бесконечная рекурсия и стек. - person Gabe Sechan; 25.06.2015
comment
ну, я предложил что-то более хакерское, я полагаю... вдоль строк пользовательского сравнения можно получить доступ к самим данным для обоих компонентов. я уверен, что это выходит за рамки учебного упражнения... - person mark; 25.06.2015
comment
@GabeSechan Я изменил свой код, чтобы использовать подход map‹int, set‹string› ›. Кажется, теперь все в порядке. Спасибо! - person Mohammed Raqeeb; 25.06.2015

arrow_upward
1
arrow_downward

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

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;
person Ross Smith    schedule 24.06.2015
comment
хотя это не позволяет использовать неуникальные ключи... подождите, почему мультикарта не работает с пользовательским сравнением? сравнение должно указывать на что-то, что содержит оба аспекта, это все... - person mark; 25.06.2015
comment
Это позволяет использовать неуникальные ключи. Он не позволяет использовать неуникальные пары ключ-значение, но если вы хотите, просто используйте мультимножество вместо набора. Вы не можете дать мультикарте сравнение, которое рассматривает как ключ, так и значение, оно не будет компилироваться. - person Ross Smith; 25.06.2015
comment
Для меня большая проблема заключается в том, что если вам нужно проверить, есть ли какое-либо значение для данного ключа, вы не можете этого сделать. Вы можете только проверить, находится ли данная пара в структуре данных. - person Gabe Sechan; 25.06.2015