Difference between revisions of "Talk:cpp/container/vector/push back"
(Created page with "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. A...") |
|||
| (11 intermediate revisions by 8 users not shown) | |||
| Line 1: | Line 1: | ||
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. | 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. | ||
[[Special:Contributions/173.11.122.193|173.11.122.193]] 10:45, 5 July 2013 (PDT) | [[Special:Contributions/173.11.122.193|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. --[[User:Nate|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. [[User:Collin Stocks|Collin Stocks]] 12:13, 18 August 2013 (PDT) | ||
| + | |||
| + | : Indeed. Thanks for bringing this up. [[User:P12|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) --[[User:Cubbi|Cubbi]] ([[User talk:Cubbi|talk]]) 21:13, 20 September 2015 (PDT) | ||
| + | |||
| + | == Exceptions == | ||
| + | |||
| + | The "Exceptions" section should probably also list at least the following possibility: | ||
| + | |||
| + | * <code>std::length_error</code> if <code>size() == max_size()</code>. | ||
| + | |||
| + | This codepath comes up implicitly in [http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4234.pdf 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. —[[Special:Contributions/4.15.79.98|4.15.79.98]] 15:38, 1 July 2016 (PDT) | ||
| + | |||
| + | : technically, {{lc|std::length_error}} is only specified for {{lc|std::vector::reserve}}, so here it would have to go under Notes, I think. --[[User:Cubbi|Cubbi]] ([[User talk:Cubbi|talk]]) 06:09, 5 July 2016 (PDT) | ||
Latest revision as of 10:54, 26 March 2021
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)
[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)
[edit] Exceptions
The "Exceptions" section should probably also list at least the following possibility:
-
std::length_errorifsize() == 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)
