如何根据 std::map 的值获取前 n 个键？有没有办法让我得到一个列表，例如前 10 个键值最大的键值？
假设我们有一张类似这样的地图：
mymap["key1"]= 10;
mymap["key2"]= 3;
mymap["key3"]= 230;
mymap["key4"]= 15;
mymap["key5"]= 1;
mymap["key6"]= 66;
mymap["key7"]= 10;
而且我只想列出与另一个相比价值更大的前 10 个键。例如，我们的 mymap 的前 4 名是
key3
key6
key4
key1
key10
注意：
这些值不是唯一的，实际上它们是每个键的出现次数。我想获取最常出现的键的列表
注意 2：
如果 map 不是一个好的候选者并且您想提出任何建议，请按照 c++11 进行，我当时无法使用 boost。
注意3：
如果使用std::unordered_multimap<int,wstring>我还有其他选择吗？
a 的顺序map是基于它的键而不是它的值，并且不能重新排序，因此有必要遍历map并维护遇到的前十个列表，或者如Potatoswatter所评论的那样，用于为您partial_sort_copy()提取前N个值：
std::vector<std::pair<std::string, int>> top_four(4);
std::partial_sort_copy(mymap.begin(),
mymap.end(),
top_four.begin(),
top_four.end(),
[](std::pair<const std::string, int> const& l,
std::pair<const std::string, int> const& r)
{
return l.second > r.second;
});
见在线演示。
选择不同类型的容器可能更合适，boost::multi_index值得研究，其中：
... 能够构建容器，以维护一个或多个具有不同排序和访问语义的索引。
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main(int argc, const char * argv[])
{
map<string, int> entries;
// insert some random entries
for(int i = 0; i < 100; ++i)
{
string name(5, 'A' + (char)(rand() % (int)('Z' - 'A') ));
int number = rand() % 100;
entries.insert(pair<string, int>(name, number));
}
// create container for top 10
vector<pair<string, int>> sorted(10);
// sort and copy with reversed compare function using second value of std::pair
partial_sort_copy(entries.begin(), entries.end(),
sorted.begin(), sorted.end(),
[](const pair<string, int> &a, const pair<string, int> &b)
{
return !(a.second < b.second);
});
cout << endl << "all elements" << endl;
for(pair<string, int> p : entries)
{
cout << p.first << " " << p.second << endl;
}
cout << endl << "top 10" << endl;
for(pair<string, int> p : sorted)
{
cout << p.first << " " << p.second << endl;
}
return 0;
}
不仅不std::map按映射到的值排序（这样的值不需要有任何定义的排序顺序），它不允许重新排列其元素，因此在++ map[ "key1" ];将值映射回键的假设结构上进行会使向后映射无效.
最好的办法是将键值对放入另一个结构中，并在需要反向映射时按值对其进行排序。如果您始终需要反向映射，则每次更改值时都必须删除、修改和重新添加。
将现有地图分类为新结构的最有效方法是std::partial_sort_copy，正如（刚才）Al Bundy 所说明的那样。
由于映射的值没有被索引，您必须阅读所有内容并选择 10 个最大值。
std::vector<mapped_type> v;
v.reserve(mymap.size());
for(const auto& Pair : mymap)
v.push_back( Pair.second );
std::sort(v.begin(), v.end(), std::greater<mapped_type>());
for(std::size_t i = 0, n = std::min<int>(10,v.size()); i < n; ++i)
std::cout << v[i] << ' ';
另一种方法是使用两个映射或一个 bimap，因此映射的值将被排序。
您正在寻找的算法是nth_element，它对一个范围进行部分排序，以便第 n 个元素位于完全排序的范围内。例如，如果您希望前三项按降序排列，您可以编写（在伪 C++ 中）
nth_element(begin, begin + 3, end, predicate)
问题是 nth_element 不适用于 std::map。因此，我建议您将数据结构更改为成对的向量（并且根据您正在处理的数据量，您可能会发现这是一个更快的数据结构）。所以，在你的例子中，我会这样写：
typedef vector<pair<string, int>> MyVector;
typedef MyVector::value_type ValueType;
MyVector v;
// You should use an initialization list here if your
// compiler supports it (mine doesn't...)
v.emplace_back(ValueType("key1", 10));
v.emplace_back(ValueType("key2", 3));
v.emplace_back(ValueType("key3", 230));
v.emplace_back(ValueType("key4", 15));
v.emplace_back(ValueType("key5", 1));
v.emplace_back(ValueType("key6", 66));
v.emplace_back(ValueType("key7", 10));
nth_element(v.begin(), v.begin() + 3, v.end(),
[](ValueType const& x, ValueType const& y) -> bool
{
// sort descending by value
return y.second < x.second;
});
// print out the top three elements
for (size_t i = 0; i < 3; ++i)
cout << v[i].first << ": " << v[i].second << endl;
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cassert>
#include <iterator>
using namespace std;
class MyMap
{
public:
MyMap(){};
void addValue(string key, int value)
{
_map[key] = value;
_vec.push_back(make_pair(key, value));
sort(_vec.begin(), _vec.end(), Cmp());
}
vector<pair<string, int> > getTop(int n)
{
int len = min((unsigned int)n, _vec.size());
vector<Pair> res;
copy(_vec.begin(), _vec.begin() + len, back_inserter(res));
return res;
}
private:
typedef map<string, int> StrIntMap;
typedef vector<pair<string, int> > PairVector;
typedef pair<string, int> Pair;
StrIntMap _map;
PairVector _vec;
struct Cmp:
public binary_function<const Pair&, const Pair&, bool>
{
bool operator()(const Pair& left, const Pair& right)
{
return right.second < left.second;
}
};
};
int main()
{
MyMap mymap;
mymap.addValue("key1", 10);
mymap.addValue("key2", 3);
mymap.addValue("key3", 230);
mymap.addValue("key4", 15);
mymap.addValue("key6", 66);
mymap.addValue("key7", 10);
auto res = mymap.getTop(3);
for_each(res.begin(), res.end(), [](const pair<string, int> value)
{cout<<value.first<<" "<<value.second<<endl;});
}
最简单的解决方案是使用std::transform构建第二张地图：
typedef std::map<int, std::string> SortedByValue;
SortedByValue map2;
std::transform(
mymap.begin(), mymap.end(),
std::inserter( map2, map2.end() ),
[]( std::pair<std::string, int> const& original ) {
return std::pair<int, std::string>( original.second, original.first );
} );
然后挑出 的最后 n 个元素map2。
或者（并且可能更有效），您可以使用 an
std::vector<std::pair<int, std::string>>并在之后对其进行排序：
std::vector<std::pair<int, std::string>> map2( mymap.size() );
std::transform(
mymap.begin(), mymap.end()
map2.begin(),
[]( std::pair<std::string, int> const& original ) {
return std::pair<int, std::string>( original.second, original.first );
} );
std::sort( map2.begin(), map2.end() );
（请注意，这些解决方案会优化时间，但会消耗更多内存。）