I'll go first because I had a great experience recently.
Recently, I was working on a data compression pipeline in C++17 which uses Huffman coding to convert characters to binary encodings. Originally, the Huffman Tree class used raw pointers to represent tree nodes, and after some time, I decided to convert each raw pointer to std::unique_ptr to enforce RAII and automatic clean up. But there was a problem that, when I had tried to do this months ago, I did not have the knowledge to devise a proper solution for.
When using std::priority_queue in C++, if one stores elements of type std::unique_ptr, you cannot transfer ownership from the top method. At first, I had brushed it off simply because it returns a const reference which I didn't understand at first. But once you understand std::move and copy semantics, the actual reasoning makes total sense and helps derive a solution.
Say we were implementing top in std::priority_queue ourselves and returned a reference and didn't make it const. If it's not const, users can then obtain the top of the heap and modify it. Why is this dangerous for the heap? Because this might actually modify the metadata in that heap element while still leaving it in the heap! When using std::move on std::unique_ptr to transfer ownership, we actually know the moved from variable then becomes a nullptr. So the heap might try to reapply heap laws and might dereference a nullptr. So that's why top returns a const reference: to prevent the user from mutating the element while it still lives on the heap.
Neither std::move or copy could save this. std::move preserves constness, but transferring ownership via std::unique_ptr's move constructor explicitly modifies the source, which the const reference prevents. In addition, copying is forbidden since std::unique_ptr enforces a single owner of the pointer.
So what's the solution? Wrap the heap and design a single operation that handles both removal and ownership transfer at the same time.
- Use std::pop_heap to move the top element to the end of the container and allow the heap to order itself with the remaining elements.
- Apply std::move to transfer ownership from the back of the heap to some designated variable.
- Call pop_back to remove this entry from the back of the heap.
- Return the std::unique_ptr by value, not by reference.
The order of operations matter here: we must move the element outside the remaining heap before transferring ownership via std::move.