Title
deque::prepend_range needs to permute
Status
ready
Section
[sequence.reqmts]
Submitter
Casey Carter

Created on 2022-07-16.00:00:00 last changed 6 days ago

Messages

Date: 2022-11-30.09:50:57

Proposed resolution:

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

  1. Modify [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 ([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.

Date: 2022-11-15.00:00:00

[ 2022-11-30; Reflector poll ]

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

Date: 2022-11-12.01:08:30

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

Date: 2022-11-15.00:00:00

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

Date: 2022-08-15.00:00:00

[ 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 [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 ([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.

Date: 2022-07-15.00:00:00

[ 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 ([swappable.requirements])" to be clearer about the specific swappable context. A separate editorial issue will be reported to take care of this problem.

Date: 2022-07-16.00:00:00

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.

History
Date User Action Args
2022-11-30 09:50:57adminsetmessages: + msg13124
2022-11-30 09:50:57adminsetstatus: open -> ready
2022-11-12 01:08:30adminsetmessages: + msg13034
2022-11-07 17:58:25adminsetmessages: + msg12950
2022-11-07 17:58:25adminsetstatus: ready -> open
2022-08-23 15:24:34adminsetmessages: + msg12691
2022-08-23 15:24:34adminsetstatus: new -> ready
2022-07-17 07:07:15adminsetmessages: + msg12601
2022-07-16 19:03:33adminsetmessages: + msg12600
2022-07-16 00:00:00admincreate