Proposed resolution:

This wording is relative to N4993.

1. Modify [deque.capacity] as indicated:

   void shrink_to_fit();

   -5- Preconditions: `T` is CppMoveInsertable into `deque`.

   -6- Effects: `shrink_to_fit` is a non-binding request to reduce memory use but does not change the size of the sequence. [Note 1: 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 move-construction of one object of a non-Cpp17CopyInsertable type `T` from another, then there are no effects.

2. Modify [deque.modifiers] as indicated:

   iterator insert(const_iterator position, const T& x);
   ...
   template<container-compatible-range<T> R>
     void append_range(R&& rg);

   -1- Effects: [...]

   -2- Complexity: The complexity is linear in the number of elements inserted plus the lesser of the distances to the beginning and end of the deque. Inserting a single element at either the beginning or end of a deque always takes constant time and causes a single call to a constructor of T constructs a single object of type `T`.

   -3- Remarks: If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of `T` construction or assignment of one object of type `T` from another , there are no effects. If an exception is thrown while inserting a single element at either end, there are no effects. Otherwise, if an exception is thrown by the move constructor of a move-construction of one object of non-Cpp17CopyInsertable type `T` from another, the effects are unspecified.

   [...]

   -5- Throws: Nothing unless an exception is thrown by the assignment operator of `T` the assignment of one object of type `T` from another .

   iterator erase(const_iterator position);
   iterator erase(const_iterator first, const_iterator last);
   void pop_front();
   void pop_back();

   -4- Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.

   [Note 1: `pop_front` and `pop_back` are erase operations. — end note]

   -5- Throws: Nothing unless an exception is thrown by thean assignment operator of `T`.

   -6- Complexity: The number of calls to the destructor of `T` objects of type `T` destroyed is the same as the number of elements erased, but the number of calls to the assignment operator of `T` is no more than the lesser of the number of elements before the erased elements and the number of elements after the erased elements.

3. Modify [forward.list.modifiers] as indicated:

   -1- [...] Inserting `n` elements into a `forward_list` is linear in `n`, and the number of calls to the copy or move constructor of objects of type `T` constructed is exactly equal to `n`. Erasing `n` elements from a `forward_list` is linear in `n` and the number of calls to the destructor of objects of type `T` destroyed is exactly equal to `n`.

4. Modify [list.modifiers] as indicated:

   -1- Complexity: Insertion of a single element into a list takes constant time and constructs exactly one call to a constructor of `T` object of type `T`. Insertion of multiple elements into a list is linear in the number of elements inserted and the number of calls to the copy constructor or move constructor of `T` objects of type `T` constructed is exactly equal to the number of elements inserted.

   -2- Remarks: Does not affect the validity of iterators and references. If an exception is thrown, there are no effects.

   iterator erase(const_iterator position);
   iterator erase(const_iterator first, const_iterator last);
   void pop_front();
   void pop_back();
   void clear() noexcept;

   -3- Effects: Invalidates only the iterators and references to the erased elements.

   -4- Throws: Nothing.

   -5- Complexity: Erasing a single element is a constant time operation with a single call to the destructor of `T` object of type `T` destroyed. Erasing a range in a list is linear time in the size of the range and the number of calls to the destructor of type `T` objects of type `T` destroyed is exactly equal to the size of the range.

5. Modify [vector.cons] as indicated:

   template<class InputIterator>
     constexpr vector(InputIterator first, InputIterator last,
                      const Allocator& = Allocator());

   -9- Effects: Constructs a `vector` equal to the range [`first`, `last`), using the specified allocator.

   -10- Complexity: Makes only N calls to the copy constructor of `T` Initializes exactly N elements (where N is the distance between `first` and `last`) and no reallocations if iterators `first` and `last` are of forward, bidirectional, or random access categories. It makes initializes order N calls to the copy constructor of `T` elements and performs order log N reallocations if they are just input iterators.

   template<container-compatible-range<T> R>
     constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());

   -11- Effects: Constructs a `vector` object with the elements of the range `rg`, using the specified allocator.

   -12- Complexity: Initializes exactly N elements from the results of dereferencing successive iterators of `rg`, where N is `ranges::distance(rg)`. Performs no reallocations if `R` models `ranges::forward_range` or `ranges::sized_range`; otherwise, performs order log N reallocations and initializes order N calls to the copy or move constructor of `T` elements.

