近似排序（数组/向量），可预测的运行时间

听起来像你想要使用

std::partition

：将感兴趣的部分移到前面，将其他部分移到后面。它的复杂性大约是O（n），但它对缓存友好，所以它可能比排序快很多。

我想到的是迭代向量，如果某个事件不太重要，不要处理它，而是把它放在一边。一旦读完整个矢量，就看看放在一边的事件。当然，您可以使用具有不同优先级的多个存储桶。并且只存储那里的引用，你不想移动数兆字节的数据。 （根据Damon的要求，现在发布了答案）

如果您有N个工作线程，请为每个工作线程提供原始未排序数组的1 / N.工作人员将要做的第一件事是你的近似快速排序算法，优先选择它的阵列的各个部分。然后，他们可以按顺序处理他们的数组 - 大致首先执行更高优先级的项目，并且还非常缓存友好。这样，您不会尝试对整个阵列进行排序，甚至尝试对整个阵列进行近似排序;什么小排序，是完全并行化的。单独分拣10件比分拣整件要便宜得多。

如果要处理的项目的优先级是随机分布的，这将最有效。如果对它们有一些排序，你最终会被一个被高优先级项目淹没或缺乏的线程处理。

为每个优先级使用单独的向量。然后你不需要对它们进行排序。

听起来像一个很好的例子，近似排序算法可能很有用。

回到十年前，Chazelle开发了一种不错的数据结构，有点像堆。关键的区别在于时间复杂度。它具有所有重要操作的恒定时间，例如，插入，删除，找到最低元素等

这种数据结构的技巧是，它通过允许排序顺序中的一些错误来打破O（n * log n）复杂性障碍。

对我而言，这听起来就像你需要的那样。调用数据结构
的
软堆
</强>
并在维基百科上解释：