Can std::vector emplace_back copy construct from an element of the vector itself?

Solution 1:

emplace_back is required to be safe for the same reason push_back is required to be safe; invalidation of pointers and references only has effect once the modifying method call returns.

In practice, this means that emplace_back performing a reallocation is required to proceed in the following order (ignoring error handling):

1. Allocate new capacity
2. Emplace-construct new element at the end of the new data segment
3. Move-construct existing elements into new data segment
4. Destruct and deallocate old data segment

At this reddit thread STL acknowledges failure of VC11 to support v.emplace_back(v[0]) as a bug, so you should definitely check whether your library supports this usage and not take it for granted.

Note that some forms of self-insertion are specifically prohibited by the Standard; for example in [sequence.reqmts] paragraph 4 Table 100 a.insert(p,i,j) has the prerequisite "i and j are not iterators into a".

Solution 2:

Contrary to what a few other people have written here, I made the experience this week that this is not safe, at least when trying to have portable code with defined behavior.

Here is some example code that may expose undefined behavior:

std::vector<uint32_t> v;
v.push_back(0);
// some more push backs into v followed but are not shown here...

v.emplace_back(v.back()); // problem is here!

The above code ran on Linux with a g++ STL without problems.

When running the same code on Windows (compiled with Visual Studio 2013 Update5), the vector sometimes contained some garbled elements (seemingly random values).

The reason is that the reference returned by v.back() was invalidated due to the container reaching its capacity limit inside v.emplace_back(), before the element was added at the end.

I looked into VC++'s STL implementation of emplace_back() and it seemed to allocate new storage, copy over the existing vector elements into the new storage location, free the old storage and then construct the element at the end of the new storage. At that point, the referenced element's underlying memory may have been freed already or otherwise invalidated. That was producing undefined behavior, causing the vector elements inserted at reallocation thresholds to be garbled.

This seems to be a (still unfixed) bug in Visual Studio. With other STL implementations I tried, the problem did not occur.

In the end, you should avoid passing a reference to a vector element to the same vector's emplace_back() for now, at least if your code gets compiled with Visual Studio and is supposed to work.

Solution 3:

I checked my vector implementation and it works here as follows:

1. Allocate new memory
2. Emplace object
3. Dealloc old memory

So everything is fine here. A similar implementation is used for push_back so this one is fine two.

FYI, here is the relevant part of the implementation. I have added comments:

template<typename _Tp, typename _Alloc>
    template<typename... _Args>
      void
      vector<_Tp, _Alloc>::
      _M_emplace_back_aux(_Args&&... __args)
      {
    const size_type __len =
      _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
// HERE WE DO THE ALLOCATION
    pointer __new_start(this->_M_allocate(__len));
    pointer __new_finish(__new_start);
    __try
      {
// HERE WE EMPLACE THE ELEMENT
        _Alloc_traits::construct(this->_M_impl, __new_start + size(),
                     std::forward<_Args>(__args)...);
        __new_finish = 0;

        __new_finish
          = std::__uninitialized_move_if_noexcept_a
          (this->_M_impl._M_start, this->_M_impl._M_finish,
           __new_start, _M_get_Tp_allocator());

        ++__new_finish;
      }
    __catch(...)
      {
        if (!__new_finish)
          _Alloc_traits::destroy(this->_M_impl, __new_start + size());
        else
          std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
        _M_deallocate(__new_start, __len);
        __throw_exception_again;
      }
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
              _M_get_Tp_allocator());
// HERE WE DESTROY THE OLD MEMORY
    _M_deallocate(this->_M_impl._M_start,
              this->_M_impl._M_end_of_storage
              - this->_M_impl._M_start);
    this->_M_impl._M_start = __new_start;
    this->_M_impl._M_finish = __new_finish;
    this->_M_impl._M_end_of_storage = __new_start + __len;
      }