c++ - 有序元素的最佳容器

Question

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

class Element
{
    int  weight;
    Data data;
};

考虑到我的应用程序的时间关键步骤(在唯一线程中定期执行)如下:

• 从容器中提取权重最小的元素，并处理数据；
• 一个 n>=0 的新 Element，具有随机 (*) weight，被插入到容器中。

容器的某些 Element 可能具有相同的权重。任何时候容器中的元素总数都很高，平均几乎是静止的(几十万)。上述提取/处理/插入序列所需的时间必须尽可能短。 (注意(*):新的权重实际上是根据数据计算的，但在这里被认为是随机的以简化。)

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

请注意，虽然我只尝试了有序容器，但我没有在我的要求中提到“有序容器”。我不需要在容器中订购 Element，我只需要尽快执行“提取最低权重元素”/“插入新元素”操作。我不局限于 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.

那你应该试试 priority_queue<T> , 或使用 make_heap / push_heap / pop_heap 在 vector<T> 上的操作.

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