如何從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並維護所有權語義

回答

相關問題