代码之家  ›  专栏  ›  技术社区  ›  Rick Jim DeLaHunt

为什么优先级队列需要底层容器的front()、pop_back()而不是back()、pop_back()?

c++
  •  13
  • Rick Jim DeLaHunt  · 技术社区  · 7 年前

    C++底漆 以及 https://en.cppreference.com/w/cpp/container/priority_queue 我知道:

    优先级队列需要随机访问 除了前面,向后推,向后弹出操作;

    我也读过这个 blog post 从谷歌知道:

    • push:向队列添加新元素,
    • pop:删除队列的最大元素,
    • top:访问队列的最大元素。

    push 应该由 push_back ,没问题。 和 pop top 似乎在同一个元素上运行。一种是访问它,另一种是删除它。所以我认为这两个行动应该由 pop_front() front() pop_back() back() .

    所以我很困惑,为什么要求 前面() 向后弹出()) 是吗?

    例如,假设基础容器是 vector 有了一些int元素 1,2,3,4,5,6 .适配器接口如何? pop() ,请 top() “使用基础” 前面() ,请 向后弹出()) “?

    1 回复  |  直到 7 年前
        1
  •  9
  •   o11c    7 年前

    尽管如此 pop() priority_queue 最终要移除顶层元素,它必须保持不变量,如果所有元素都简单地移动了,就不会发生这种情况。因此,它通过交换 front() back() pop_back()

    push() push_back()

    注意:由于C++使用最大堆(与常规约定相反),不变的是任何元素都必须是 比它的两个孩子(如果他们存在的话)。因为大多数有用的问题都涉及最小堆,所以您几乎总是必须指定 std::greater<> Compare 模板参数。