libc++ difference between vector::insert overloads

Question

The std::vector implementation of libc++ has the following overloads of insert:

template <class _Tp, class _Allocator>
typename vector<_Tp, _Allocator>::iterator
vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
{
    pointer __p = this->__begin_ + (__position - begin());
    if (this->__end_ < this->__end_cap())
    {
        __RAII_IncreaseAnnotator __annotator(*this);
        if (__p == this->__end_)
        {
            __alloc_traits::construct(this->__alloc(),
                                      _VSTD::__to_raw_pointer(this->__end_), __x);
            ++this->__end_;
        }
        else
        {
            __move_range(__p, this->__end_, __p + 1);
            const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
            if (__p <= __xr && __xr < this->__end_) // [*]
                ++__xr;
            *__p = *__xr;
        }
        __annotator.__done();
    }
    else
    {
        allocator_type& __a = this->__alloc();
        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
        __v.push_back(__x);
        __p = __swap_out_circular_buffer(__v, __p);
    }
    return __make_iter(__p);
}

... and a similar, taking an rvalue reference:

template <class _Tp, class _Allocator>
typename vector<_Tp, _Allocator>::iterator
vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
{
    pointer __p = this->__begin_ + (__position - begin());
    if (this->__end_ < this->__end_cap())
    {
        __RAII_IncreaseAnnotator __annotator(*this);
        if (__p == this->__end_)
        {
            __alloc_traits::construct(this->__alloc(),
                                      _VSTD::__to_raw_pointer(this->__end_),
                                      _VSTD::move(__x));
            ++this->__end_;
        }
        else
        {
            __move_range(__p, this->__end_, __p + 1);
            *__p = _VSTD::move(__x);
        }
        __annotator.__done();
    }
    else
    {
        allocator_type& __a = this->__alloc();
        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
        __v.push_back(_VSTD::move(__x));
        __p = __swap_out_circular_buffer(__v, __p);
    }
    return __make_iter(__p);
}

What is the purpose of the branch marked with [*] in the first overload? Is it required by the standard? Why is it absent in the second overload? I couldn't find the equivalent construct in libstdc++.

Edit: libstdc++ solves the same problem by creating a temporary copy.

Answer 1

It's a condition to handle the case where the element you're trying to insert already exists in the vector.

To explain this, let's start with defining the variables being used in the function.

• __p is a pointer to the position where you want to insert the new element
• __xr is a pointer to the address of the element you want to insert

The code path you're asking about is executed when the vector has sufficient capacity to insert an additional element (if (this->__end_ < this->__end_cap())). Also, the insertion point is not the end() iterator (if (__p == this->__end_) — the else path is executed).

In this case, the implementation first moves everything in the range [__p, end()) one position further — __move_range(__p, this->__end_, __p + 1);

But what if the element you're trying to insert was part of the range that just got moved? If so, you must increment the pointer to the element to be inserted. That is what the following lines do

if (__p <= __xr && __xr < this->__end_)
  ++__xr;

The rvalue reference overload isn't doing the same checks because the implementation is allowed to assume that any object referred to by an rvalue reference is uniquely referenced, so trying to perform an insert with an rvalue reference to an element that already exists in the vector is undefined behavior.

From N3337, §17.6.4.9/1 [res.on.arguments]

Each of the following applies to all arguments to functions defined in the C++ standard library, unless explicitly stated otherwise.
— ...
— If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument.

Here's the defect report and rationale for the above clause.