c++ - 在 C++ 中实现可变排名表

Question

在事件驱动的模拟器中，我需要跟踪目录中大量内容元素的流行程度。更具体地说，我有兴趣了解任何给定内容的排名，即它在按请求数量降序排序的列表中的位置。我知道每个内容的请求数每次只会增加一个，因此排名不会发生显着变化。此外，只有在极少数情况下才会在目录中插入或删除元素，而请求的数量和频率要高得多。实现这个的最佳数据结构是什么？

这些是我考虑过的选项:

• 一个std::map<ContentElement, unsigned int>将内容映射到他们收到的请求数。这不是一个好的选择，因为它需要我将所有内容转储到一个列表中，并在我想知道内容的排名时对其进行排序，这很常见。
• 一个boost::multi_index_container有两个索引，一个用于 ContentElement 的 hashed_unique 和一个用于请求数量的 ordered_not_unique。这使我能够快速检索内容以更新其请求数量，并在我通过 modify 执行此操作时保持容器排序。调用，但我对有序索引的理解是，它仍然迫使我遍历其所有元素以计算内容的排名——我想不出一种从有序迭代器中提取排名位置的简单方法。
• 一个boost::bimap在内容元素和排名位置之间，由存储每个内容的请求数的外部排序 vector 支持。本质上，内容的等级也将表示 vector 元素的索引及其请求数。这允许我做我想做的一切(例如，轻松地从内容到排名，反之亦然)并且在新请求之后对 vector 进行排序最多需要在 bimap 中进行两次交换。然而，它感觉笨拙且容易出错，因为我很容易失去 map 和 vector 之间的同步，然后一切都会分崩离析。

我的直觉告诉我一定有一种更简单、更优雅的方法来处理这个问题，但我找不到。谁能帮忙？

Answer 1

不需要做全排序。这里的关键见解是排名只能在访问时改变 +1 或 -1。我会做以下...

将元素保存在您选择的容器中，例如

map< elementId, elementInstance >

维护一个元素排名的链表，像这样:

list< rankingInstance >

rankingInstance 有一个指向 elementInstance 的指针以及当前排名和当前访问次数的值。在访问时，您:

1. 访问 map 中的元素
2. 获取其当前排名和访问次数
3. 更新计数
4. 使用当前排名，访问链表
5. 检查邻居
6. 必要时交换列表中的位置
7. 如果发生交换，返回并更新排名改变的两个元素