6. Modify [vector.capacity] as indicated:

   constexpr void reserve(size_type n);

   -3- Preconditions: `T` is CppMoveInsertable into `vector`.

   -4- Effects: A directive that informs a `vector` of a planned change in size, so that it can manage the storage allocation accordingly. After `reserve()`, `capacity()` is greater or equal to the argument of `reserve` if reallocation happens; and equal to the previous value of `capacity()` otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of `reserve()`. If an exception is thrown other than by the move constructor of a move-construction of one object of non-Cpp17CopyInsertable type `T` from another, there are no effects.

   [...]

   constexpr shrink_to_fit();

   -8- Preconditions: `T` is CppMoveInsertable into `vector`.

   -9- Effects: `shrink_to_fit` is a non-binding request to reduce `capacity()` to `size()`. [Note 2: 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. If an exception is thrown other than by the move constructor move-construction of one object of a non-Cpp17CopyInsertable type `T` from another, there are no effects.

   [...]

   constexpr void resize(size_type sz);

   -14- Preconditions: `T` is Cpp17MoveInsertable and Cpp17DefaultInsertable into `vector`.

   -15- Effects: [...]

   -16- Remarks: If an exception is thrown other than by the move constructor move-construction of one object of a non-Cpp17CopyInsertable type `T` from another, there are no effects.

7. Modify [vector.modifiers] as indicated:

   iterator insert(const_iterator position, const T& x);
   ...
   template<container-compatible-range<T> R>
     void append_range(R&& rg);

   -1- Complexity: [...]

   -2- 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, 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 other than by the copy constructor, move constructor, assignment operator, or move assignment operator of `T` or by any \tcode{InputIterator} operation the construction or assignment of one object of type `T` from another, or by any `InputIterator` operation, there are no effects. If an exception is thrown while inserting a single element at the end and `T` is Cpp17CopyInsertable or is_nothrow_move_constructible_v<T> is `true`, there are no effects. Otherwise, if an exception is thrown by the move constructor of a move-construction of one object of non-Cpp17CopyInsertable type `T` from another, the effects are unspecified.

   constexpr iterator erase(const_iterator position);
   constexpr iterator erase(const_iterator first, const_iterator last);
   constexpr void pop_back();

   -3- Effects: Invalidates iterators and references at or after the point of the erase.

   -4- Throws: Nothing unless an exception is thrown by the assignment operator or move assignment operator of `T` construction or assignment of one object of type `T` from another.

   -5- Complexity: The destructor of `T` is called the number of times number of objects of type `T` destroyed is equal to the number of the elements erased, but thean assignment operator of `T` is called the number of times equal to the number of elements in the vector after the erased elements.

8. Modify [inplace.vector.modifiers] as indicated:

   constexpr iterator erase(const_iterator position);
   constexpr iterator erase(const_iterator first, const_iterator last);
   constexpr void pop_back();

   -29- Complexity: The destructor of `T` is called the number of times number of objects of type `T` destroyed is equal to the number of the elements erased, but thean assignment operator of `T` is called the number of times equal to the number of elements after the erased elements.

[ 2024-12-06; Jonathan adds wording, incorporating Arthur's wording ]

[ 2024-12-06; LWG telecon ]

[list.modifiers] p1 says:

Complexity: Insertion of a single element into a list takes constant time and exactly one call to a constructor of `T`. Insertion of multiple elements into a list is linear in the number of elements inserted, and the number of calls to the copy constructor or move constructor of `T` is exactly equal to the number of elements inserted.

Similarly, p5 says:

Complexity: Erasing a single element is a constant time operation with a single call to the destructor of `T`. Erasing a range in a list is linear time in the size of the range and the number of calls to the destructor of type `T` is exactly equal to the size of the range.

[deque.modifiers] is similar. Look for similar problems elsewhere.

[ 2024-08-02; Reflector poll ]

Set priority to 3 after reflector poll. Arthur to draft wording.

The spec for `deque::erase` talks about a exception "thrown by the assignment operator of `T`" but it's unclear which assignment operator this means. Arguably, this is fine because it means "the assignment operator that is used when repositioning the remaining elements". However, `deque::append_range`, `vector::append_range`, `vector::erase`, `inplace_vector::append_range`, and `inplace_vector::erase` talk about "the assignment operator or move assignment operator" which is just odd. In C++03 this just said "the assignment operator" and move semantics added "or the move assignment operator" but we could improve it.

What we should talk about is "an assignment operator", or "the assignment operator selected by overload resolution for the assignment expressions performed by the operation", or something like that.

This is potentially a bigger issue than just assignment: for `append_range` we say "If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator [...]" and there's no guarantee that the constructor used for initializing a Cpp17CopyInsertable type is a copy constructor or move constructor. It could be some templated constructor that is a better match than any of the special member functions.