resize() and append() functions across the librarySection: 27.4.3.5 [string.capacity], 23.3.5.3 [deque.capacity], 23.3.9.3 [list.capacity], 23.3.11.3 [vector.capacity], 23.3.7.5 [forward.list.modifiers], 29.6.2.8 [valarray.members], 27.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 𝒪(N2).
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:
27.4.3.5 [string.capacity]
23.3.5.3 [deque.capacity]
23.3.9.3 [list.capacity]
23.3.11.3 [vector.capacity]
The following classes have a resize() member function but do not support push_back():
23.3.7.5 [forward.list.modifiers]
29.6.2.8 [valarray.members]
The following classes have an append() member function:
27.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: