在输出和输出之前按照值排序std :: map破坏 [英] Sorting a std::map by value before output & destroy

问题描述

我知道map不准备排序，它对于快速和随机的密钥访问进行了大量优化，实际上不支持std :: sort。

I am aware that map is not prepared to be sorted, its heavily optimized for fast and random key access., and actually doesn't support std::sort.

我当前的问题是我有一个完整的

My current problem is that I have a full

 map<std::string,int>

我不再使用，我只需要提取10对值）命令并销毁它。

which I'm not going to use anymore, I just need to extract 10 pairs in value(int) order and destroy it.

最好的事情是可能的是将它排序，然后迭代它10次，但显然不是一个解决方案。

The best thing if it was possible would be to sort it in place and then iterate it 10 times, but that apparently is not a solution.

我尝试不同的解决方案，通过一个multimap（允许重复键），但我想知道是否有一个更优雅的解决方案，使用stl算法

I'm trying different solutions as going through a multimap(to allow duplicate keys) but I'd like to know if there is a more elegant solution, using stl algorithms as much as posible.

编辑：

我正在使用地图，因为99％的时间我需要它作为地图，快速键查找增加值。

I'm using a map because for the 99% of the time I need it as a map, fast key lookups to increase values. Just need a good way of later extracting in value order when I don't need the map anymore.

目前的方法应该是：

• std ::将地图（std :: string，int）复制到向量（对（std :: string，int））


• 排序向量


• 获取前10个值


• 销毁向量和地图

• std::copy the map (std::string,int) to a vector(pair(std::string,int))
• sort the vector
• get the first 10 values
• destroy vector and map

推荐答案

地图存储为按照键顺序排序的树。

Maps are stored as a tree sorted in key order. You want the 10 smallest (or largest) integer values, and their keys, right?

在这种情况下，迭代映射并将所有的键值对放在一个向量对（ std :: vector< std :: pair< std :: string，int>>）。我想你可以使用std :: vector的two-iterator-arg构造函数。然后在向量上使用 std :: partial_sort 。为partial_sort指定一个比较器，它通过仅比较值int来比较对，忽略键字符串。然后你有10对你想在向量的开始，并且向量的其余部分包含未指定的顺序剩余的对。

In that case, iterate the map and put all the key-value pairs in a vector of pairs (std::vector<std::pair<std::string, int> >). I think you can just use the two-iterator-arg constructor of std::vector for this. Then use std::partial_sort on the vector. Specify a comparator to partial_sort, which compares pairs by just comparing the value int, ignoring the key string. Then you have the 10 pairs you want at the start of the vector, and the rest of the vector contains the remaining pairs in an unspecified order.

代码（未测试）：

typedef std::pair<std::string, int> mypair;

struct IntCmp {
    bool operator()(const mypair &lhs, const mypair &rhs) {
        return lhs.second < rhs.second;
    }
};


void print10(const std::map<std::string,int> &mymap) {
    std::vector<mypair> myvec(mymap.begin(), mymap.end());
    assert(myvec.size() >= 10);
    std::partial_sort(myvec.begin(), myvec.begin() + 10, myvec.end(), IntCmp());

    for (int i = 0; i < 10; ++i) {
        std::cout << i << ": " << myvec[i].first 
            << "-> " << myvec[i].second << "\n";
    }
}

请注意，如果有多个相同值的字符串，两边的限制为10，那么它不指定哪些你得到。你可以通过让比较器看看字符串，在整数相等的情况下控制这个。

Note that if there are several strings with the same value, either side of the limit of 10, then it's not specified which ones you get. You can control this by having your comparator look at the string too, in cases where the integers are equal.

这篇关于在输出和输出之前按照值排序std :: map破坏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！