首页 文章

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

提问于
浏览
10

我'm aware that map is not prepared to be sorted. It' s针对快速和随机密钥访问进行了大量优化,实际上不支持 std::sort .

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

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

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

EDIT:

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

目前的做法应该是:

  • std::copy map(std::string,int)vector(pair(std::string,int))

  • 对矢量进行排序

  • 获取前10个值

  • 摧毁矢量和 Map

5 回答

  • 7

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

    在这种情况下,迭代 Map 并将所有键值对放在一对矢量中( std::vector<std::pair<std::string, int> >) . 我认为你可以使用std :: vector的双迭代器-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的任一侧,则不会指定您获得的字符串 . 在整数相等的情况下,您也可以通过让比较器查看字符串来控制它 .

  • 25

    对于按值迭代,您可以使用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_strval_int ) .

  • 1

    可能不是最优雅的方式,但您可以通过集合中的值对它们进行排序:

    #include <map>
    #include <set>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    struct sortPairSecond
    {
       bool operator()(const pair<string, int> &lhs, const pair<string, int> &rhs)
       {
           return lhs.second < rhs.second;
       }
    };
    
    
    int main (int argc, char *argv[])
    {
        cout << "Started...\n";
        map<string, int> myMap;
        myMap["One"]   = 1;
        myMap["Ten"]   = 10;
        myMap["Five"]  = 5;
        myMap["Zero"]  = 0;
        myMap["Eight"] = 8;
    
    
        cout << "Map Order:\n---------------\n";
        set<pair<string,int>, sortPairSecond > mySet;
        for(map<string, int>::const_iterator it = myMap.begin(); it != myMap.end(); ++it)
        {
            cout << it->first << " = " << it->second << "\n";
            mySet.insert(*it);
        }
    
        cout << "\nSet Order:\n--------------\n";
        for(set<pair<string, int> >::const_iterator it = mySet.begin(); it != mySet.end(); ++it)
        {
            cout << it->first << " = " << it->second << "\n";
        }
    
        return 1;
    }
    
  • 1

    如果使用map迭代器进行迭代,则将获得按键排序的项,因为它在内部使用 balancer 二叉树来存储值 . 所以你可以使用迭代器从中提取10个值 . 这是你想要的还是你想要做的其他事情?请澄清 .

    编辑:您可以直接使用set并传递比较函数,而不是使用向量和排序 . 然后你可以提取前10个元素 . 这是我的测试代码:

    typedef std::pair<std::string, int> MyPair;
    
    
    struct MyTestCompare
    {
    
        bool operator()(const MyPair& firstPair, const MyPair& secondPair) const
        {
            return firstPair.second < secondPair.second;
        }
    };
    
    int main()
    {
        std::map<std::string, int> m;
        m[std::string("1")] = 10;   
    m[std::string("2")] = 40;
    m[std::string("3")] = 30;
    m[std::string("4")] = 20;
    
    
    
        std::set<MyPair,MyTestCompare> s;
        std::map<std::string, int>::iterator iter = m.begin();
        std::map<std::string, int>::iterator endIter = m.end();
        for(; iter != endIter; ++iter)
        {
            s.insert(*iter);
        }
    
    }
    
  • 1

    另一种可能性是构建反向 Map . 对你而言 std::map<int, std::string> . 反向映射中的条目按其值排序 .

    以下是我在工具箱中用于此类场合的内容:

    template< typename TK, typename TV, class TP, class TA, typename T1, typename T2 >
    inline void asserted_insert(std::map<TK,TV,TP,TA>& m, const T1& k, const T2& v)
    {
      typedef std::map<TK,TV,TP,TA>                   map_type;
      typedef typename map_type::value_type           value_type;
      assert( m.insert(value_type(k,v)).second );
    }
    
    template< class TMap > struct reverse_map;
    template< typename T1, typename T2 > struct reverse_map< std::map<T1,T2> > {
      typedef std::map<T2,T1>                         result_t;
    };
    
    template< typename T1, typename T2, class TP1, class TA1, class TP2, class TA2 >
    inline void build_reverse_map(const std::map<T1,T2,TP1,TA1>& map, std::map<T2,T1,TP2,TA2>& reverse_map)
    {
      typedef std::map<T1,T2,TP1,TA1>                 map_type;
    
      for( typename map_type::const_iterator it=map.begin(),
                                            end=map.end(); it!=end; ++it ) {
        asserted_insert( reverse_map, it->second, it->first );
      }
    }
    

    此代码假定值也是唯一的(如果不是这样,则抛出断言) . 如果这不适用于您的问题,您可以轻松更改代码以使用多 Map .

相关问题