Мне нужно спроектировать структуру данных, которая в основном хранит пары ключ-значение, где ключ является целым числом, а его значение — строкой.
Условие 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, Ева)
Я бы не использовал мультикарту. Я бы использовал map<int, set<string>>
, Причина в том, что вам нужны ваши ключи и значения отсортированы. Мультикарта только собирается сортировать ключи. Используя карту наборов, карта будет сортироваться по ключам, а набор будет сортироваться по значениям (при условии, что вы дадите ему правильный компаратор).
Если вы хотите отсортировать пары ключ-значение как по ключу, так и по значению, то вам не нужна мультикарта, которая не позволяет сортировать значения по одному и тому же ключу. Вам нужен набор пар с пользовательской функцией сравнения, которая сортирует их в нужном вам порядке. Примерно так (предупреждение, код написан на макушке, не проверено):
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;