Why can't I std::move std::unique_ptrs between std::sets?

Question

I really want to move some unique_ptrs from one std::set into another:

#include <memory>
#include <algorithm>
#include <set>

int main()
{
   std::set<std::unique_ptr<int>> a;
   std::set<std::unique_ptr<int>> b;

   a.insert({0, std::unique_ptr<int>(new int(42))});

   std::move(a.begin(), a.end(), std::inserter(b, b.end()));
}

However, my GCC 4.8.5 on CentOS 7 is distinctly unhappy:

[root@localhost ~]# g++ test.cpp -std=c++11 -o test
In file included from /usr/include/c++/4.8.2/set:60:0,
                 from test.cpp:2:
/usr/include/c++/4.8.2/bits/stl_tree.h: In instantiation of ‘std::_Rb_tree_node<_Val>::_Rb_tree_node(_Args&& ...) [with _Args = {const std::unique_ptr<int, std::default_delete<int> >&}; _Val = std::unique_ptr<int>]’:
/usr/include/c++/4.8.2/ext/new_allocator.h:120:4:   required from ‘void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::_Rb_tree_node<std::unique_ptr<int> >; _Args = {const std::unique_ptr<int, std::default_delete<int> >&}; _Tp = std::_Rb_tree_node<std::unique_ptr<int> >]’
/usr/include/c++/4.8.2/bits/alloc_traits.h:254:4:   required from ‘static typename std::enable_if<std::allocator_traits<_Alloc>::__construct_helper<_Tp, _Args>::value, void>::type std::allocator_traits<_Alloc>::_S_construct(_Alloc&, _Tp*, _Args&& ...) [with _Tp = std::_Rb_tree_node<std::unique_ptr<int> >; _Args = {const std::unique_ptr<int, std::default_delete<int> >&}; _Alloc = std::allocator<std::_Rb_tree_node<std::unique_ptr<int> > >; typename std::enable_if<std::allocator_traits<_Alloc>::__construct_helper<_Tp, _Args>::value, void>::type = void]’
/usr/include/c++/4.8.2/bits/alloc_traits.h:393:57:   required from ‘static decltype (_S_construct(__a, __p, (forward<_Args>)(std::allocator_traits::construct::__args)...)) std::allocator_traits<_Alloc>::construct(_Alloc&, _Tp*, _Args&& ...) [with _Tp = std::_Rb_tree_node<std::unique_ptr<int> >; _Args = {const std::unique_ptr<int, std::default_delete<int> >&}; _Alloc = std::allocator<std::_Rb_tree_node<std::unique_ptr<int> > >; decltype (_S_construct(__a, __p, (forward<_Args>)(std::allocator_traits::construct::__args)...)) = <type error>]’
/usr/include/c++/4.8.2/bits/stl_tree.h:408:36:   required from ‘std::_Rb_tree_node<_Val>* std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {const std::unique_ptr<int, std::default_delete<int> >&}; _Key = std::unique_ptr<int>; _Val = std::unique_ptr<int>; _KeyOfValue = std::_Identity<std::unique_ptr<int> >; _Compare = std::less<std::unique_ptr<int> >; _Alloc = std::allocator<std::unique_ptr<int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<std::unique_ptr<int> >*]’
/usr/include/c++/4.8.2/bits/stl_tree.h:1023:66:   required from ‘std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, _Arg&&) [with _Arg = const std::unique_ptr<int>&; _Key = std::unique_ptr<int>; _Val = std::unique_ptr<int>; _KeyOfValue = std::_Identity<std::unique_ptr<int> >; _Compare = std::less<std::unique_ptr<int> >; _Alloc = std::allocator<std::unique_ptr<int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::unique_ptr<int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]’
/usr/include/c++/4.8.2/bits/stl_tree.h:1482:33:   required from ‘std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique_(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator, _Arg&&) [with _Arg = const std::unique_ptr<int>&; _Key = std::unique_ptr<int>; _Val = std::unique_ptr<int>; _KeyOfValue = std::_Identity<std::unique_ptr<int> >; _Compare = std::less<std::unique_ptr<int> >; _Alloc = std::allocator<std::unique_ptr<int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::unique_ptr<int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::unique_ptr<int> >]’
/usr/include/c++/4.8.2/bits/stl_tree.h:1722:37:   required from ‘void std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_II, _II) [with _InputIterator = const std::unique_ptr<int>*; _Key = std::unique_ptr<int>; _Val = std::unique_ptr<int>; _KeyOfValue = std::_Identity<std::unique_ptr<int> >; _Compare = std::less<std::unique_ptr<int> >; _Alloc = std::allocator<std::unique_ptr<int> >]’
/usr/include/c++/4.8.2/bits/stl_set.h:518:4:   required from ‘void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = const std::unique_ptr<int>*; _Key = std::unique_ptr<int>; _Compare = std::less<std::unique_ptr<int> >; _Alloc = std::allocator<std::unique_ptr<int> >]’
/usr/include/c++/4.8.2/bits/stl_set.h:530:9:   required from ‘void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::unique_ptr<int>; _Compare = std::less<std::unique_ptr<int> >; _Alloc = std::allocator<std::unique_ptr<int> >]’
test.cpp:9:49:   required from here
/usr/include/c++/4.8.2/bits/stl_tree.h:140:49: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = int; _Dp = std::default_delete<int>]’
    _M_value_field(std::forward<_Args>(__args)...) { }
                                                 ^
