c++ - 使用堆查找 map 的顶部元素

Question

我有一个 unordered_hashmap 将一个字符串(例如 personName 或 SSN)映射到一个 struct Attributes，它具有该人的许多属性，包括年度收入。有许多这样的 HashMap 对应于不同的组织，例如 mapOrganizationA、mapOrganizationB 等。我需要找到具有 top-k 年收入的人(具有属性)。我在考虑使用一个带有k个节点的最小堆(以最低工资为根)，这样我就可以一个一个地扫描 map ，当前元素的收入大于最小堆的根，根可以更新。这是从不同 map 获取 top-k 的正确方法吗？我可以利用 STL 中的 min-heap 数据结构。

Answer 1

您可以使用 make_heap, push_heap, pop_heap, sort_heap, is_heap将任何非关联容器(或序列，实际上)视为堆。

这不太适合您的映射，但我认为没有什么可以阻止您将值(或指向这些值的指针/引用)存储在例如用于此目的的列表中？

另外，也许看看 Boost.MultiIndex 这是一个专注于为同一数据提供多个(高效!)索引的库