Мне нужно отсортировать std::map по значению, а не по ключу. Есть ли простой способ сделать это?
Я получил одно решение из следующей ветки:
std :: map сортировать по данным?
Есть ли лучшее решение?
map<long, double> testMap;
// some code to generate the values in the map.
sort(testMap.begin(), testMap.end()); // is there any function like this to sort the map?
Несмотря на то, что правильные ответы уже были опубликованы, я подумал, что добавлю демонстрацию того, как вы можете сделать это чисто:
template<typename A, typename B>
std::pair<B,A> flip_pair(const std::pair<A,B> &p)
{
return std::pair<B,A>(p.second, p.first);
}
template<typename A, typename B>
std::multimap<B,A> flip_map(const std::map<A,B> &src)
{
std::multimap<B,A> dst;
std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()),
flip_pair<A,B>);
return dst;
}
int main(void)
{
std::map<int, double> src;
...
std::multimap<double, int> dst = flip_map(src);
// dst is now sorted by what used to be the value in src!
}
Generic Associative Source (требуется С++ 11)
Если вы используете альтернативный вариант std::map для исходного ассоциативного контейнера (например, std::unordered_map), вы можете закодировать отдельную перегрузку, но в конце действие все равно будет таким же, поэтому обобщенный ассоциативный контейнер использование вариационных шаблонов может быть использовано для любой конструкции отображения:
// flips an associative container of A,B pairs to B,A pairs
template<typename A, typename B, template<class,class,class...> class M, class... Args>
std::multimap<B,A> flip_map(const M<A,B,Args...> &src)
{
std::multimap<B,A> dst;
std::transform(src.begin(), src.end(),
std::inserter(dst, dst.begin()),
flip_pair<A,B>);
return dst;
}
Это будет работать как для std::map, так и std::unordered_map в качестве источника флип.
Мне нужно было что-то подобное, но перевернутая карта не сработала бы для меня. Я просто скопировал свою карту (частоту ниже) в вектор пар, а затем отсортировал пары, но я хотел.
std::vector<std::pair<int, int>> pairs;
for (auto itr = freq.begin(); itr != freq.end(); ++itr)
pairs.push_back(*itr);
sort(pairs.begin(), pairs.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b)
{
return a.second < b.second;
}
);
Если вы хотите представить значения на карте в отсортированном порядке, скопируйте значения из карты в вектор и отсортируйте вектор.
Мне нравится ответ от Oli (перелистывание карты), но, похоже, у него есть проблема: карта контейнера не позволяет использовать два элемента с одним и тем же ключом.
Решение состоит в том, чтобы сделать dst типа multimap. Другим является сброс src в вектор и сортировка вектора. Первый требует незначительных изменений в ответе Оли, и последний может быть реализован с использованием STL-копии в сжатом виде
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
map<int, int> m;
m[11] = 1;
m[22] = 2;
m[33] = 3;
vector<pair<int, int> > v;
copy(m.begin(),
m.end(),
back_inserter<vector<pair<int, int> > >(v));
for (size_t i = 0; i < v.size(); ++i) {
cout << v[i].first << " , " << v[i].second << "\n";
}
return 0;
};
Вы не можете сортировать std::map таким образом, потому что записи на карте сортируются по ключу. Если вы хотите сортировать по значению, вам нужно создать новый std::map с измененным ключом и значением.
map<long, double> testMap;
map<double, long> testMap2;
// Insert values from testMap to testMap2
// The values in testMap2 are sorted by the double value
Помните, что двойные ключи должны быть уникальными в testMap2 или использовать std::multimap.
Чтобы построить решение Oli (fooobar.com/questions/149994/...) с использованием мультикарт, вы можете заменить две функции шаблона, которые он использовал, следующими:
template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {
multimap<B,A> dst;
for(map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
dst.insert(pair<B, A>(it -> second, it -> first));
return dst;
}
Вот пример программы, которая показывает все пары ключ-значение, сохраняемые после выполнения переворота.
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {
multimap<B,A> dst;
for(typename map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
dst.insert(pair<B, A>(it -> second, it -> first));
return dst;
}
int main() {
map<string, int> test;
test["word"] = 1;
test["spark"] = 15;
test["the"] = 2;
test["mail"] = 3;
test["info"] = 3;
test["sandwich"] = 15;
cout << "Contents of original map:\n" << endl;
for(map<string, int>::const_iterator it = test.begin(); it != test.end(); ++it)
cout << it -> first << " " << it -> second << endl;
multimap<int, string> reverseTest = flip_map(test);
cout << "\nContents of flipped map in descending order:\n" << endl;
for(multimap<int, string>::const_reverse_iterator it = reverseTest.rbegin(); it != reverseTest.rend(); ++it)
cout << it -> first << " " << it -> second << endl;
cout << endl;
}
Результат:
A std::map, отсортированное по его значению, по существу, является std::set. Самый простой способ - скопировать все записи на карте в набор (взятый и адаптированный из здесь)
template <typename M, typename S>
void MapToSet( const M & m, S & s )
{
typename M::const_iterator end = m.end();
for( typename M::const_iterator it = m.begin(); it != end ; ++it )
{
s.insert( it->second );
}
}
Одно предупреждение: если карта содержит разные клавиши с одинаковым значением, они не будут вставлены в набор и будут потеряны.
В следующем примере кода я написал простой способ вывода верхних слов в карту word_map, где ключ - это строка (слово), а значение - без знака int (вхождение слова).
Идея проста, найдите текущее верхнее слово и удалите его с карты. Он не оптимизирован, но он хорошо работает, когда карта невелика, и нам нужно только выводить верхние N слов, а не сортировать всю карту.
const int NUMBER_OF_TOP_WORDS = 300;
for (int i = 1; i <= NUMBER_OF_TOP_WORDS; i++) {
if (word_map.empty())
break;
// Go through the map and find the max item.
int max_value = 0;
string max_word = "";
for (const auto& kv : word_map) {
if (kv.second > max_value) {
max_value = kv.second;
max_word = kv.first;
}
}
// Erase this entry and print.
word_map.erase(max_word);
cout << "Top:" << i << " Count:" << max_value << " Word:<" << max_word << ">" << endl;
}
Перевернутая структура больше не может быть картой, а скорее мультимапом, поэтому в приведенном выше примере flip_map не все элементы из B обязательно появятся в результирующей структуре данных.
U может рассмотреть возможность использования boost:: bimap, который может дать вам ощущение, что карта сортируется по ключевым словам и по значениям одновременно (это не то, что действительно происходит).
В этом контексте мы должны преобразовать карту в мультикарту. Я думаю, что преобразование карты в набор не очень хорошо, потому что мы потеряем много информации, если в исходной карте будет много повторяющихся значений. Вот мое решение, я определил менее чем компаратор, который сортирует по значению (функция cmp). Мы можем настроить функцию cmp как наше требование.
std::map<int, double> testMap = { {1,9.1}, {2, 8.0}, {3, 7.0}, {4,10.5} };
auto cmp = [](const double &lhs,
const double &rhs)->bool
{
return lhs < rhs;
};
std::multimap<double, int, decltype(cmp)> mmap(cmp);
for (auto item : testMap)
mmap.insert(make_pair(item.second, item.first));
Другим решением было бы использование std :: make_move_iterator для создания нового вектора (С++ 11)
int main(){
std::map<std::string, int> map;
//Populate map
std::vector<std::pair<std::string, int>> v {std::make_move_iterator(begin(map)),
std::make_move_iterator(end(map))};
// Create a vector with the map parameters
sort(begin(v), end(v),
[](auto p1, auto p2){return p1.second > p2.second;});
// Using sort + lambda function to return an ordered vector
// in respect to the int value that is now the 2nd parameter
// of our newly created vector v
}