如何从priority_queue中提取unique_ptr并维护所有权语义

Question

我在priority_queue中有一个unique_ptr，我想将其从该集合中删除，并将其放在deque上，同时保持unique_pr的所有权语义。但我找不到一种方法可以在不出现编译错误的情况下将其从priority_queue中删除："试图引用已删除的函数"。实现这一目标的正确方法是什么？

struct MyStruct {
int val = 2;
MyStruct(const int val) : val(val) {}
};
void testDeque() {
std::priority_queue<std::unique_ptr<MyStruct>> q1;
q1.emplace(std::make_unique<MyStruct>(10));
std::deque<std::unique_ptr<MyStruct>> q2;
q2.push_back(q1.top()); // <- compiler error "attempting to reference a deleted function"
q2.push_back(std::move(q1.top())); // <- compiler error "attempting to reference a deleted function"
q1.pop();
}

Answer 1

创建自己的堆。所有堆函数都已在<algorithm>标头中。

std::vector<std::unique_ptr<MyStruct>> q1;
auto push = [&q1](std::unique_ptr<MyStruct> p) {
q1.push_back(std::move(p));
std::push_heap(q1.begin(), q1.end());
};
auto pop = [&q1]() {
std::pop_heap(q1.begin(), q1.end());
auto result = std::move(q1.back());
q1.pop_back();
return result;
};
push(std::make_unique<MyStruct>(10));
std::deque<std::unique_ptr<MyStruct>> q2;
q2.push_back(pop());

Answer 2

如果priority_queue::top返回一个非常数引用，用户可以更改元素的值，从而破坏使其工作的priority_queue内部不变量。引用cppreference：

使用priority_queue类似于在某些随机访问容器中管理堆，其优点是不会意外使堆失效。

因此，您的priority_queue在std::move(q1.top())和q1.pop()之间处于无效状态：指针在移动后为null，因此它现在实际上是最小的元素，而不是最大的元素，这违反了类不变量。虽然这在实践中可能有效，但依赖实现细节而不是文档化的行为通常是不好的。

正如Benjamin Lindley在他的文章中所建议的那样，您可以根据<algorithm>中的std::heap*函数编写自己的priority_queue，从而可以更改存储的值。或者，您可以使用一些排序的容器，如std::set，从而牺牲堆的优势。

Answer 3

当top返回无法移动的const_reference时，您应该const_castit:

q2.push_back(std::move(const_cast<std::unique_ptr<MyStruct>&>(q1.top())));

move使对象处于有效状态，因此遵循q1.pop()是完全安全的。