Why is string::resize linear in complexity?

Question

The string needs to delete its old memory, then declare a new memory buffer, both of which are O(1) in complexity. The cplusplus.com reference says this is linear in time complexity of the new string length. Is this because the old string needs to be copied over? What if you start with an empty string?

Basically I want a string declared with a size n buffer, in O(1) time. Is this possible?

Answer 1

Every element of the new string is initialized, either by moving old elements, or by making copies of the second argument of std::string::resize (which defaults to CharT()).

Therefore the number of initializations is (new length).

One could imagine that for some future improved allocator that allowed in-place adjustment of a block size (like realloc from the C library), that the additional memory might be found contiguous to the old, and only max(0, (new length) - (old length)) initializations needed. But the current allocator scheme doesn't support such.

Answer 2

The string content also needs to be copied or initialized which, obviously, has a complexity linear in the new size of the string.