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

问题描述 投票:48回答:12

我需要按值而不是按键对std::map进行排序。有一个简单的方法吗?

我从以下主题获得了一个解决方案: qazxsw poi 有更好的解决方案吗?

std::map sort by data?
c++ dictionary std
12个回答
52
投票

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

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?

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

如果你使用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! } 的替换为源关联容器(例如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作为翻转的来源。


1
投票

翻转结构可能不再是地图而是多图,因此在上面的flip_map示例中,并非B中的所有元素都必然出现在结果数据结构中。


1
投票

另一个解决方案是使用std :: make_move_iterator来构建一个新的向量(C ++ 11)

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

0
投票

在这种情况下,我们应该将map转换为multimap。我认为转换映射到设置并不好,因为如果原始映射中存在许多重复值,我们将丢失许多信息。这是我的解决方案,我定义了按值排序的比较器(cmp函数)。我们可以根据需要自定义cmp功能。

    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
  }

32
投票

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

std::unordered_map

12
投票

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


8
投票

我喜欢Oli的答案(翻转地图),但似乎有问题:容器地图不允许两个元素具有相同的键。

解决方案是使dst成为类型multimap。另一个是将src转储到向量中并对向量进行排序。前者需要对Oli的答案进行微小的修改,而后者可以简洁地使用STL副本来实现

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

3
投票

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


3
投票

要使用多映射构建Oli的解决方案(std::multimap),您可以将以下使用的两个模板函数替换为:

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

结果:


1
投票

按其值排序的#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; } 本质上是std::map。到目前为止,最简单的方法是将地图中的所有条目复制到一组(从std::set采取和改编)

here

一个警告:如果地图包含具有相同值的不同键,则它们将不会插入到集合中并丢失。


1
投票

您可以考虑使用boost :: bimap,这可能会让您感觉地图按键和值同时排序(但这不是真正发生的事情)


1
投票

在下面的示例代码中,我写了一个简单的方法来输出word_map map中的顶部单词,其中key是string(word),value是unsigned int(单词出现)。

这个想法很简单,找到当前的顶级单词并从地图中删除它。它没有经过优化,但是当地图不大时我们只需要输出前N个单词,而不是排序整个地图。

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 );
    }
}
© www.soinside.com 2019 - 2024. All rights reserved.