c++ - 每帧需要一次时 make_heap vs priority_queue 效率

Question

我试图找到有关此特定用途的信息，但找不到。

在一个模拟软件(就像一个视频游戏)中，我正在构建一个事件管理器，它根据事件创建者提交的值来确定事件的优先级。事件队列每帧将被解析一次，其中的所有事件都将被处理，因此每个新帧都以一个空队列开始。

现在我有两个选项来存储事件并设置它们的优先级:

1. 使用 std::priority_queue，它将始终保持列表/vector/容器的优先级，然后在适当的时候简单地解析它；
2. 使用非优先容器，当我需要解析它时，就在它之前调用 make_heap 以便它使事件优先。

因为我每帧只解析一次事件列表，所以我不需要始终对其设置优先级。

我的问题是:在这种情况下，make_heap 是否比让容器始终保持最新更有效？还是取决于我管理的数据量？还是我想多了？

Answer 1

渐近地没有区别:

1. 在有序集合中插入 N 次是 O(N log N)。

2. 对 N 个元素的无序集合进行排序的复杂度为 O(N log N)。

因此，选择最快解决方案的最佳方式是同时实现并检查真实数据。

我认为将事件存储在诸如 std::vector 的容器中并在最后对它们进行排序会更快，因为快速添加和帧准备不会使 CPU 缓存失效，这可能发生在“long"和非平凡的 O(log N) 插入 std::priority_queue 或 std::map。

同时将事件存储在简单容器 (std::vector) 中并在需要时处理它们(排序等)对我来说看起来更合乎逻辑。