Title
Complexity guarantees for resize() and append() functions across the library
Status
lewg
Section
[string.capacity][deque.capacity][list.capacity] [vector.capacity][forward.list.modifiers][valarray.members] [string.append][fs.path.append]
Submitter
Louis Dionne

Created on 2021-08-11.00:00:00 last changed 1 month ago

Messages

Date: 2021-08-15.00:00:00

[ 2021-08-20; Reflector poll ]

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

Date: 2021-08-11.00:00:00

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:

  • [string.capacity]

  • [deque.capacity]

  • [list.capacity]

  • [vector.capacity]

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

  • [forward.list.modifiers]

  • [valarray.members]

The following classes have an append() member function:

  • [string.append]

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

History
Date User Action Args
2021-08-20 17:10:36adminsetmessages: + msg11990
2021-08-20 17:10:36adminsetstatus: new -> lewg
2021-08-11 00:00:00admincreate