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

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

Section: 21.3.3.5 [string.capacity], 22.3.8.3 [deque.capacity], 22.3.10.3 [list.capacity], 22.3.11.3 [vector.capacity], 22.3.9.5 [forward.list.modifiers], 26.7.2.8 [valarray.members], 21.3.3.7.2 [string.append], 29.12.6.5.3 [fs.path.append] Status: Tentatively NAD Submitter: Louis Dionne Opened: 2021-08-11 Last modified: 2022-02-23

Priority: 3

View other active issues in [string.capacity].

View all other issues in [string.capacity].

View all issues with Tentatively 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 `𝒪(N2)`.

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:

- 21.3.3.5 [string.capacity]

- 22.3.8.3 [deque.capacity]

- 22.3.10.3 [list.capacity]

- 22.3.11.3 [vector.capacity]

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

- 22.3.9.5 [forward.list.modifiers]

- 26.7.2.8 [valarray.members]

The following classes have an `append()` member function:

- 21.3.3.7.2 [string.append]

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

Proposed resolution: