3004. §[string.capacity] and §[vector.capacity] should specify time complexity for capacity()

Section: 24.3.2.4 [string.capacity], 26.3.11.3 [vector.capacity] Status: Tentatively Ready Submitter: Andy Giese Opened: 2017-07-24 Last modified: 2017-11-01

Priority: 0

View other active issues in [string.capacity].

View all other issues in [string.capacity].

View all issues with Tentatively Ready status.

Discussion:

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.

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

Proposed resolution:

This resolution is relative to N4659.

  1. Edit 24.3.2.4 [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 26.3.11.3 [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.