Search code examples
c++stringc++11erase

How string pop_back is implemented in constant time?

std::string pop_back() : Remove the last element of the string

In the C++ specification it is said that the C++11 string class function pop_back has a constant time complexity.

(to be more precise - Unspecified but generally constant)

http://www.cplusplus.com/reference/string/string/pop_back/

Apart from that I read the draft of C++11 specification and it is said that pop_back is equal to str.erase(str.length() -1). As far as I know the erase function simply allocates a new amount of memory and copies the remaining elements (not deleted) to this memory which will take up to linear time. In the light of this how can the pop_back finish in constant time.

Solution

  • It does not have to reallocate.

    The function probably just overwrites the last character with a zero and decrements some length information.