在输出之前按值对 std::map 进行排序 &破坏

2022-01-07 00:00:00 dictionary sorting c++ stl

我知道地图尚未准备好进行排序.它针对快速和随机密钥访问进行了大量优化，实际上不支持 std::sort.

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

我目前的问题是我有一个完整的 map<std::string,int>，我不会再使用它了.我只需要按 value(int) 顺序提取 10 对并销毁它.

My current problem is that I've a full map<std::string,int> 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<int,string> (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::copy map(std::string,int) 到 vector(pair(std::string,int))
  • 对向量进行排序
  • 获取前 10 个值
  • 销毁矢量和地图

推荐答案

地图存储为按键顺序排序的树.您想要 10 个最小(或最大)整数值及其键，对吗?

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::vector 的两个迭代器参数构造函数.然后在向量上使用 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 << "
";
    }
}

请注意，如果有多个字符串具有相同的值，在 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.

相关文章