Movatterモバイル変換

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

2223.shrink_to_fit effect on iterator validity

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

Priority:2

View otheractive issues in [vector.capacity].

View all otherissues in [vector.capacity].

View all issues withC++17 status.

Discussion:

After the additions by2033⁽ⁱ⁾, 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.13.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 affectsstd::basic_string andstd::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 forvector, becausewe want to allow the short-string-optimization.

[2014-02-15 post-Issaquah session]

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

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

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 reducecapacity() tosize(), becausedeque doesn't have capacity!

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

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

STL: The other thing I don't like the repeated definition of reallocation forvector, we define it once and use it in a bunch of places. At most we can lift it up to thevector 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 changingbasic_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" intobasic_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 aboutcapacity() which it doesn't have. Since the container's capacity is unobservable, I'm saying that invalidation is unconditional.

• Invector'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 thatshrink_to_fit() should be a no-op when called twice in a row. (Indirectly, if the first call reducescapacity() tosize(), 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 allN 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 modifydeque'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 p14unchanged, because we don't speak aboutreallocations and we give the strong exception guarantee in 27.4.3.2[string.require] (Invalidationspecification also at that place):

   void shrink_to_fit();

   -14-Remarks:shrink_to_fit is a non-binding request to reducecapacity() tosize(). [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 beMoveInsertable into*this.

   -?-Effects:shrink_to_fit is a non-binding request to reducecapacity() tosize(). [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-CopyInsertableT there are no effects.

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

   -7-Remarks:shrink_to_fit is a non-binding request to reducecapacity() tosize(). [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-CopyInsertableT there are no effects.Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

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

   void shrink_to_fit();

   -7-Requires:T shall beMoveInsertable into*this.

   -?-Effects:shrink_to_fit is a non-binding request to reducecapacity() tosize(). [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-CopyInsertableT there are no effects.

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

   -9-Remarks:shrink_to_fit is a non-binding request to reducecapacity() tosize(). [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-CopyInsertableT there are no effects.Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

4. Edit 23.3.13.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 ofT or by anyInputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyInsertableT, the effects are unspecified.

[2015-02 Cologne]

GR: I'm concerned thatshrink_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 thatreserve() invalidates? AM: It should say that in the container requirements. VV: vector specifies inreserve that there's reallocation if and only if the capacity changes. GR: I can't findanything in the container requirements aboutreserve. DK: No, it's specified for every container separately. GR: It isn't specified for string.

GR: I'm noticing that the issue touches onshrink_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 withbasic_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 reducecapacity() tosize(). [Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note]It does not increasecapacity(), but may reducecapacity() 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 beMoveInsertable 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-CopyInsertableT 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 thesize of the sequence. [Note: The request is non-binding to allow latitude for implementation-specificoptimizations. —end note]shrink_to_fit invalidates all the references, pointers, and iterators referring to the elements in the sequence.

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

   void shrink_to_fit();

   -7-Requires:T shall beMoveInsertable into*this.

   -?-Effects:shrink_to_fit is a non-binding request to reducecapacity() tosize(). [Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note] It does not increasecapacity(), but may reducecapacity() by causing reallocation. If an exception is thrown other than by the move constructor of a non-CopyInsertableT there are no effects.

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

   -9-Remarks:shrink_to_fit is a non-binding request to reducecapacity() tosize(). [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-CopyInsertableT 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.13.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. […]