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

Question

这类似于 Moving elements out of an associative container ，但不完全一样。考虑以下函数 pop 从容器中删除元素并将其返回:

#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 无法复制。但是，正如您所知，在这种情况下 move 值是“合法的”，因为我实际上是从容器中删除它(因此它不需要不可修改)，所以问题是，有没有办法实现这个以安全、合法的方式？或者从集合中提取元素是否必然涉及拷贝？我想我可以 const_cast 并且它可能会工作，但据我所知那将是 UB。这对于重类型来说很麻烦，但对于不可复制的类型来说更是如此，一旦将它们插入到集合中，它们将永远“入狱”。

Answer 1

C++17 引入了 node_handle s 用于关联容器。它们允许从关联容器中删除元素而不复制它们。特别是，您想要的行为可以通过 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;
}