[ 2014-10-01, STL adds discussion and provides new wording ]

Compared to the previous proposed resolution:

• I'm changing basic_string's wording because (1) we should guarantee that capacity won't increase, (2) we should mention that it's linear complexity, and (3) we can provide a better invalidation guarantee than [string.require]/5. (As previously noted, we already have the strong exception guarantee.) This introduces the term "reallocation" into basic_string, but immediately explains what it means for iterator validity. As far as I can tell, the Small String Optimization doesn't complicate the wording here; it's a reason why an implementation might not honor the request, but if the capacity is reduced, we are definitely reallocating buffers and will invalidate everything (including when the destination is the small buffer).

• Between N3485 and N3936, deque's wording was updated to avoid talking about capacity() which it doesn't have. Since the container's capacity is unobservable, I'm saying that invalidation is unconditional.

• In vector's wording, I'm also guaranteeing that capacity won't increase, and that iterators/etc. remain valid if the capacity is unchanged.

My wording doesn't directly say that shrink_to_fit() should be a no-op when called twice in a row. (Indirectly, if the first call reduces capacity() to size(), the second call must preserve iterators/etc.) I considered rewording the complexity to say "linear if reallocation happens", but that's potentially problematic (what if we copy almost all N elements, then one throws and we have to unwind? There are no effects, so reallocation didn't happen, yet we took longer than constant time). Implementers can always do better than the stated complexity bounds.

I chose not to modify deque's requirements, so implementations remain free to reallocate the elements themselves.

I didn't attempt to centralize vector's reallocation wording. That can be done editorially, if someone is sufficiently motivated.

Previous resolution from Juan Soulie/Daniel [SUPERSEDED]:

This wording is relative to N3485.

1. Keep [string.capacity] around p14 unchanged, because we don't speak about reallocations and we give the strong exception guarantee in [string.require] (Invalidation specification also at that place):

   void shrink_to_fit();
   

   -14- Remarks: 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 ].

2. Edit [deque.capacity] around p7 as indicated:

   void shrink_to_fit();
   

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

   -?- 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 ] Reallocation happens at this point if and only if the function effectively reduces the capacity. If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.

   -6- Complexity: Linear in the size of the sequence.

   -7- Remarks: 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 ] If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

3. Edit [vector.capacity] around p7 as indicated:

   void shrink_to_fit();
   

   -7- Requires: T shall be MoveInsertable into *this.

   -?- 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 ] Reallocation happens at this point if and only if the function effectively reduces the capacity. If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.

   -8- Complexity: Linear in the size of the sequence.

   -9- Remarks: 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 ] If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

4. Edit [vector.modifiers] p1 as indicated:

   iterator insert(const_iterator position, const T& x);
   iterator insert(const_iterator position, T&& x);
   iterator insert(const_iterator position, size_type n, const T& x);
   template <class InputIterator>
   iterator insert(const_iterator position, InputIterator first, InputIterator last);
   iterator insert(const_iterator position, initializer_list<T>);
   template <class... Args> void emplace_back(Args&&... args);
   template <class... Args> iterator emplace(const_iterator position, Args&&... args);
   void push_back(const T& x);
   void push_back(T&& x);
   

   -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. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.