C++ 使用值对 std::map 进行排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5056645/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting std::map using value
提问by user619237
I need to sort an std::mapby value rather than by key. Is there an easy way to do it?
我需要std::map按值而不是按键排序。有没有简单的方法来做到这一点？
I got one solution from the follwing thread:
std::map sort by data?
Is there a better solution?
我从以下线程中得到了一个解决方案：
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?
采纳答案by Oliver Charlesworth
Even though correct answers have already been posted, I thought I'd add a demo of how you can do this cleanly:
尽管已经发布了正确的答案，但我想我会添加一个演示，说明如何干净利落地做到这一点：
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 (requires C++11)
通用关联源（需要 C++11）
If you're using an alternate to std::mapfor the source associative container (such as std::unordered_map), you could code a separate overload, but in the end the action is still the same, so a generalized associative container using variadic templates can be used for eithermapping construct:
如果您使用替代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;
}
This will work for both std::mapand std::unordered_mapas the source of the flip.
这两个工作std::map，并std::unordered_map与倒装的来源。
回答by NielW
I needed something similar, but the flipped map wouldn't work for me. I just copied out my map (freq below) into a vector of pairs, then sorted the pairs however I wanted.
我需要类似的东西，但翻转的地图对我不起作用。我只是将我的地图（下面的频率）复制到一对向量中，然后按照我想要的方式对这些对进行排序。
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;
}
);
回答by Bogatyr
If you want to present the values in a map in sorted order, then copy the values from the map to vector and sort the vector.
如果要按排序顺序显示地图中的值，请将地图中的值复制到向量并对向量进行排序。
回答by cxwangyi
I like the the answer from Oli (flipping a map), but seems it has a problem: the container map does not allow two elements with the same key.
我喜欢 Oli 的答案（翻转地图），但似乎有一个问题：容器地图不允许具有相同键的两个元素。
A solution is to make dst the type multimap. Another one is to dump src into a vector and sort the vector. The former requires minor modifications to Oli's answer, and the latter can be implemented using STL copy concisely
一种解决方案是使 dst 成为 multimap 类型。另一种方法是将 src 转储到向量中并对向量进行排序。前者需要对Oli的回答稍作修改，后者可以简洁地使用STL copy来实现
#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;
};
回答by ericgrosse
To build on Oli's solution (https://stackoverflow.com/a/5056797/2472351) using multimaps, you can replace the two template functions he used with the following:
要使用 multimaps构建 Oli 的解决方案 ( https://stackoverflow.com/a/5056797/2472351)，您可以将他使用的两个模板函数替换为以下内容：
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;
}
Here is an example program that shows all the key-value pairs being preserved after performing the flip.
这是一个示例程序，它显示了执行翻转后保留的所有键值对。
#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;
}
Result:
结果：
回答by Fox32
You can't sort a std::mapthis way, because a the entries in the map are sorted by the key. If you want to sort by value, you need to create a new std::mapwith swapped key and value.
您不能以std::map这种方式对 a 进行排序，因为 a 映射中的条目是按键排序的。如果要按值排序，则需要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
Remember that the double keys need to be unique in testMap2or use std::multimap.
请记住，双键必须是唯一的testMap2或使用std::multimap.
回答by rubenvb
A std::mapsorted by it's value is in essence a std::set. By far the easiest way is to copy all entries in the map to a set (taken and adapted from here)
std::map按其值排序的A本质上是 a 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 );
}
}
One caveat: if the map contains different keys with the same value, they will not be inserted into the set and be lost.
一个警告：如果映射包含具有相同值的不同键，它们将不会被插入到集合中并丢失。
回答by Yan Bussieres
Another solution would be the usage of std::make_move_iterator to build a new vector (C++11 )
另一种解决方案是使用 std::make_move_iterator 来构建一个新向量（C++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
}
回答by Yuri Feldman
Flipped structure might no longer be a map but rather a multimap, thus in the flip_map example above not all elements from B will necessarily appear in the resulting data structure.
翻转结构可能不再是映射而是多映射，因此在上面的 flip_map 示例中，并非来自 B 的所有元素都一定会出现在结果数据结构中。
回答by Yuri Feldman
U can consider using boost::bimap that might gave you a feeling that map is sorted by key and by values simultaneously (this is not what really happens, though)
你可以考虑使用 boost::bimap ，这可能会让你感觉地图同时按键和值排序（但这不是真正发生的事情）
