c++ - 如何快速将元素重复插入到排序列表中

Question

我没有接受过正式的 CS 培训，所以请多多包涵。

我需要做一个模拟，可以抽象出如下(省略细节):

We have a list of real numbers representing the times of events. In each step, we

1. remove the first event, and
2. as a result of "processing" it, a few other events may get inserted into the list at a strictly later time

and repeat this many times.

问题

我可以使用什么数据结构/算法来尽可能高效地实现它？我需要显着增加列表中事件/数字的数量。优先考虑的是尽可能快地处理长列表。

由于我是在 C++ 中执行此操作，STL 或 boost 中已有哪些数据结构可以简化此操作的实现？

---

更多详情:

列表中的事件数是可变的，但保证在 n 和 2*n 之间，其中 n 是一些模拟范围。在事件时间增加的同时，最新事件和最早事件的时间差也保证小于常数 T。最后，我怀疑事件的时间密度虽然不是常数，但也有上限和下限(即所有事件永远不会强烈聚集在一个时间点周围)

到目前为止的努力:

正如问题的标题所说，我正在考虑使用经过排序的数字列表。如果我使用链表进行恒定时间插入，那么我很难找到以快速(次线性)方式插入新事件的位置。

现在我正在使用一个近似值，我将时间分成桶，并跟踪每个桶中有多少事件。然后随着时间“流逝”一个接一个地处理桶，当从前面移除一个桶时总是在末尾添加一个新桶，从而保持桶的数量不变。这很快，但只是一个近似值。

Answer 1

最小堆可能适合您的需要。有一个 explanation here我认为 STL 为您提供了 priority_queue。

插入时间为O(log N)，移除时间为O(log N)