c++ - 从优先级队列中获取 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 保留在 a 中，priority_queue或者我错过了什么？

score 11 · Accepted Answer

std::priority_queue::top()返回一个 const 引用，所以你不能移动它。看看没有方法来获取可以移动的非常量引用的公共接口priority_queueunique_ptr（这是强制性的，它没有复制构造函数）。

解决方案：替换unique_ptr为shared_ptr能够复制它们（而不仅仅是移动它们）。

或者，当然，完全使用另一种容器（但如果你一开始就选择priority_queue了，这对你来说可能是不可接受的）。

您也可以使用“受保护的成员黑客”来访问受保护的成员c（底层容器），但我不推荐它，这很脏，很可能是 UB。

score 9 · Accepted Answer

我同意，这非常烦人。为什么它让我std::move元素进入队列，然后让我无法将它们移出？我们不再有原件的副本，所以当我执行top()and时我需要一个非常量对象pop()。

解决方案： extend 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

};

score 0 · Accepted Answer

这是另一个丑陋的解决方法。就个人而言，我比其他建议的丑陋解决方法更喜欢它。根据您的情况，您可能需要使用这个。将原始指针存储在优先级队列中。每次弹出时，请确保将其放入唯一的指针中。还有一个析构函数来清理剩余的东西。

这是一个未经测试的代码。

class Queue_with_extra_steps {
public:
  void push( std::unique_ptr<int>&& value ) {
    queue.push( value.release() );
  }
  std::unique_ptr<int> pop() {
    if( queue.empty() ) {
      return nullptr;
    }
    std::unique_ptr<int> ans( queue.top() );
    queue.pop();
    return ans;
  }
  ~Queue_with_extra_steps() {
    while( !queue.empty() ) {
      this->pop();
    }
  }
  // Add other functions if need be.
private:
  std::priority_queue<int*> queue;
};

score 0 · Accepted Answer

一个不那么难看的解决方法是使用 mutable 创建包装器unique_ptr。您还可以分离“优先级数据”以防止其破坏堆。

#include <iostream>
#include <queue>
#include <memory>
using namespace std;

template<typename T>
struct unique_ptr_storage{
    unique_ptr_storage(uint32_t _priority,std::unique_ptr<T> &&_ptr)
    : priority(_priority)
    , ptr(std::move(_ptr)){}
    
    mutable std::unique_ptr<T> ptr;
    std::unique_ptr<T> release()const{
        return std::move(ptr);
    }
    uint32_t priority;
    bool operator<(const unique_ptr_storage<T> &other)const{
        return priority<other.priority;
    }
};

int main() {
    std::priority_queue<unique_ptr_storage<int>> q;
    
    q.emplace(1,std::make_unique<int>(10));
    q.emplace(3,std::make_unique<int>(30));
    q.emplace(2,std::make_unique<int>(20));
    
    while(!q.empty()){
        std::unique_ptr<int> p=q.top().release();
        q.pop();
        std::cout<<*p<<std::endl;
    }
    return 0;
}

输出：

30
20
10

score 0 · Accepted Answer

由于std::priority_queue::top()返回一个 const 引用，我们必须使用一些替代方法来解决它。根据对象的生命周期，您可以选择以下解决方案：

将 aconst MyObject *作为值存储在priority_queue
std::priority_queue::top()会给你一个const MyObject *
使用const_cast（https://en.cppreference.com/w/cpp/language/const_castconst ）从指针中删除限定符

使用此解决方案，如果您还需要管理对象的生命周期，您可以在另一个容器中管理unique_ptr外部，priority_queue同时仍然利用priority_queue' 对对象进行排序的能力。

c++ - 从优先级队列中获取 unique_ptr

5 回答 5

Related

Reference