有序元素的最佳容器

Question

我正在开发时间紧迫的应用程序，正在寻找最好的容器来处理以下类型的元素集合：

class Element
{
    int  weight;
    Data data;
};

考虑到我的应用程序的时间关键步骤在一个唯一线程中定期执行，如下所示：

从容器中取出最低weight的Element，data进行处理；
新 Element 的 n>=0，随机 (*) weight，被插入到容器中。

有些 Element 个容器的重量可能相同。任何时候容器中的元素总数都很高，平均几乎是静止的（几十万）。上述 extract/process/insert 序列所需的时间必须尽可能短。（注意（*）：新的权重实际上是根据数据计算的，但在这里被认为是随机的以简化。）

在对不同的 STL 容器进行一些搜索和尝试之后，我最终使用了 std::multiset 容器，它的执行速度比订购的 std::vector[=39 快了大约 5 倍=] 并且比有序 std:list 快 16 倍。但是，考虑到我的应用程序的瓶颈仍然存在于 extract/insert 操作中，我想知道我是否可以实现更好的性能。

请注意，虽然我只尝试了有序的容器，但我没有在我的要求中提到 "ordered container"。我不需要在容器中订购 Element，我只需要尽快执行 "extract lowest weighted element"/"insert new elements" 操作。我不局限于 STL 容器，如果合适的话，可以使用 boost 或任何其他实现。

感谢您的帮助。

Answer 1

I do not need the Element to be ordered in the container, I only need to perform the "extract lowest weighted element"/"insert new elements" operations as fast as possible.

那么你应该在 vector<T>.

上尝试 priority_queue<T>, or use make_heap/push_heap/pop_heap 操作

由于您正在寻找最小堆，而不是最大堆，因此您需要提供一个自定义比较器，以相反的顺序排列您的 Element 对象。

Answer 2

尝试以下任一方法：

std::map<int,std::vector<Data>>

或

std::unordered_map<int,std::vector<Data>>

上面的int是权重

根据许多不同的因素（例如元素是否存在），它们在查找、删除和添加方面都有不同的速度。（如果有，unordered_map .find 更快，如果没有，map .find 更快）

Answer 3

我认为在 STL 中，惰性 std::vector 会给出最好的结果。

建议的伪代码可能如下所示：

在向量末尾放回新元素
只有当你想要最小元素时，才对数组进行排序并得到第一个元素

通过这种方式，您可以获得 vector 的分摊插入时间、相对少量的内存分配和良好的缓存局部性。

Answer 4

考虑不同的候选人以及您的假设将如何影响最终选择是有益的。当您的需求发生变化时，切换容器变得更加容易。

通常，大小为 N 的容器的基本 acces/modification 操作大致有 3 个复杂性类别：（摊销）O(1)、O(log N) 和 O(N).

您的第一个要求（找到权重最低的元素）为您提供了大约三个具有 O(1) 复杂度的候选项，以及一个具有 O(N) 复杂度的候选项 每个元素：

O(1) 对于 std::priority_queue<Element, LowestWeightCompare>
O(1) 对于 std::multiset<Element, LowestWeightCompare>
O(1) 对于 boost::flat_multiset<Element, LowestWeightCompare>
O(N) 对于 std::unordered_multiset<Element>

您的第二个要求（随机插入新元素）为您提供以下四种选择的每个元素的复杂性

O(log N) 对于 std::priority_queue
O(log N) 对于 std::multiset
O(N) 对于 boost::flat_multiset
已摊销 O(1) std::unordered_multiset

在前三个选择中，boost::multiset应该被其他两个占主导地位N。在剩下的两个中，std::priority_queue 比 std::multiset 更好的缓存行为可能占上风。但是：衡量，衡量，衡量，然而。

std::unorderd_multiset 是否与其他三个竞争是先验的模棱两可的。根据随机插入元素的数量 n，每批 find(1)-insert(n) 的总成本对于 std::unordered_multiset 为 O(N) search + O(n) insertion，对于 std::multiset 为 O(1) search + O(n log N) insertion。同样，衡量，衡量，衡量。

这些考虑因素对您的要求有多稳健？ 如果您必须在每批中找到 k 最低权重的元素，则情况将更改如下.然后你必须比较 find(k)-insert(n) 的成本。搜索成本大致按

O(k log N) 对于 std::priority_queue
O(1) 对于 std::multiset
O(1) 对于 boost::flat_multiset
O(k N) 对于 std::unordered_multiset

请注意，priority_queue 只能有效访问顶部元素，而不是它的 k 顶部元素，而无需实际调用 pop()，每个元素具有 O(log N) 复杂度称呼。如果您预计您的代码可能会从 find(1)-insert(n) 批处理模式更改为 find(k)-insert(n)，那么选择 std::multiset 可能是个好主意，或者至少记录什么样的接口它需要的更改。

奖金：两全其美？！您可能还想尝试一下 Boost.MultiIndex 并使用类似的东西（查看文档以获取语法正确）

boost::multi_index<
    Element, 
    indexed_by<
        ordered_non_unique<member<Element, &Element::weight>, std::less<>>,
        hashed_non_unique<>
    >
>

以上代码将创建一个基于节点的容器，该容器实现两个指针结构以跟踪按 Element 权重排序并允许快速散列插入。这将允许 O(1) 查找最低权重 Element 并且还允许 O(n) 随机插入 n 新元素。

对于大型 N，它应该比前面提到的四个容器更好地扩展，但是同样，对于中等 N，指针追逐到随机内存中引起的缓存效应可能会破坏它的理论优势std::priority_queue。我有没有提到衡量，衡量，衡量的口头禅？

有序元素的最佳容器

Best container for ordered elements

c++

containers

boost

stl

multiset