In file included from /usr/include/c++/4.8.2/memory:81:0,
                 from test.cpp:1:
/usr/include/c++/4.8.2/bits/unique_ptr.h:273:7: error: declared here
       unique_ptr(const unique_ptr&) = delete;
       ^

What do I need to do to make this work?

Answer 1

You basically cannot do this in C++14 since a set's elements are const. Since moving is a modifying operation, you would need some way to get non-const access to the elements and there's simply no way to do this.

But you will be able to do this in C++17 with the new merge() member function:

b.merge(std::move(a));

Similarly, there will be an extract() member function that will remove and give you non-const access to a single node.

---

Of course, you could always use a type like (with h/t by T.C.):

struct Hack {
    mutable std::unique_ptr<T> p;
    T* raw_ptr;

    bool operator<(Hack const& h) const {
        // implemented in terms of the raw ptr
        // not the unique ptr
    }
};

Moving from p is now safe (it's mutable) and as long as you just move (and not reset()) and implement the ordering in terms of the raw pointer, then you should preserve the set ordering as well. You have to store two pointers now, but this should avoid UB in C++11.

Answer 2

Here's one way to do this using C++11 in g++ 4.8.2:

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

// One possible solution:
template <typename Type>
void move_set_unique_ptr( 
    std::set<std::unique_ptr<Type>> & source,
    std::set<std::unique_ptr<Type>> & destination
) {
    for ( const std::unique_ptr<Type> & source_unique_ptr : source ) {
        destination.insert(
            std::move( const_cast<std::unique_ptr<Type> &>( source_unique_ptr ) )
        );
    }
    source.clear();
}

// Not part of a solution ... just for use with std::cout:
template <typename Type>
std::ostream & operator << (
    std::ostream & o,
    const std::set<std::unique_ptr<Type>> & s
);

int main() {
    using type = int;

    std::set<std::unique_ptr<type>> a;
    std::set<std::unique_ptr<type>> b;

    // std::make_unique<T> is not available in C++11

    a.insert( nullptr );
    a.insert( std::unique_ptr<type>( new type{ 62 } ) );
    a.insert( std::unique_ptr<type>( new type{ 42 } ) );
    a.insert( std::unique_ptr<type>( new type{ 22 } ) );

    b.insert( std::unique_ptr<type>( new type{ 41 } ) );
    b.insert( std::unique_ptr<type>( new type{ 42 } ) );
    b.insert( std::unique_ptr<type>( new type{ 43 } ) );
    b.insert( nullptr );

    std::cout << "a: " << a << '\n';
    std::cout << "b: " << b << '\n';

    move_set_unique_ptr(a, b);

    std::cout << "a: " << a << '\n';
    std::cout << "b: " << b << '\n';
}

// Not part of a solution ... just for use with std::cout:
template <typename Type>
std::ostream & operator << (
    std::ostream & o,
    const std::set<std::unique_ptr<Type>> & s
) {
    auto i = std::begin( s );
    auto end = std::end( s );
    o << '{';
    if ( i != end ) {
        auto print = [ &o, &i ]() {
            o << i->get() << ": " << ( *i == nullptr ? Type{} : **i );
        };
        o << ' '; print();
        for ( ++i; i != end; ++i ) {
            o << ", "; print();
        }
        o << ' ';
    }
    o << '}';
    return o;
}

This will output something like the following:

a: { 0: 0, 0x8f3c50: 62, 0x8f3ca0: 42, 0x8f3cf0: 22 }
b: { 0: 0, 0x8f3d40: 41, 0x8f3d90: 42, 0x8f3de0: 43 }
a: {}
b: { 0: 0, 0x8f3c50: 62, 0x8f3ca0: 42, 0x8f3cf0: 22, 0x8f3d40: 41, 0x8f3d90: 42, 0x8f3de0: 43 }

Answer 3

The elements of a std::set are const, mainly because a std::set is ordered by the value of the elements. Changing the values could change the ordering which--as consequence--will corrupt the internal representation of the std::set.

Moving a std::unique_ptr out of a std::set will certainly render the std::set unusable.