Title
(push|emplace)_back should invalidate the end iterator
Status
c++20
Section
[vector.modifiers]
Submitter
Casey Carter

Created on 2018-03-10.00:00:00 last changed 37 months ago

Messages

Date: 2018-12-01.15:00:55

Proposed resolution:

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

  1. Change [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 [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 [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 [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.

Date: 2018-12-01.00:00:00

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

Date: 2018-11-28.00:00:00
Per discussion in the prioritization thread on the reflector.

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

Per discussion in the prioritization thread on the reflector.
Date: 2018-06-18.00:00:00

[ 2018-06-18 after reflector discussion ]

Priority set to 3

Previous resolution [SUPERSEDED]:

  1. Edit [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 […]

Date: 2018-03-10.00:00:00

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

History
Date User Action Args
2021-02-25 10:48:01adminsetstatus: wp -> c++20
2019-02-26 17:40:23adminsetstatus: voting -> wp
2019-01-21 04:50:04adminsetstatus: ready -> voting
2018-12-01 15:00:55adminsetmessages: + msg10240
2018-12-01 15:00:55adminsetstatus: new -> ready
2018-11-28 18:55:41adminsetmessages: + msg10239
2018-06-19 05:49:11adminsetmessages: + msg9933
2018-03-12 04:28:08adminsetmessages: + msg9717
2018-03-10 00:00:00admincreate