3732. prepend_range and append_range can't be amortized constant time

Section: 23.2.4 [sequence.reqmts] Status: C++23 Submitter: Tim Song Opened: 2022-07-06 Last modified: 2023-11-22

Priority: Not Prioritized

View other active issues in [sequence.reqmts].

View all other issues in [sequence.reqmts].

View all issues with C++23 status.

Discussion:

23.2.4 [sequence.reqmts]/69 says "An implementation shall implement them so as to take amortized constant time." followed by a list of operations that includes the newly added append_range and prepend_range. Obviously these operations cannot be implemented in amortized constant time.

Because the actual complexity of these operations are already specified in the concrete container specification, we can just exclude them here.

[2022-08-23; Reflector poll]

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

[2022-11-12 Approved at November 2022 meeting in Kona. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4910.

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

   -69- The following operations are provided for some types of sequence containers but not others. An implementation shall implement themOperations other than prepend_range and append_range are implemented so as to take amortized constant time.