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

Question

我知道map不适合排序，它被高度优化以实现快速和随机的键访问，并且实际上不支持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))
• 对向量进行排序
• 获取前10个值
• 销毁向量和map

- Arkaitz Jimenez

---

你的需求对我来说非常不清楚。如果我理解正确，您需要通过值而不是键在地图中找到10个条目？一旦您拥有它们，您打算怎么做？我问这个问题是因为“销毁”是一个模糊的术语，我无法猜测std::pair<std::string,int>的含义。它们是否应该从地图中删除？（可能不是，因为您说您不再需要地图。但还有其他吗？） - sbi

地图将被销毁，所以我不关心它以后会发生什么，只需要这10个值。 - Arkaitz Jimenez

Answer 1

Map被存储为按键排序的树。你想要获取10个最小（或最大）的整数值及其对应的键，是吗？

在这种情况下，迭代Map并将所有键值对放入一对向量中(std::vector<std::pair<std::string, int> >)。我认为您可以使用std::vector的两个迭代器参数构造函数来完成此操作。然后在向量上使用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的限制范围内的任意一侧，那么不指定哪个字符串将被获取。您可以通过让您的比较器也查看字符串来控制此项，这种情况下整数相等。

- Steve Jessop

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）。

- Kirill V. Lyadvinsky

Answer 3

可能不是最优雅的方法，但您可以通过集合中的值进行排序，如下所示：

#include

- RC.

Answer 4

如果你使用map迭代器进行迭代，你将会得到按key排序的items，因为它在内部使用平衡二叉树来存储值。所以你可以使用迭代器从中提取10个值。这是你想要的吗？还是你想做其他事情？请澄清。

编辑： 不必使用vector和排序，你可以直接使用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);
    }

}

- Naveen

---

我只需要按值（整数）顺序提取10个成对数据并将其删除。 - Arkaitz Jimenez

你的地图是什么类型，即键和值各是什么？ - Naveen

抱歉，问题描述中的地图类型被忽略了，我已经解决了这个问题。 - Arkaitz Jimenez

Answer 5

另一种可能性是构建反向映射。对于您来说，这将是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 );
  }
}

这段代码假设值是唯一的（如果不是，则会引发断言）。如果这不适用于您的问题，您可以轻松地更改代码以使用多重映射。

- sbi