deque::prepend_range needs to permute
Casey Carter

Created on 2022-07-16.00:00:00 last changed 4 weeks ago


Date: 2022-07-17.07:07:15

Proposed resolution:

This wording is relative to N4910.

  1. Modify [sequence.reqmts] as indicated:


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

Date User Action Args
2022-07-17 07:07:15adminsetmessages: + msg12601
2022-07-16 19:03:33adminsetmessages: + msg12600
2022-07-16 00:00:00admincreate