c++ - 相对于使用堆，使用带有 insert() 的向量作为优先级队列的开销是多少？(c++)

我目前正在开展一个项目，在该项目中我实现了一个结构指针向量以用作优先级队列。我使用 for 循环来确定向量中的位置（如果不小于后面），然后使用insert()将结构指针放置在队列中的位置。我back()用作队列的前端，因此我可以维护向量的弹出功能。

我只是想确定使用堆库是否会增加速度，因为这个项目取决于时间。如果您愿意，可以提供代码，堆/向量的大小可能会大大增加，因为这是 hanoi A* 搜索算法的塔。

想如果有人知道的话，我也会要求未来的知识，以便为我节省一些调试断点洗牌。

标签： c++performancevectorheapoverhead

我做了一个简单的基准测试，首先将N随机ints 插入优先级队列，然后弹出N顶部元素。

可以预期，std::vector当队列大小较小时，使用线性搜索排序会获胜，而当队列大小较大时std::priority_queue，它被实现为具有最坏插入时间的最大堆。O(log N)

基准代码可以在这里找到。