Как упорядочить элементы карты, используя ее значения, если ключи одинаковые?
У меня есть ситуация, когда я должен хранить оценки некоторых студентов в порядке убывания. Так создали map<marks,string>, Поскольку карта хранит данные в виде кучи, всегда наивысшая оценка будет сверху. Но проблема возникает, когда у меня одинаковые оценки для двух учеников, и я должен затем оценить их по имени (алфавитный порядок с учетом первой буквы их имени).
Что я сделал: На этот раз я разделил метки и имена на другую карту с ключом в качестве имени и меткой в качестве значения. А затем распечатал новую карту в обратном порядке. А затем продолжил с того места, где я оставил старую карту. Но это требует создания дополнительной карты и требует большой обработки.
Мой вопрос Есть лучший способ сделать это?
Решение
Вы могли бы создать map<marks, list<string> > или что-то подобное, чтобы хранить все имена для одной марки там. Списки идут с sort метод, так что вы можете отсортировать все списки, которые имеют более одной записи.
Если вы вставите их все одновременно, вы можете
-
создать список, если ключа нет
-
добавить название в список отметок
-
перебрать все ключи
-
отсортировать значение, если оно больше 1
-
Распечатать.
-
Другие решения
Я хотел бы иметь такую карту:
map<marks, vector<string>>
Таким образом, каждый знак связан с отсортированный массив студентов. Каждый раз, когда вы хотите вставить нового ученика в вектор, вам просто нужно найти правильный индекс, чтобы сохранить ваш вектор отсортированным (дихотомический поиск — самый быстрый)
Вы также можете использовать list<string> вместо vector
Вы можете просто использовать set<pair<mark, string>/*optional appropriate-comparator*/>, Сначала будут сортироваться по меткам, а затем по именам.
Это все еще будет O(log n) для сортированной вставки в отличие от отсортированного векторного решения
В основном вам нужна карта, которая может хранить дубликаты ключей (int) в не возрастающем порядке и значения (строки) в не убывающем порядке.
У меня есть ситуация, когда я должен хранить оценки некоторых студентов в порядке убывания.
использование std::greater так что ключи будут храниться в нисходящий порядок:
std::map<int, string, std::greater<int> > m;
Но проблема возникает, когда у меня одинаковая оценка для двух студентов.
использование Multimap вместо карты. Мультикартовые магазины дублировать ключи и это его специальность.
std::multimap<int, string, std::greater<int> > m;
Затем я должен оценить их на основе их имени (в алфавитном порядке с учетом первой буквы их имени).
Сохранение значения идентичных ключей на карте в векторе> сортировка вектора> вставка отсортированного вектора обратно в карту.
Обратите внимание, что внутри мультикарты вам не нужно беспокоиться об изменении ключей или их порядка. Значения являются единственными, чей порядок будет изменен (это тоже только в пределах ключа с одинаковым значением).
multimap<int, string, greater<int> >:: iterator it = m.begin(), st; //Stores duplicate keys(marks).
vector<string> vec;
int lastKey = INT_MAX;
while(it != m.end())
{
if(it->first < lastKey)
{
//Sort the Names
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++){
st->second = vec[i];
st++;
}
st = it;
vec.clear();
}
vec.push_back(it->second); //Insert name
lastKey = it->first; //marks of last inserted name.
it++;
}
//Do same for the last(lowest valued key in map) key.
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++){
st->second = vec[i];
st++;
}