我正在开发时间紧迫的应用程序,并且正在寻找最好的容器来处理以下类型的元素集合:
class Element
{
int weight;
Data data;
};
考虑到我的应用程序的时间关键步骤(在唯一线程中定期执行)如下:
- 从容器中提取
权重
最小的元素
,并处理数据
; - 一个 n>=0 的新
Element
,具有随机 (*)weight
,被插入到容器中。
容器的某些 Element
可能具有相同的权重。任何时候容器中的元素总数都很高,平均几乎是静止的(几十万)。上述提取/处理/插入序列所需的时间必须尽可能短。 (注意(*):新的权重实际上是根据数据计算的,但在这里被认为是随机的以简化。)
在对不同的 STL 容器进行一些搜索和尝试后,我最终使用了 std::multiset 容器,它的执行速度比有序的 std::vector 快 5 倍,快 16 倍比有序的 std:list。但是,考虑到我的应用程序的瓶颈仍然存在于提取/插入操作中,我想知道我是否可以实现更好的性能。
请注意,虽然我只尝试了有序容器,但我没有在我的要求中提到“有序容器”。我不需要在容器中订购 Element
,我只需要尽快执行“提取最低权重元素”/“插入新元素”操作。我不局限于 STL 容器,如果合适的话,可以使用 boost 或任何其他实现。
感谢您的帮助。
最佳答案
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
对象以相反的顺序。
关于c++ - 有序元素的最佳容器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36224942/