12

最小的工作示例。

#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 作为答案，但我也遇到了同样的错误。

4

6 回答 6

20

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

但是，有一种解决方法。保证优先级队列中的对象实际上不是const. 它们是普通对象，队列只是不提供对它们的可变访问。因此，这样做是完全合法的：

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

正如@DyP 在评论中指出的那样，您应该确保移出的对象仍然可以传递给队列的比较器。而且我相信，为了保留队列的先决条件，它必须像以前一样进行比较（这几乎是不可能实现的）。

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

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

请注意，每当您为类提供自定义复制/移动构造函数时，您也应该提供相应的复制/移动赋值运算符（否则，该类的行为可能不一致）。因此，只需给您的班级一个已删除的复制赋值运算符和一个适当的移动赋值运算符。

（注意：是的，在某些情况下您想要一个可移动构造但不能移动分配的类，但它们非常罕见（如果您找到它们就会知道它们）。根据经验，总是同时提供ctor和assignment op）

于 2013-11-22T16:28:12.363 回答
7

根据您要存储在优先级队列中的类型，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对于保留无效对象的顺序关系的移动语义没有特殊要求，并且不会有代码部分使优先级队列的不变量无效。

于 2016-07-06T10:54:51.817 回答
6

它很容易扩展std::priority_queue，因为它将底层容器公开为受保护的成员：

template <
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>>
class extended_priority_queue : public std::priority_queue<T, Container, Compare> {
public:
  T top_and_pop() {
    std::pop_heap(c.begin(), c.end(), comp);
    T value = std::move(c.back());
    c.pop_back();
    return value;
  }
  
protected:
  using std::priority_queue<T, Container, Compare>::c;
  using std::priority_queue<T, Container, Compare>::comp;
};

如果您需要将一个元素移出std::priority_queue实例，您可以使用它extended_priority_queue来实现一个辅助函数：

template<typename PriorityQueue>
auto priority_queue_top_and_pop(PriorityQueue& queue) ->
    typename PriorityQueue::value_type {
  return static_cast<extended_priority_queue<
      typename PriorityQueue::value_type,
      typename PriorityQueue::container_type,
      typename PriorityQueue::value_compare>&>(queue).top_and_pop();
}

更新。正如@FrançoisAndrieux 指出的那样，在实际代码中最好：避免使用priority_queue_top_and_pop（技术上是UB）；extended_priority_queue从私有继承std::priority_queue以避免不需要的隐式转换。

于 2018-07-16T19:23:01.433 回答
5

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

于 2014-03-29T23:59:09.817 回答
1

这里有什么区别？

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

std::priority_queue::top返回 a const value_type&，因此您不能调用std::move（需要 a 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它来解决这个问题，但要确保你写了详尽的评论来描述你在做什么以及为什么。

于 2013-11-22T16:34:05.800 回答
0

排名靠前的答案看起来不错，但不幸的是，它与-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 上运行它（不是 clang，在这种情况下宏不会做任何事情）你会在比较器中触发一个空指针取消引用。

于 2018-02-08T16:27:02.857 回答