是否可以在不复制的情况下从集合中提取元素？

Question

这与Moving elements out of an associative container相似，但不完全相同。考虑以下函数 pop 从容器中删除元素并 return 它：

#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;
}

显然，注释行不会编译，因为像 set、unordered_set 等关联容器的迭代器只提供对元素的 const 访问（我确实理解原因），并且无法复制 unique_ptr。但是，如您所知，在这种情况下，移动值是 "legit"，因为我实际上是从容器中删除它（因此它不需要不可修改），所以问题是，有没有办法以安全、合法的方式实施？或者从集合中提取元素是否必然涉及副本？我想我可以 const_cast 并且它可能会起作用，但据我所知，那将是 UB。这对于重类型来说很麻烦，但对于不可复制的类型来说更是如此，一旦将它们插入到集合中，它们将永远 "jailed"。

Answer 1

C++17引入了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函数：

#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;
}

是否可以在不复制的情况下从集合中提取元素？

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

c++

set

move-semantics