Talk:cpp/container/vector/push back

The page contains a major error. It states that no iterators or references are invalidated when the capacity is sufficient to accommodate the new element. This is incorrect. Any insertion operator on a vector always invalidates all iterators and references that refer to the point of insertion and past the point of insertion. For this reason `push_back` always invalidates the `end()` iterator. 173.11.122.193 10:45, 5 July 2013 (PDT)

Thanks for the note, I believe you are correct. I've updated the page to reflect that the past-the-end iterator is invalidated. --Nate 19:00, 5 July 2013 (PDT)

Complexity

The complexity of this operation is usually constant, but if the vector does not have the capacity to hold the additional element, a resize takes place, which is linear in the number of elements. This resize happens a logarithmic number of times in the final size of the vector. Thus the complexity of push_back is amortised constant, not constant. Collin Stocks 12:13, 18 August 2013 (PDT)

Indeed. Thanks for bringing this up. P12 13:18, 18 August 2013 (PDT)

complexity

In order to claim amortized constant complexity, do we have to assume memory allocation has constant complexity? Can we assume that?

standard C++ complexity requirements are expressed in terms of operations on the elements of the container. Allocation of a new uninitialized memory block is not an operation on an element and is excluded from the analysis (but move constructor calls that follow are counted) --Cubbi (talk) 21:13, 20 September 2015 (PDT)

Exceptions

The "Exceptions" section should probably also list at least the following possibility:

• std::length_error if size() == max_size().

This codepath comes up implicitly in N4234 "0-overhead-principle violations in exception handling - part 2", and was pretty confusing to me until I traced through and realized what was going on. —4.15.79.98 15:38, 1 July 2016 (PDT)

technically, std::length_error is only specified for std::vector::reserve, so here it would have to go under Notes, I think. --Cubbi (talk) 06:09, 5 July 2016 (PDT)