How is string pop_back implemented in constant time?
std::string pop_back()
: remove the last element of the line
The C ++ spec says that the C ++ 11 string class function pop_back has constant time complexity.
(more precisely - Unspecified, but usually permanent)
http://www.cplusplus.com/reference/string/string/pop_back/
Also, I read the draft of the C ++ 11 spec and it says what pop_back
is equal str.erase(str.length() -1)
. As far as I know, the erase function just allocates a new amount of memory and copies the remaining items (not deleted) into that memory, which will take up to linear time. In light of this, how can pop_back finish in constant time.
source to share
When it comes to "complexity", you should always look at the big picture, not just the individual case.
First, let's look at the growth of c push_back()
. If you grow from an empty container into one of the large Ns, the implementation will perform a series of reallocations. Each time this happens, the complexity will be O(M)
for whatever size it is at the time, but the rest of the iterations will be constant.
In fact, the difficulty will be the sum of a geometric progression. Let them say that he redistributes to double the capacity, and let him say that he starts at 16.
So the total for those redistributed would be:
16 + 32 + 64 + 128 + ... + N/2
(assuming N is a power of 2) which you know will add up to
N-16.
Add all those for which there is no reallocation and your grand sum is close to 2N
, so O(N)
for all inserts N
and therefore constant time to insert into the big picture, even if that particular one cannot be.
Now this is an example. Let's say we start with N
and make a large series of calls pop_back()
. Assuming it does the same thing in reverse order, it will have the same difficulty.
QED
Of course, there are more problems here. For example, pop_back
and erase
cannot be thrown away, i.e. Leaking exceptions, and reallocation even in a smaller buffer will first need to allocate more memory to move the data before releasing the old one, so an exception might be thrown doing this. However, an implementation can simply "try" the reallocation into a smaller buffer, and if an error occurs, catch it and then revert back to a simple "boolean" change. Of course, this means that your system is reaching full capacity, and that reducing the size of your lines is not helping.
The likelihood is that while it is open to implementation, most implementations never get redeployed to pop_back. The only time this can happen is if the string is implemented with an internal member buffer for small strings and this length has been reached, in which case there is no danger of moving all data into it and freeing up the "free storage" "Memory. This cannot quit.
source to share