c++ - 在输出和销毁之前按值对 std::map 进行排序

Question

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

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

如果可能的话，最好的办法是就地排序，然后迭代 10 次，但这显然不是解决方案。

我正在尝试不同的解决方案来处理 multimap<int,string> (允许重复键)，但我想知道是否有更优雅的解决方案，尽可能多地使用 STL 算法。

编辑:

我使用 map 是因为在 99% 的时间里，我需要它作为 map :快速键查找以增加值。当我不再需要 map 时，只需要一种稍后按值顺序提取的好方法。

目前的做法是:

• std::copy map(std::string,int)到 vector(pair(std::string,int))
• 对 vector 进行排序
• 获取前 10 个值
• 销毁 vector 和 map

Answer 1

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

在那种情况下，迭代映射并将所有键值对放在一个对 vector 中( std::vector<std::pair<std::string, int> >) 。我认为你可以为此使用 std::vector 的双迭代器参数构造函数。然后在 vector 上使用 std::partial_sort。为 partial_sort 指定一个比较器，它通过只比较值 int 来比较对，忽略键字符串。然后你在 vector 的开头有你想要的 10 对， vector 的其余部分包含未指定顺序的剩余对。

代码(未经测试):

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 的任一侧，则不会指定您获得哪些。在整数相等的情况下，您也可以通过让比较器查看字符串来控制这一点。