This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD status.

3579. Complexity guarantees for resize() and append() functions across the library

Section: 23.4.3.5 [string.capacity], 24.3.8.3 [deque.capacity], 24.3.10.3 [list.capacity], 24.3.11.3 [vector.capacity], 24.3.9.5 [forward.list.modifiers], 28.6.2.8 [valarray.members], 23.4.3.7.2 [string.append], 31.12.6.5.3 [fs.path.append] Status: NAD Submitter: Louis Dionne Opened: 2021-08-11 Last modified: 2022-08-23

Priority: 3

View all other issues in [string.capacity].

View all issues with NAD status.

Discussion:

This issue requests to clarify the complexity requirements for resize and append member functions across the library. Currently, none of them have complexity requirements associated to them, which means that implementations are free to use a geometric growth approach or not. A geometric growth approach (like what's required by push_back) implies that calling resize/append with successively larger sizes will have amortized 𝒪(N) complexity, whereas using a resize-exactly approach makes that pattern 𝒪(N²).

I believe the Standard should either specify that those member functions are required to have behavior that is consistent with push_back, or explicitly mention that implementations are allowed to use whatever growth strategy they want. If we do the former, users could start relying on this guarantee in a portable manner. If we do the latter, it would make it clear to users that they should not rely on the amortized 𝒪(N) guarantee if they want their code to be portable.

The following classes have a resize() member function and also a push_back() member function:

• 23.4.3.5 [string.capacity]

• 24.3.8.3 [deque.capacity]

• 24.3.10.3 [list.capacity]

• 24.3.11.3 [vector.capacity]

The following classes have a resize() member function but do not support push_back():

• 24.3.9.5 [forward.list.modifiers]

• 28.6.2.8 [valarray.members]

The following classes have an append() member function:

• 23.4.3.7.2 [string.append]

• 31.12.6.5.3 [fs.path.append]

None of them specify a complexity requirement. I think we should update all of them to describe what is expected or permitted in an implementation.

[2021-08-20; Reflector poll]

Set priority to 3 and status to "LEWG" after reflector poll.

[2022-02-22 LEWG telecon; Status changed: LEWG → Tentatively NAD.]

A paper would be needed. Such a paper would need to include discussion on whether allocate_at_least (new for C++23) has an impact.

[2022-08-23 Status changed: Tentatively NAD → NAD.]

Proposed resolution: