CODEWITHSUNDEEP
c++containerslanguage-lawyerc++17move-semantics
Tomilov Anatoliy
Tomilov Anatoliy

Reputation: 16741

State of the value to insert

Is it possible the value passed to insert is left in a moved from state after move insertion if insert returns false?

#include <memory>
#include <map>

#include <cassert>

struct less
{
    template< typename T >
    bool operator () (const std::shared_ptr<T> & lhs, const std::shared_ptr<T> & rhs) const
    {
        return *lhs < *rhs;
    }
};

int main() {
    using key_type = int;
    using value_type = int;
    using map_type = std::map<std::shared_ptr<key_type>, std::shared_ptr<value_type>, less>;
    map_type m;
    auto p = typename map_type::value_type{std::make_shared<key_type>(1), std::make_shared<value_type>(1)};
    if (!m.insert(p).second) {
        assert(false);
    }
    assert(p.first);
    assert(p.second);
    if (m.insert(std::move(p)).second) {
        assert(false);
    }
    assert(p.first);
    assert(p.second);
}

Is the behavior of the last two assertion implementation defined?

Upvotes: 3

Views: 281

Answers (1)

lubgr
lubgr

Reputation: 38325

From [map.modifiers/2] on std::map::insert, we have

template<class P>  
pair<iterator, bool> insert(P&& x);

[...]

Effects: The first form is equivalent to return emplace(std::forward<P>(x)).

So it's in std::map::emplace... from [associative.reqmts/8] (emphasis mine):

a_­uniq.​emplace(args)

Effects: Inserts a value_­type object t constructed with std::forward<​Args​>(​args)... if and only if there is no element in the container with key equivalent to the key of t.

Hence, construction does not take place if there is already an object in the container that is associated with an equivalent key.

Let's verify with <map> from the Llvm implementation. In what follows, I've deleted some parts of the code to make it more readable. First, std::map::insert does this:

template <class _Pp, /* some SFINAE... */>
/* symbol visibility ... */
pair<iterator, bool> insert(_Pp&& __p)
    {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}

Let's go to __tree::insert_unique, then:

pair<iterator, bool> __insert_unique(__container_value_type&& __v) {
    return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v));
}

Still not there... but in __tree::emplace_unique_key_args it comes:

/* Template, template, template... return value... template */
__tree</* ... */>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
{
    __parent_pointer __parent;
    __node_base_pointer& __child = __find_equal(__parent, __k);
    __node_pointer __r = static_cast<__node_pointer>(__child);
    bool __inserted = false;
    if (__child == nullptr)
    {
        /* Some legacy dispatch for C++03... */

        // THIS IS IT:
        __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
        __r = __h.release();
        __inserted = true;
    }
    return pair<iterator, bool>(iterator(__r), __inserted);
}

I think we don't have to look into __find_equal(__parent, __k) to understand that __child == nullptr is the condition that triggers the actual insertion. In this branch, the call to __construct_node forwards the arguments, which will steal the resources managed by the std::shared_ptr<int> you passed in. The other branch simply let's the arguments untouched.

Upvotes: 3

Related Questions