关键词：
【中文标题】如何根据 std::map 的值获取前 n 个键？【英文标题】：How can i get the top n keys of std::map based on their values? 【发布时间】：2013-07-31 07:13:55 【问题描述】：如何根据值获取 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>，我还有其他选择吗？
【问题讨论】：
也许 std::map 不是你想要的。 Boost.Bimap 允许你使用值类型作为键 c++ - Tricky Method - need solution 和 map operations(find most occurence element) 等可能重复 对此有任何 c++11 解决方案吗？我当时不能使用 boost 【参考方案1】：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;
);
见online demo。
选择不同类型的容器可能更合适，boost::multi_index 值得研究，其中：
... 支持构建容器，维护一个或多个具有不同排序和访问语义的索引。
【讨论】：
使用std::partial_sort_copy可以省去迭代和保持top N的手动工作。
实际上再三考虑，我认为警告甚至不适用。它是工作的正确工具。
@Potatoswatter：谢谢，我今天学习了一种新的 STL 算法！
太好了，谢谢十亿，partial_sort_copy 的顺序是什么？【参考方案2】：
#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;
【讨论】：
【参考方案3】：std::map 不仅不按映射到的值排序（这样的值不需要有任何定义的排序顺序），它不允许重新排列其元素，因此在映射值的假设结构上执行 ++ map[ "key1" ];返回键将使反向映射无效。
最好的办法是将键值对放入另一个结构中，并在需要反向映射时按值对其进行排序。如果您始终需要反向映射，则每次更改值时都必须删除、修改和重新添加。
将现有地图分类为新结构的最有效方法是 std::partial_sort_copy，正如（刚刚）由 Al Bundy 说明的那样。
【讨论】：
【参考方案4】：由于映射的值没有被索引，您必须阅读所有内容并选择 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] << ' ';
另一种方法是使用两个映射或一个双映射，因此映射的值将被排序。
【讨论】：
Hossein 想要钥匙，而不是价值吗？【参考方案5】：您正在寻找的算法是 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;
【讨论】：
【参考方案6】：#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;);
【讨论】：
多映射不是更好的选择吗，因为与键不同的值可以重复并且无法在映射中表示？【参考方案7】：最简单的解决方案是使用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 );
);
然后挑选map2 的最后n 个元素。
或者（并且可能更有效），您可以使用
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() );
（请注意，这些解决方案会优化时间，但代价是 更多内存。）
【讨论】：
非常感谢:) 哪个算快？与手动遍历旧地图并将值插入新的多地图相比，std::transform() 有什么好处吗？（因为肯定有相同的出现，我不想丢失它们）？与使用地图相比，在向量中的每次插入中创建/删除/复制项目效率低吗？ 带有向量的解决方案肯定是这里考虑的两个解决方案中更快的（尽管带有partial_sort_copy 的解决方案可能更快）。插入地图（或多地图）通常是一项相当昂贵的操作；插入向量非常快（平均而言），并且在第二个解决方案中，最初以所需的大小构造向量。 （一个有趣的替代方法是使用目标大小的向量，使用第一个 n 元素初始化，然后作为堆管理，在其余元素上使用 for_each。如何在给定对象列表的情况下找到前 N 个？
】如何在给定对象列表的情况下找到前N个？【英文标题】：HowtofindTopNgivenalistofObject?【发布时间】：2021-08-1718:28:57【问题描述】：我想将键值对存储在地图中，并根据以下逻辑根据Key的值（数据列表）对条目进行排序：按数据对... 查看详情
如何为没有默认构造函数的对象指示 std::unordered_map 的值构造
】如何为没有默认构造函数的对象指示std::unordered_map的值构造【英文标题】：Howtoinstructstd::unordered_map\'svalueconstructionforobjectsthatdon\'thaveadefaultconstructor【发布时间】：2019-03-2715:04:31【问题描述】：假设我有以下课程：structFooFoo(intb... 查看详情
PySpark - 如何根据 CoordinateMatrix 中表示的相似点获取前 k 个 ID？
】PySpark-如何根据CoordinateMatrix中表示的相似点获取前k个ID？【英文标题】：PySpark-Howtoobtaintop-kidsbasedontheirsimilaritesrepresentedinaCoordinateMatrix?【发布时间】：2018-01-0809:14:21【问题描述】：我有一个数据字典（键代表项目（1,2,3..是项... 查看详情
将 std::map 转换为有序的 std::vector
...】：我有一个std::map，它存储一个字符串和一个类，我想根据类属性的值创建一个有序向量。但是，当我遍历向量时，什么都不会打印。到目前为止，我的代码是这样的，编译器没有发现任何错误：voidChampionship::orde 查看详情
计算向量的 std::map 的值作为键并作为值的两倍？
】计算向量的std::map的值作为键并作为值的两倍？【英文标题】：Computingthevaluesofastd::mapofvectorasthekeyanddoubleasthevalue?【发布时间】：2018-03-2905:58:46【问题描述】：std::map<std::vector<double>,double>MyMethod(std::map<std::vector<doubl 查看详情
C++ std::map 持有任何类型的值
】C++std::map持有任何类型的值【英文标题】：C++std::mapholdingANYtypeofvalue【发布时间】：2014-09-0208:16:46【问题描述】：基本上，我希望MyClass包含一个Hashmap，它将字段名称（字符串）映射到任何类型的值..为此，我编写了一个单独的M... 查看详情
用于从 std::map 的最后 n 个元素创建 std::vector 的惯用 C++
】用于从std::map的最后n个元素创建std::vector的惯用C++【英文标题】：idiomaticC++forcreatingastd::vectorfromthelastnelementsofastd::map【发布时间】：2012-03-1214:43:44【问题描述】：从std::map的最后n个元素创建std::vector的C++惯用方式是什么？我对... 查看详情
如何根据时间戳匹配值，当时间戳不存在时，该值是前一个时间戳的值
】如何根据时间戳匹配值，当时间戳不存在时，该值是前一个时间戳的值【英文标题】：HowtomatchValuesbasedontimestampsandwhentimestampdoesnotexistthevalueistheprevioustimestamp\'svalue【发布时间】：2019-12-1216:22:13【问题描述】：我正在尝试生成一... 查看详情
如何获取前 3 种类型的每组的值
】如何获取前3种类型的每组的值【英文标题】：Howtogetthevaluesforeverygroupofthetop3types【发布时间】：2021-09-1119:12:39【问题描述】：我有这张桌子ratings：iduser_idtypevalue00Rest410Bar320Cine230Cafe141Rest451Bar361Cine271Cafe582Rest492Bar3103Cine2113Cafe5我... 查看详情
如何从具有最高值的 unordered_map 中获取密钥？
】如何从具有最高值的unordered_map中获取密钥？【英文标题】：Howtogetthekeyfromanunordered_mapwiththehighestvalue?【发布时间】：2021-04-2500:00:02【问题描述】：我有以下代码查看是否存在键，如果存在，则返回键和值：std::unordered_map<std::... 查看详情
根据标准化值选择前 N 列
】根据标准化值选择前N列【英文标题】：SelecttopNcolumnsbasedonstandardizedvalues【发布时间】：2017-11-2123:24:10【问题描述】：有一点谷歌问题。如果所有值都是标准化的，是否可以根据每列中的值选择10列。例如clusterId|v1|v2|v3|v4|v6|v26__... 查看详情
如何获取 BTreeMap 中的最后一项？
】如何获取BTreeMap中的最后一项？【英文标题】：HowcanIgetthelastiteminaBTreeMap?【发布时间】：2016-02-1509:48:15【问题描述】：如果您有一个键/值对（或只是键）的排序映射，那么显而易见的操作之一就是获取第一个或最后一个对（或... 查看详情
当数据类型为 TIMESTAMP 和 TIMEZONE 时如何获取前一小时的值
】当数据类型为TIMESTAMP和TIMEZONE时如何获取前一小时的值【英文标题】：HowtograbthevaluefortheprevioushourwhenthedatatypeisTIMESTAMPwithTIMEZONE【发布时间】：2018-08-0617:49:35【问题描述】：因此，如果满足条件，我有一些逻辑将尝试获取与前一... 查看详情
如何根据另一列的值获取单行值？
】如何根据另一列的值获取单行值？【英文标题】：Howtogetsinglerowofvaluesbasedonvalueofanothercolumn?【发布时间】：2018-06-1013:30:20【问题描述】：我正在尝试根据name列中的值从value列中选择值。例如：mysql>selectname,valuefromrss_feed_property... 查看详情
c++map怎样根据索引的内容查找到key
c++的std::map有两种方式可以实现依据索引的内容查找对应的键值使用std::map的find接口。例子如下：std::map<std::string,int>mapTest;std::map<std::string,int>::iteratorit=mapTest.find("index");if(it!=mapTest.end())returnit->second;使用std::map... 查看详情
根据值有效地跟踪字典的前 k 个键
...】：2013-03-0319:32:35【问题描述】：当字典的键更新时，您如何有效地跟踪具有最大值的字典的前k个键？我尝试过在每次更新后从字典中创建排序列表的简单方法（如Gettingkeywithmaximumvalueindictionary?中所述），但 查看详情
从具有自定义类型的 c++ 中的 std::map 获取值
】从具有自定义类型的c++中的std::map获取值【英文标题】：getvaluefromstd::mapinc++whichhascustomtype【发布时间】：2015-03-3115:53:39【问题描述】：我已将地图初始化为：typedefvoid*ProxyClientHandler;std::map<string,ProxyClientHandler>connectedClient;... 查看详情
如何根据另一个对象数组的值获取一个对象数组键的值？
】如何根据另一个对象数组的值获取一个对象数组键的值？【英文标题】：howtogetthevaluesofonearrayofobjectskeybasedonvaluesofanotherarrayofobjects?【发布时间】：2020-09-1706:28:06【问题描述】：data=\'uid\':12,\'amount\':100,\'uid\':23,\'amount\':250object=12... 查看详情