c++ - 每次更新时显示 map 按值排序

Question

基本上，我有

map<std::string, int>

如果我有

• 富 5
• 第 10 栏
• 插孔 3

在 map 中，我要显示它(注意倒序)

• 第 10 栏
• 富 5
• 插孔 3

每次更新时，我都想遍历所有元素，计算它们，按值排序。实现它的好方法是什么？我应该为构造函数提供一个比较器吗？

我要注意 map 中的值将至少更新 1 亿次，因此效率至关重要，因为额外的空间不是问题

请不要使用 Boost 解决方案...thx

Answer 1

struct keyval_t { std::string key; int val; };
int operator<(const keyval_t &a, const ketval_t &b)
{ return a.val<b.val || (a.val==b.val && a.key<b.key); }

那么你需要一张 map 和一套:

map<std::string, int>; set<keyval_t>;

update时，需要先查找map，确定key-value对，然后同时更新map和set。在打印时，您只需遍历集合。就理论上的时间复杂度而言，这是最优的。不过，它会增加一倍的内存。这是否符合您的目标？

要减少内存，您可以考虑以下几点:

map<std::string,uint64_t>; set<uint64_t>;

映射的值(也是集合的键)是:(uint64_t)val<<32|counter，其中counter是区分相同值的东西。例如，每当插入一个键时，计数器就会加 1。更新值时不需要更新计数器。如果您不喜欢 uint64_t，请改用 pair 。此解决方案也更快，因为它避免了字符串之间的比较。