c++ - 为什么 std::set 在 std::vector 上优于 std::priority_queue 在 std::deque 上优于 std::priority_queue？

Question

在实现 A* 时，我尝试了三种类型的容器：std::set、std::priority_queueonstd::vector和std::priority_queueon std::deque。

我使用的唯一操作是push(e)、pop()和top()。

push(e)on仅std::set使用实现insert(e)。pop是m_data.erase(m_data.begin())，并且top()是*m_data.begin()。

std::priority_queue对于给定的操作，没有对onstd::vector和std::priority_queueon进行额外的实现std::deque。

在其他一切不变的情况下，std::set工作速度比其他两个选项快两倍左右。

为什么会这样？如果总是如此，为什么要std::priority_queue在效率方面使用？

PS 所有这些的复杂性push(e)是logn（n容器中元素的数量在哪里）。pop()for的给定实现std::set是 amortized ，如此处const所示，对于其他两个选项，它是（其中是比较次数），如此处所示。适合所有人。lognntopconst

PPS 我不太明白这里the number of comparisons是什么意思。是堆的深度吗？

可以在此处找到有关实施的详细信息。

标签： c++data-structuresstlcontainerstime-complexity