Is it possible to extract an element from a set without copying it?

Question

This is similar to Moving elements out of an associative container, but not exactly the same. Consider the following function pop to remove an element from a container and return it:

#include <utility>
#include <vector>
#include <set>
#include <memory>
#include <iostream>

using namespace std;

template<typename T>
typename T::value_type pop(T &collection)
{
    auto it = collection.begin();
    auto value = move(*it);
    collection.erase(it);
    return move(value);
}

int main()
{
    vector<unique_ptr<int>> v;
    v.push_back(make_unique<int>(1));
    v.push_back(make_unique<int>(2));
    cout << "pop(v): " << *pop(v) << endl;  // prints "pop(v): 1"
    set<unique_ptr<int>> s;
    s.insert(make_unique<int>(1));
    s.insert(make_unique<int>(2));
    // cout << "pop(s): " << *pop(s) << endl;  // This does not compile
    return 0;
}

Obviously, the commented line does not compile, because iterators of associative containers like set, unordered_set, etc. only provide const access to the elements (I do understand the reason for this), and unique_ptr cannot be copied. However, as you can tell, in this case moving the value is "legit", because I am actually erasing it from the container (hence it does not need to be unmodifiable), so the question is, is there a way to implement this in a safe, legal way? Or does extracting an element from a set necessarily involve a copy? I suppose I could const_cast and it would probably work, but as I understand it that would be UB. This is troublesome from heavy types, but even more so for non-copyable types, which would be "jailed" forever once they are inserted into a set.

Answer 1

C++17 introduces node_handles for associative containers. They allow to remove elements from associative containers without copying them. In particular, your desired behaviour may be implemented with the extract function:

#include <utility>
#include <vector>
#include <set>
#include <memory>
#include <iostream>

using namespace std;

template<typename T>
typename T::value_type pop(T &collection)
{
    auto node = collection.extract(begin(collection));
    return move(node.value());
}

int main()
{
    set<unique_ptr<int>> s;
    s.insert(make_unique<int>(1));
    s.insert(make_unique<int>(2));
    cout << "pop(s): " << *pop(s) << endl;
    return 0;
}