c++ - 如何将元素移出 STL 优先级队列

Question

C++ 的 STL 优先级队列有一个 void pop() 方法和一个 const ref top() 方法。因此，如果你想将元素移出队列，你必须这样做:

T moved = std::move(const_cast<T&>(myQueue.top())));
myQeue.pop();

这有效地将 top 转换为非常量，以便它可以 move (而不是复制)。我不喜欢这段代码，因为强制 move 可能会使优先级队列的不变量无效，这应该因为弹出而无关紧要，但事情可能出错。

有没有更好的方法来完成弹出/move ？为什么没有T&& top_and_pop()函数？

Answer 1

std::priority_queue 基本上是堆算法 之上的薄层。您可以使用以下方法轻松创建自己的优先级队列:

• std::vector
• std::push_heap
• std::pop_heap

使用这些构建 block ，实现很简单，您可以轻松实现 move 弹出操作。以下 list 包含一个最小的工作实现:

template <typename Type, typename Compare = std::less<Type>>
class queue
{
private:
    std::vector<Type> _elements;
    Compare _compare;
public:
    explicit queue(const Compare& compare = Compare())
        : _compare{compare}
    { }
    void push(Type element)
    {
        _elements.push_back(std::move(element));
        std::push_heap(_elements.begin(), _elements.end(), _compare);
    }
    Type pop()
    {
        std::pop_heap(_elements.begin(), _elements.end(), _compare);
        Type result = std::move(_elements.back());
        _elements.pop_back();
        return std::move(result);
    }
};