使用值对std :: map进行排序

Question

我需要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?

Answer 1

即使已经发布了正确的答案,我想我会添加一个如何干净利落地演示的演示:

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::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翻转的来源.

Answer 2

我需要类似的东西,但翻转的地图对我不起作用.我只是将我的地图(下面的频率)复制到一对矢量中,然后对我想要的那些对进行排序.

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

Answer 3

如果要按排序顺序在地图中显示值,请将地图中的值复制到矢量并对矢量进行排序.

Answer 4

我喜欢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;
};

Answer 5

您不能以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。

Answer 6

要使用 multimaps构建 Oli 的解决方案 ( /sf/answers/353975821/ )，您可以将他使用的两个模板函数替换为以下内容：

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

结果：