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

我在priority_queue中有一个unique_ptr，我想从该集合中移除它并将其放在deque上，同时保持unique_ptr的所有权语义。但我找不到一种方法将其从priority_queue中解脱出来，而不会出现编译错误：“尝试引用已删除的函数”。什么是正确的方式来实现这一目标？如何从priority_queue中提取unique_ptr并维护所有权语义

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(); 
}

来源

2017-10-28 mentics

看起来你不应该这样做，为[顶（）返回一个为const_reference（http://en.cppreference.com/w/cpp/container/priority_queue/top）。 –

这是@MateuszDrost建议的100％重复，接受的答案甚至与此处最高的答案相同。 –

建立自己的堆。所有堆函数已经在您的<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());

来源

2017-10-28 21:24:13

所以你说的，因为一直到priority_queue接口定义，它不能做什么，我想，我必须用别的东西吗？ – mentics

@taotree：你可以使用'std :: priority_queue'，但不能直接使用'std :: unique_ptr '。例如，您可以将其封装在具有可变成员的另一个结构中。但我认为，让自己的小优先级队列类所需的接口将是从长远来看更好，容易实现。（只需将我提供的lambda包装到一个类中）。 –

-1

由于top回报const_reference不能移动，你应该const_cast它：

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

move在有效状态左边的对象，所以下面q1.pop()是完全安全的。

来源

2017-10-28 21:33:15

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

Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

所以，你priority_queue处于无效状态std::move(q1.top())和q1.pop()之间：指针后移空，因此它实际上是最小的元素现在，不是最大的，这违反了类不变量。虽然这可能在实践中起作用，但依靠实施细节而不是记录在案的行为通常是不好的。

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

来源

2017-10-28 21:45:37 lisyarus

他可以编写自己的'Compare'函数，其中null是最大的元素。 –

@MateuszDrost当然。尽管如此，'priority_queue'有没有办法让一个非const引用到它的顶部元素，并做了'const_cast'仍然违反类接口：它根本不支持更改存储的值。 – lisyarus

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

回答

相关问题