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. 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)

[edit] 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)

[edit] 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)