3742. deque::prepend_range needs to permute

Section: 23.2.4 [sequence.reqmts] Status: C++23 Submitter: Casey Carter Opened: 2022-07-16 Last modified: 2023-11-22

Priority: 2

View other active issues in [sequence.reqmts].

View all other issues in [sequence.reqmts].

View all issues with C++23 status.

Discussion:

When the range to be inserted is neither bidirectional nor sized, it's simpler to prepend elements one at a time, and then reverse the prepended elements. When the range to be inserted is neither forward nor sized, I believe this approach is necessary to implement prepend_range at all — there is no way to determine the length of the range modulo the block size of the deque ahead of time so as to insert the new elements in the proper position.

The container requirements do not allow prepend_range to permute elements in a deque. I believe we must allow permutation when the range is neither forward nor sized, and we should allow permutation when the range is not bidirectional to allow implementations the freedom to make a single pass through the range.

[2022-07-17; Daniel comments]

The below suggested wording follows the existing style used in the specification of insert and insert_range, for example. Unfortunately, this existing practice violates the usual wording style that a Cpp17XXX requirement shall be met and that we should better say that "lvalues of type T are swappable (16.4.4.3 [swappable.requirements])" to be clearer about the specific swappable context. A separate editorial issue will be reported to take care of this problem.

[2022-08-23; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll.

Previous resolution [SUPERSEDED]:

This wording is relative to N4910.

  1. Modify 23.2.4 [sequence.reqmts] as indicated:

    a.prepend_range(rg)

    -94- Result: void

    -95- Preconditions: T is Cpp17EmplaceConstructible into X from *ranges::begin(rg). For deque, T is also Cpp17MoveInsertable into X, Cpp17MoveConstructible, Cpp17MoveAssignable, and swappable (16.4.4.3 [swappable.requirements]).

    -96- Effects: Inserts copies of elements in rg before begin(). Each iterator in the range rg is dereferenced exactly once.

    [Note 3: The order of elements in rg is not reversed. — end note]

    -97- Remarks: Required for deque, forward_list, and list.

[2022-11-07; Daniel reopens and comments]

The proposed wording has two problems:

  1. It still uses "swappable" instead of "swappable lvalues", which with the (informal) acceptance of P2696R0 should now become Cpp17Swappable.

  2. It uses an atypical form to say "T (is) Cpp17MoveConstructible, Cpp17MoveAssignable" instead of the more correct form "T meets the Cpp17MoveConstructible and Cpp17MoveAssignable requirements". This form was also corrected by P2696R0.

The revised wording uses the P2696R0 wording approach to fix both problems.

[Kona 2022-11-12; Set priority to 2]

[2022-11-30; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll.

[2023-02-13 Approved at February 2023 meeting in Issaquah. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4917 assuming that P2696R0 has been accepted.

  1. Modify 23.2.4 [sequence.reqmts] as indicated:

    a.prepend_range(rg)

    -94- Result: void

    -95- Preconditions: T is Cpp17EmplaceConstructible into X from *ranges::begin(rg). For deque, T is also Cpp17MoveInsertable into X, and T meets the Cpp17MoveConstructible, Cpp17MoveAssignable, and Cpp17Swappable (16.4.4.3 [swappable.requirements]) requirements.

    -96- Effects: Inserts copies of elements in rg before begin(). Each iterator in the range rg is dereferenced exactly once.

    [Note 3: The order of elements in rg is not reversed. — end note]

    -97- Remarks: Required for deque, forward_list, and list.