在C ++ 11中移出std priority_queue的元素

问题描述

最小工作示例。

#include <cassert>
#include <list>
#include <queue>
//#define USE_PQ

struct MyClass
{
    const char* str;
    MyClass(const char* _str) : str(_str) {}
    MyClass(MyClass&& src) { str = src.str; src.str = nullptr; }
    MyClass(const MyClass&) = delete;
};

struct cmp_func
{
    bool operator() (const MyClass&, const MyClass&) const
    {
        return true;
    }
};

typedef std::priority_queue<MyClass, std::vector<MyClass>, cmp_func> pq_type;

#ifdef USE_PQ
MyClass remove_front(pq_type& l)
{
    MyClass moved = std::move(l.top());
    // error from the above line:
    // use of deleted function ‘MyClass::MyClass(const MyClass&)’
    l.pop();
    return std::move(moved);
}
#else
MyClass remove_front(std::list<MyClass>& l)
{
    MyClass moved = std::move(l.front());
    l.erase(l.begin());
    return std::move(moved);
}
#endif

int main()
{
    const char* hello_str = "Hello World!";
    MyClass first(hello_str);
#ifdef USE_PQ
    pq_type l;
    l.push(std::move(first));
    MyClass moved = remove_front(l);
#else
    std::list<MyClass> l;
    l.push_back(std::move(first));
    MyClass moved = remove_front(l);
#endif
    assert(moved.str);
    assert(!first.str);
    return 0;
}

现在删除第4行的注释符号，它说需要复制构造函数（我的被删除）。此外，它错过 operator = 。问题：

So this works. Now remove the comment signs from line 4 and it says that copy constructors would be needed (mine is deleted). Also, it misses operator=. Questions:

• 这里有什么区别？


• 问题可以解决吗？

• What is the difference here?
• Can the problem be fixed? If yes, how, if no, why not?

注意：你也可以使用boost的priority_queue作为你的答案，同样的错误。

Note: You can also use boost's priority_queue for your answer, but I got the same error with it.

推荐答案

这似乎是一个疏忽的设计 std :: priority_queue< ; T> 。似乎没有办法直接移动（不复制）一个元素。问题是 top（）返回一个 const T& ，所以不能绑定到 T&&< / code>。和 pop（）返回 void ，所以你不能得到它。

That seems to be an oversight in the design of std::priority_queue<T>. There doesn't appear to be a way to directly move (not copy) an element out of it. The problem is that top() returns a const T&, so that cannot bind to a T&&. And pop() returns void, so you can't get it out of that either.

但是，有一个解决方法。它确保优先级队列中的对象实际上不是 const 。他们是正常的对象，队列只是不给他们可变的访问。因此，这样做是完全合法的：

However, there's a workaround. It's as good as guaranteed that the objects inside the priority queue are not actually const. They are normal objects, the queue just doesn't give mutable access to them. Therefore, it's perfectly legal to do this:

MyClass moved = std::move(const_cast<MyClass&>(l.top()));
l.pop();

正如@DyP在注释中指出的那样，你应该确保移动对象仍然可行以便传递到队列的比较器。我相信，为了保留队列的前提条件，它必须比较以前的情况（这是不可能实现的）。

As @DyP pointed out in comments, you should make certain that the moved-from object is still viable for being passed to the queue's comparator. And I believe that in order to preserve the preconditions of the queue, it would have to compare the same as it did before (which is next to impossible to achieve).

因此，您应该封装 cast&在函数中调用top（）和 pop（），并确保队列之间不发生修改。如果你这样做，你可以合理地确定比较器不会在被移动的对象上被调用。

Therefore, you should encapsulate the cast & top() and pop() calls in a function and make sure no modifications to the queue happen in between. If you do that, you can be reasonably certain the comparator will not be invoked on the moved-from object.

当然，这样的函数应该非常好地记录。

And of course, such a function should be extremely well documented.

请注意，无论何时为类提供自定义复制/移动构造函数，都应提供相应的复制/移动赋值运算符（否则，类可能表现不一致）。所以只要给你的类一个删除的副本赋值运算符和一个适当的移动赋值运算符。

Note that whenever you provide a custom copy/move constructor for a class, you should provide the corresponding copy/move assignment operator as well (otherwise, the class can behave inconsistently). So just give your class a deleted copy assignment operator and an appropriate move assignment operator.

这篇关于在C ++ 11中移出std priority_queue的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！