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

Section: 27.4.3.5 [string.capacity], 23.3.11.3 [vector.capacity] Status: C++20 Submitter: Andy Giese Opened: 2017-07-24 Last modified: 2021-02-25

Priority: 0

View all other issues in [string.capacity].

View all issues with C++20 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. ]

[2018-3-17 Adopted in Jacksonville]

Proposed resolution:

This resolution is relative to N4659.

1. Edit 27.4.3.5 [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 23.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.