Title
§[string.capacity] and §[vector.capacity] should specify time complexity for capacity()
Status
c++20
Section
[string.capacity][vector.capacity]
Submitter
Andy Giese

Created on 2017-07-24.00:00:00 last changed 23 months ago

Messages

Date: 2018-03-18.16:03:30

Proposed resolution:

This resolution is relative to N4659.

  1. Edit [string.capacity] as indicated:

    size_type capacity() const noexcept;
    

    -9- Returns: The size of the allocated storage in the string.

    -?- Complexity: Constant time.

  2. Edit [vector.capacity] as indicated:

    size_type capacity() const noexcept;
    

    -1- Returns: The total number of elements that the vector can hold without requiring reallocation.

    -?- Complexity: Constant time.

Date: 2018-03-17.00:00:00

[ 2018-3-17 Adopted in Jacksonville ]

Date: 2017-11-01.00:00:00

[ 2017-11-01 Moved to Tentatively Ready after 10 positive votes for P0 on c++std-lib. ]

Date: 2017-07-24.00:00:00

basic_string and vector both have a capacity function that returns the size of the internally allocated buffer. This function does not specify a time complexity nor does it have an implied time complexity. However, given the complexities for data() to be 𝒪(1) and size() to be 𝒪(1), we can imagine that it's reasonable to also require capacity() to be 𝒪(1), since the implementation will most likely be caching the size of the allocated buffer so as to check for the need to reallocate on insertion.

History
Date User Action Args
2021-02-25 10:48:01adminsetstatus: wp -> c++20
2018-03-18 16:03:30adminsetmessages: + msg9735
2018-03-18 16:03:30adminsetstatus: voting -> wp
2018-02-12 01:13:49adminsetstatus: ready -> voting
2017-11-01 18:09:14adminsetmessages: + msg9491
2017-11-01 18:09:14adminsetstatus: new -> ready
2017-07-29 20:17:38adminsetmessages: + msg9434
2017-07-24 00:00:00admincreate