This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of WP status.

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

Section: 22.3.11.5 [vector.modifiers] Status: WP Submitter: Casey Carter Opened: 2018-03-10 Last modified: 2019-02-27

Priority: 3

View all other issues in [vector.modifiers].

View all issues with WP status.

Discussion:

22.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. […]
This statement is redundant, given the blanket wording in 22.2.1 [container.requirements.general] paragraph 12:
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.
It seems that this second sentence (1) should be a note that reminds us that the blanket wording applies here when no reallocation occurs, and/or (2) actually intends to specify that iterators at and after the insertion point are invalidated.

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 22.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]

Per discussion in the prioritization thread on the reflector.

[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 21.3.2.4 [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 22.3.8.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 22.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 22.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.