2223. shrink_to_fit effect on iterator validity

Section: 23.3.11.3 [vector.capacity] Status: C++17 Submitter: Juan Soulie Opened: 2012-12-17 Last modified: 2017-07-30

Priority: 2

View other active issues in [vector.capacity].

View all other issues in [vector.capacity].

View all issues with C++17 status.

Discussion:

After the additions by 2033, it appears clear that the intended effect includes a reallocation and thus the potential effect on iterators should be explicitly added to the text in order to not contradict 23.2.2 [container.requirements.general]/11, or at the very least, explicitly state that a reallocation may happen.

Taking consistency with "reserve" into consideration, I propose:

• that the current "Remarks" are made its "Effect" instead, inserting "Reallocation happens at this point if and only if the function effectively reduces the capacity." after the note on non-bindingness.

• adding a "Remarks" paragraph, similar to that of reserve: "Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence."

BTW, while we are at it, I believe the effect on iterators should also be explicitly stated in the other instance a reallocation may happen: 23.3.11.5 [vector.modifiers]/1 — even if obvious, it only contradicts 23.2.2 [container.requirements.general]/11 implicitly.

I propose to also insert "Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence." at the appropriate location in its "Remarks".

[2012-12-19: Jonathan Wakely comments]

The described problem also affects std::basic_string and std::deque.

[2013-03-15 Issues Teleconference]

Moved to Review.

[2013-04-18, Bristol]

Daniel extends the P/R.

Rationale:

The wording in 27.4.3.5 [string.capacity] combined with 27.4.3.2 [string.require] seems to say the necessary things. We cannot impose all requirements as we do for vector, because we want to allow the short-string-optimization.

[2014-02-15 post-Issaquah session]

STL: I think that shrink_to_fit should be a no-op when called twice.

STL: Do we ever define reallocation for deque? Nope, all mentions of "reallocation" are in vector. We define what it means in vector::reserve(), but not for deque.

STL: Oh duh, they define reallocate in the PR. But I think we can do better here.

STL: Optimally, deque shrinking just allocates a new map of pointers, and drops empty blocks, but preserves pointers/references to elements.

Alisdair: That's like unordered containers, invalidating only iterators.

Pablo: It doesn't make sense to reduce capacity() to size(), because deque doesn't have capacity!

STL: For vector, "effectively reduces the capacity" is unnecessary, the capacity there is observable.

STL: There is a strong reason to provide an optimal shrink to fit for deque, since only the library implementer can do this.

STL: The other thing I don't like the repeated definition of reallocation for vector, we define it once and use it in a bunch of places. At most we can lift it up to the vector synopsis.

STL: I'll write new wording.

[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 27.4.3.2 [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 27.4.3.5 [string.capacity] around p14 unchanged, because we don't speak about reallocations and we give the strong exception guarantee in 27.4.3.2 [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 23.3.5.3 [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 23.3.11.3 [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 23.3.11.5 [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.

[2015-02 Cologne]

GR: I'm concerned that shrink_to_fit may cause reallocation without changing the capacity. […] It's about correctness. The statement about invalidation is useless if I cannot detect whether reallocation has happened?

AM: It seems like the logic goes the other way round: It's the capacity change that causes reallocation, so if there's no capacity change, there's no reallocation. But that's not quite how I'd like to say it... maybe this, : "If capacity does not change, no reallocation occurs."

GR: Where does it actually say that reserve() invalidates? AM: It should say that in the container requirements. VV: vector specifies in reserve that there's reallocation if and only if the capacity changes. GR: I can't find anything in the container requirements about reserve. DK: No, it's specified for every container separately. GR: It isn't specified for string.

GR: I'm noticing that the issue touches on shrink_to_fit for a bunch of containers. Anyway, I think the reserve issue [re string] is in scope for this issue. This change is touching on a lot of members.

AM: Landing this change will provide clarity for what we should do with basic_string. GR: We're already asking for changes; we should fix string as well. AM: If one of the changes is ready before the other, I'd like to land the finished part first, but if both are ready for Lenexa, I'm equally happy to fix them in one go.

DK will reword this.

Conclusion: Update wording, revisit in Lenexa.

[2016-08 Chicago]

Monday PM: Move to Tentatively Ready

Proposed resolution:

This wording is relative to N3936.

1. Change 27.4.3.5 [string.capacity] p14 as depicted:

   void shrink_to_fit();
   

   -14- RemarksEffects: 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.

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

   -?- Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. If no reallocation happens, they remain valid.

2. Change 23.3.5.3 [deque.capacity] p5-p7 as depicted:

   void shrink_to_fit();
   

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

   -?- 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 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 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]shrink_to_fit invalidates all the references, pointers, and iterators referring to the elements in the sequence.

3. Change 23.3.11.3 [vector.capacity] p7-p9 as depicted:

   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] It does not increase capacity(), but may reduce capacity() by causing reallocation. 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. If no reallocation happens, they remain valid.

4. Change 23.3.11.5 [vector.modifiers] p1 as depicted:

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