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

### 2223. `shrink_to_fit` effect on iterator validity

Section: 22.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 22.2.1 [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: 22.3.11.5 [vector.modifiers]/1 — even if obvious, it only contradicts 22.2.1 [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 21.3.3.5 [string.capacity] combined with 21.3.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 21.3.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 21.3.3.5 [string.capacity] around p14 unchanged, because we don't speak about reallocations and we give the strong exception guarantee in 21.3.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 22.3.8.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 22.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 22.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 21.3.3.5 [string.capacity] p14 as depicted:

   >     void shrink_to_fit();

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

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