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

Question

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

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

如果可能的话,最好的方法是将它排序到位,然后迭代10次,但这显然不是解决方案.

我正在尝试使用不同的解决方案multimap<int,string>(允许重复键),但我想知道是否有更优雅的解决方案,使用stl算法和posible一样多.

编辑:

我正在使用地图,因为在99%的时间里,我需要它作为地图:快速键查找以增加值.当我不再需要地图时,只需要一个好的方法稍后提取值顺序.

目前的做法应该是:

• std::copy在map(std::string,int)一个vector(pair(std::string,int))
• 对矢量进行排序
• 得到前10个值
• 摧毁矢量和地图

Answer 1

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

在这种情况下,迭代映射并将所有键值对放在一对对象中(std::vector<std::pair<std::string, int> >).我认为你可以使用std :: vector的two-iterator-arg构造函数.然后std::partial_sort在向量上使用.指定partial_sort的比较器,通过比较值int来比较对,忽略键字符串.然后在向量的开头有10对你想要的对,其余的向量包含未指定顺序的剩余对.

代码(未经测试):

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

Answer 2

对于按值迭代,您可以使用boost :: multi_index.它看起来如下:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
using namespace boost::multi_index;

struct X {
  X( std::string val_str, int val_int ) : val_str(val_str), val_int(val_int) {};
  std::string val_str;
  int         val_int;
};

typedef multi_index_container<
    X,
    indexed_by<
        hashed_unique< member<X, std::string, &X::val_str> >,
        ordered_non_unique< member<X, int, &X::val_int> >
    >
> X_map;

void func()
{
   X_map data;
   data.insert( X("test", 1) );
   // ...

   // search by val_str 
   // complexity is equal to O(1) for hashed index (worst cast O(n) ), 
   // and O(log n) for ordered index
   X_map::const_iterator it = data.find( "test" );
   // ...

   // iterate in order of val_int
   size_t N = 0;
   for ( X_map::nth_index<1>::type::const_iterator it = data.get<1>().begin(); N < 10 && it != data.get<1>().end(); ++it, ++N ) {
     // copy elements somewhere
   }
}

您可以使用任何索引进行迭代(val_str或val_int).