3077. (push|emplace)_back should invalidate the end iterator

Section: 23.3.11.5 [vector.modifiers] Status: C++20 Submitter: Casey Carter Opened: 2018-03-10 Last modified: 2021-02-25

Priority: 3

View all other issues in [vector.modifiers].

View all issues with C++20 status.

Discussion:

23.3.11.5 [vector.modifiers] paragraph 1 specifies that emplace_back and push_back do not invalidate iterators before the insertion point when reallocation is unnecessary:

Remarks: Causes reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. If no reallocation happens, all the iterators and references before the insertion point remain valid. […]

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

Also, it seems intended that reallocation should invalidate the end iterator as well.

[2018-06-18 after reflector discussion]

Priority set to 3

Previous resolution [SUPERSEDED]:

1. Edit 23.3.11.5 [vector.modifiers] as indicated:

   -1- Remarks: Invalidates the past-the-end iterator. Causes reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. [Note: If no reallocation happens, all the iterators and references before the insertion point remain valid.—end note] If an exception is thrown […]

[2018-11-28 Casey provides an updated P/R]

[2018-12-01 Status to Tentatively Ready after seven positive votes on the reflector.]

Proposed resolution:

This wording is relative to the post-San Diego working draft.

1. Change 27.4.3.5 [string.capacity] as indicated:

   void shrink_to_fit();
   

   -11- Effects: shrink_­to_­fit is a non-binding request to reduce capacity() to size(). [ Note: The request is non-binding to allow latitude for implementation-specific optimizations. — end note ] It does not increase capacity(), but may reduce capacity() by causing reallocation.

   -12- Complexity: If the size is not equal to the old capacity, linear in the size of the sequence; otherwise constant.

   -13- Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator. [ Note: If no reallocation happens, they remain valid. — end note ]

2. Change 23.3.5.3 [deque.capacity] as indicated:

   void shrink_to_fit();
   

   -5- Requires: T shall be Cpp17MoveInsertable into *this.

   -6- Effects: shrink_­to_­fit is a non-binding request to reduce memory use but does not change the size of the sequence. [ Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note ] If the size is equal to the old capacity, or if an exception is thrown other than by the move constructor of a non-Cpp17CopyInsertable T, then there are no effects.

   -7- Complexity: If the size is not equal to the old capacity, linear in the size of the sequence; otherwise constant.

   -8- Remarks: shrink_to_fit If the size is not equal to the old capacity, then invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator.

3. Change 23.3.11.3 [vector.capacity] as indicated:

   void reserve(size_type n);
   

   […]

   -7- Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator. [ Note: If no reallocation happens, they remain valid. — end note ] No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity().

   void shrink_to_fit();
   

   […]

   -10- Complexity: If reallocation happens, linear in the size of the sequence.

   -11- Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator. [ Note: If no reallocation happens, they remain valid. — end note ]

4. Change 23.3.11.5 [vector.modifiers] as indicated:

   -1- Remarks: Causes reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence as well as the past-the-end iterator. If no reallocation happens, all the iterators and references then references, pointers, and iterators before the insertion point remain valid but those at or after the insertion point, including the past-the-end iterator, are invalidated. If an exception is thrown […]

   -2- Complexity: The complexity is If reallocation happens, linear in the number of elements of the resulting vector; otherwise linear in the number of elements inserted plus the distance to the end of the vector.