从优先级队列中获取unique_ptr

Question

我正在维护一组unique_ptr实例priority_queue.在某些时候,我想获得第一个元素并将其从队列中删除.但是,这总是会产生编译器错误.请参阅下面的示例代码

int main ()
{
  std::priority_queue<std::unique_ptr<int>> queue;
  queue.push(std::unique_ptr<int>(new int(42)));

  std::unique_ptr<int> myInt = std::move(queue.top());
  return 1;
}

这会产生以下编译器错误(gcc 4.8.0):

uptrtest.cpp: In function ‘int main()’: uptrtest.cpp:6:53: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = int; _Dp = std::default_delete<int>]’    std::unique_ptr<int> myInt = std::move(queue.top());
                                                     ^ In file included from /usr/include/c++/4.8/memory:81:0,
                 from uptrtest.cpp:1: /usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here
       unique_ptr(const unique_ptr&) = delete;
       ^

更改要queue在此问题中使用的代码可以解决问题并且代码编译得很好.

有没有办法保持unique_ptrs priority_queue或我错过了什么？

Answer 1

std::priority_queue::top()返回一个const引用,因此您无法移动它.查看公共接口,priority_queue没有方法可以获取可以移动的非const引用(这是必需的unique_ptr,它没有复制构造函数).

解决方法:更换unique_ptr有shared_ptr能够复制它们(而不仅仅是移动它们).

或者,当然,完全使用另一种容器(但如果你priority_queue首先选择,这可能是你不能接受的).

您也可以使用"受保护的成员黑客"来访问受保护的成员c(底层容器),但我不推荐它,这很脏,很可能是UB.

Answer 2

我同意,这非常令人讨厌.为什么它让我的std::move元素进入队列,然后让我无法将它们移出？我们不再拥有原始的副本,所以当我做一个top()和我时,我需要一个非const对象pop().

解决方案:扩展std::priority_queue,添加一次pop_top()执行两者的方法.这应该保留队列的任何顺序.它确实依赖于c ++ 11.以下实现仅适用于gcc编译器.

template<typename _Tp, typename _Sequence = std::vector<_Tp>,
    typename _Compare = std::less<typename _Sequence::value_type> >
class priority_queue: std::priority_queue<_Tp, _Sequence, _Compare> {
public:
    typedef typename _Sequence::value_type value_type;
public:

#if __cplusplus < 201103L
explicit
priority_queue(const _Compare& __x = _Compare(),
        const _Sequence& __s = _Sequence()) : 
        std::priority_queue(__x, __s) {}
#else
explicit 
priority_queue(const _Compare& __x, const _Sequence& __s) :
        std::priority_queue<_Tp, _Sequence, _Compare>(__x, __s) {}

explicit 
priority_queue(const _Compare& __x = _Compare(), _Sequence&& __s =
        _Sequence()) :
        std::priority_queue<_Tp, _Sequence, _Compare>(__x, std::move(__s)) {}
#endif

using std::priority_queue<_Tp, _Sequence, _Compare>::empty;
using std::priority_queue<_Tp, _Sequence, _Compare>::size;
using std::priority_queue<_Tp, _Sequence, _Compare>::top;
using std::priority_queue<_Tp, _Sequence, _Compare>::push;
using std::priority_queue<_Tp, _Sequence, _Compare>::pop;

#if __cplusplus >= 201103L

using std::priority_queue<_Tp, _Sequence, _Compare>::emplace;
using std::priority_queue<_Tp, _Sequence, _Compare>::swap;

/**
 *  @brief  Removes and returns the first element.
 */
value_type pop_top() {
    __glibcxx_requires_nonempty();

    // arrange so that back contains desired
    std::pop_heap(this->c.begin(), this->c.end(), this->comp);
    value_type top = std::move(this->c.back());
    this->c.pop_back();
    return top;
}

#endif

};