使用值对 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?
209596 次浏览
小开

如果希望以排序顺序显示映射中的值，那么将值从映射复制到矢量并对矢量进行排序。

小开

您不能以这种方式对 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。

小开

按值排序的 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 );
}
}

注意: 如果 map 包含具有相同值的不同键，则不会将它们插入集合并丢失。

小开

您可以考虑使用 ost: : bimap，它可能会让您感觉到 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!
}

通用关联源(需要 C + + 11)

如果你在源关联容器(比如 std::unordered_map)中使用 std::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作为翻转的来源。

小开

我喜欢 Oli 给出的答案(翻转一个映射) ，但似乎有一个问题: 容器映射不允许两个元素具有相同的键。

一种解决方案是使 dst 类型为 multimap。另一种方法是将 src 转储到向量中并对向量进行排序。前者需要对 Oli 的答案稍作修改，而后者可以使用简洁的 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::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;
}
);
小开

在下面的示例代码中，我编写了一个简单的方法来输出 word _ map 映射中的 top 单词，其中 key 是 string (word) ，value 是 unsignedint (word 匹配)。

这个想法很简单，找到当前的顶部单词，并从地图上删除它。虽然还没有优化，但是在地图不大的情况下，我们只需要输出前 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;
}
小开

翻转结构可能不再是一个映射，而是一个多映射，因此在上面的 lip _ map 示例中，来自 B 的所有元素不一定都会出现在结果数据结构中。

小开

要使用多重映射构建 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;
}

下面是一个示例程序，它显示了在执行翻转之后保留的所有键-值对。

#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;
}

结果:

enter image description here

小开

在这种情况下，我们应该把 map 转换成 multimap。我认为把地图转换成集合是不好的，因为我们会丢失很多信息，以防有很多重复的价值在原来的地图。这是我的解决方案，我定义了小于比较器，按值排序(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 构建一个新的向量(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
}
小开

对 std::map进行排序而不进行任何其他复制或转换的另一种方法是使用不同的 Compare类型重新定义 std::map:

namespace nonstd {
template <class Key,
class T,
class Compare = std::greater<T>,
class Allocator = std::allocator<std::pair<Key const, T>>
>
using map = std::map<Key, T, Compare, Allocator>;
}


int main() {
nonstd::map<char, std::size_t> const values = {
{'A', 3}, {'B', 2}, {'C', 5}
};


for (auto const& value : values) {
std::clog << value.first << " : " << value.second << std::endl;
}
}
小开

只需将值放入矢量中，并根据每个映射键的值对矢量进行排序。

#include <bits/stdc++.h>
using namespace std;


int main()
{


std::map<std::string, int> mymap;
mymap.insert(std::make_pair("earth", 5));
mymap.insert(std::make_pair("moon", 33));
mymap.insert(std::make_pair("sun", 2));


vector<std::pair<std::string, int>> myvector {mymap.begin(), mymap.end()};




sort(myvector.begin(), myvector.end(), [](std::pair<std::string, int> l, std::pair<std::string, int> r)
{
return l.second < r.second;
});
  

return 0;
}

提交答案