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

Question

最小工作示例。

#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=。问题：

• 这里有什么区别？
• 问题能解决吗？如果是的话，如果不是，为什么不呢？

注意：您也可以使用boost的priority_queue作为您的答案，但我得到了与它相同的错误。

Answer 1

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

但是，有一种解决方法。这与确保优先队列内的对象实际上不是const一样好。它们是普通的对象，队列不会给予它们可变的访问权限。因此，它是完全合法的做到这一点：

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

由于@DyP在评论中指出，你应该肯定的是，移动，从目标仍然是可行的被传递到队列的比较。我相信，为了保留队列的先决条件，它必须与以前相同（这是几乎不可能实现的）。

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

当然，这样的功能应该是非常有据可查的。

---

请注意，只要你一类提供自定义的复制/移动构造函数，你应该提供相应的复制/移动赋值运算符，以及（否则，类可以行为不一致）。所以给你的班级一个删除拷贝赋值操作符和一个合适的移动赋值操作符。 （注：是的，有些情况下你需要一个可移动的，但不能移动的类，但它们非常少见（如果你找到它们，你就会知道它们）。经验法则，总是提供ctor和赋值操作）

Answer 2

这里有什么区别？

MyClass remove_front(pq_type& l) 
{ 
    MyClass moved = std::move(l.top()); // PROBLEM 
    l.pop(); 
    return std::move(moved); 
} 

std::priority_queue::top返回一个const value_type&，所以你不能叫std::move（这需要一个T&&）。

MyClass remove_front(std::list<MyClass>& l) 
{ 
    MyClass moved = std::move(l.front()); 
    l.erase(l.begin()); 
    return std::move(moved); 
} 

std::list::front具有一个返回参考过载，因此它具有结合到T&&一种方式。

我不确定为什么top没有非常量过载（可能是标准中的疏忽？）。你可以使用const_cast来解决这个问题，但要确保你写下详细的评论，描述你在做什么以及为什么。

Answer 3

为什么没有非（const-ref）top（）：可能有一个很好的理由：修改对象会破坏priority_queue不变量。所以const_cast技巧可能只会在你弹出后立即起作用。

Answer 4

根据您想要存储在优先级队列中的类型，替代Angew的解决方案（避免了const_cast并删除了一些在脚下拍摄自己的机会）将包装元素类型，如下所示：

struct Item { 
    mutable MyClass element; 
    int priority; // Could be any less-than-comparable type. 

    // Must not touch "element". 
    bool operator<(const Item& i) const { return priority < i.priority; } 
}; 

移出队列的元素将被做这样：

MyClass moved = std::move(l.top().element); 
l.pop(); 

这样一来，有上MyClass的移动语义无特殊要求维护秩序relatio n，对于无效的对象中的不变量，将不存在任何代码段，其中优先级队列的不变量是无效的。

Answer 5

排名最高的答案看起来不错，但不幸的是，它与-D_GLIBCXX_DEBUG不兼容。例如：

#include <iostream> 
#include <memory> 
#include <queue> 
#include <vector> 

struct T { 
    int x; 
    std::shared_ptr<int> ptr; 
    T(int x, std::shared_ptr<int> ptr) : x(x), ptr(ptr) {} 
}; 
struct Compare { 
    bool operator()(const T& x, const T& y) { 
    return *x.ptr < *y.ptr; 
    } 
}; 
int main() { 
    auto ptr1 = std::make_shared<int>(3); 
    auto ptr2 = std::make_shared<int>(3); 
    std::priority_queue<T, std::vector<T>, Compare> f; 
    f.emplace(3, ptr1); 
    f.emplace(4, ptr2); 
    T moved = std::move(const_cast<T&>(f.top())); 
    f.pop(); 
    std::cerr << moved.x << "\n"; 
} 

如果你运行这个与g++ foo.cpp -D_GLIBCXX_DEBUG -O0 -g -std=c++11 && ./a.out在GCC（不铛，宏不会做在这种情况下，任何东西），你将触发比较空指针。