Is it safe to push_back an element from the same v

问题:

vector<int> v;
v.push_back(1);
v.push_back(v[0]);

If the second push_back causes a reallocation, the reference to the first integer in the vector will no longer be valid. So this isn't safe?

vector<int> v;
v.push_back(1);
v.reserve(v.size() + 1);
v.push_back(v[0]);

This makes it safe?

回答1:

It looks like http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 addressed this problem (or something very similar to it) as a potential defect in the standard:

1) Parameters taken by const reference can be changed during execution of the function

Examples:

Given std::vector v:

v.insert(v.begin(), v[2]);

v[2] can be changed by moving elements of vector

The proposed resolution was that this was not a defect:

vector::insert(iter, value) is required to work because the standard doesn't give permission for it not to work.

回答2:

Yes, it's safe, and standard library implementations jump through hoops to make it so.

I believe implementers trace this requirement back to 23.2/11 somehow, but I can't figure out how, and I can't find something more concrete either. The best I can find is this article:

http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771

Inspection of libc++'s and libstdc++'s implementations shows that they are also safe.

回答3:

The standard guarantees even your first example to be safe. Quoting C++11

[sequence.reqmts]

3 In Tables 100 and 101 ... X denotes a sequence container class, a denotes a value of X containing elements of type T, ... t denotes an lvalue or a const rvalue of X::value_type

16 Table 101 ...

Expression a.push_back(t) Return type void Operational semantics Appends a copy of t. Requires: T shall be CopyInsertable into X. Container basic_string, deque, list, vector

So even though it's not exactly trivial, the implementation must guarantee it will not invalidate the reference when doing the push_back.

回答4:

It is not obvious that the first example is safe, because the simplest implementation of push_back would be to first reallocate the vector, if needed, and then copy the reference.

But at least it seems to be safe with Visual Studio 2010. Its implementation of push_back does special handling of the case when you push back an element in the vector. The code is structured as follows:

void push_back(const _Ty& _Val)
    {   // insert element at end
    if (_Inside(_STD addressof(_Val)))
        {   // push back an element
                    ...
        }
    else
        {   // push back a non-element
                    ...
        }
    }

回答5:

This isn't a guarantee from the standard, but as another data point, v.push_back(v[0]) is safe for LLVM's libc++.

libc++'s std::vector::push_back calls __push_back_slow_path when it needs to reallocate memory:

void __push_back_slow_path(_Up& __x) {
  allocator_type& __a = this->__alloc();
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), 
                                                  size(), 
                                                  __a);
  // Note that we construct a copy of __x before deallocating
  // the existing storage or moving existing elements.
  __alloc_traits::construct(__a, 
                            _VSTD::__to_raw_pointer(__v.__end_), 
                            _VSTD::forward<_Up>(__x));
  __v.__end_++;
  // Moving existing elements happens here:
  __swap_out_circular_buffer(__v);
  // When __v goes out of scope, __x will be invalid.
}

回答6:

The first version is definitely NOT safe:

Operations on iterators obtained by calling a standard library container or string member function may access the underlying container, but shall not modify it. [ Note: In particular, container operations that invalidate iterators conflict with operations on iterators associated with that container. — end note ]

from section 17.6.5.9

---

Note that this is the section on data races, which people normally think of in conjunction with threading... but the actual definition involves "happens before" relationships, and I don't see any ordering relationship between the multiple side-effects of push_back in play here, namely the reference invalidation seems not to be defined as ordered with respect to copy-constructing the new tail element.

回答7:

It is completely safe.

In your second example you have

v.reserve(v.size() + 1);

which is not needed because if vector goes out of its size, it will imply the reserve.

Vector is responsible for this stuff, not you.

回答8:

Both are safe since push_back will copy the value, not the reference. If you are storing pointers, that is still safe as far as the vector is concerned, but just know that you'll have two elements of your vector pointing to the same data.

Section 23.2.1 General Container Requirements

16

• a.push_back(t) Appends a copy of t. Requires: T shall be CopyInsertable into X.
• a.push_back(rv) Appends a copy of rv. Requires: T shall be MoveInsertable into X.

Implementations of push_back must therefore ensure that a copy of v[0] is inserted. By counter example, assuming an implementation that would reallocate before copying, it would not assuredly append a copy of v[0] and as such violate the specs.

回答9:

From 23.3.6.5/1: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Since we're inserting at the end, no references will be invalidated if the vector isn't resized. So if the vector's capacity() > size() then it's guaranteed to work, otherwise it's guaranteed to be undefined behavior.