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

我需要做一个模拟,可以抽象到以下(省略细节)：

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.最后,我怀疑时间事件的密度虽然不是恒定的,但也有一个上下绑定(即所有事件永远不会强烈聚集在一个时间点附近)

到目前为止的努力：

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

现在我正在使用近似值,我将时间划分为桶,并跟踪每个桶中有多少事件.然后随着时间的推移逐个处理铲斗,当从前面移除一个铲斗时,总是在末端添加一个新铲斗,从而保持铲斗的数量不变.这很快,但只是近似值.