CODEWITHSUNDEEP
c++stringg++capacity
sleepsort
sleepsort

Reputation: 1331

c++ string capacity change during copy assignment

In the C++ Standard std:string follows an exponential growth policy, therefore I suppose the capacity() of string during concatenation will always be increased when necessary. However, when I test test.cpp, I found that in the for-loop, only every two times will the capacity() be shrunk back to length() during assignment.

Why isn't this behavior depending on the length of string, but depending on how frequent I change the string? Is it some kind of optimization?

The following codes are tested with g++ -std=c++11.

test.cpp: 

#include <iostream>  
int main(int argc, char **argv) {
  std::string s = "";
  for (int i = 1; i <= 1000; i++) {
    //s += "*";
    s = s + "*";
    std::cout << s.length() << " " << s.capacity() << std::endl;
  }
  return 0;
}

And the output will be like this: 

1 1
2 2
3 4
4 4
5 8
6 6    // why is capacity shrunk?
7 12
8 8    // and again?
9 16
10 10  // and again?
11 20
12 12  // and again?
13 24
14 14  // and again?
15 28
16 16  // and again?
17 32
...
996 996
997 1992
998 998  // and again?
999 1996
1000 1000  // and again?

Upvotes: 1

Views: 962

Answers (2)

M.M
M.M

Reputation: 141544

It's actually not convered by the C++ standard what happens to capacity() when strings are moved, assigned, etc. This could be a defect. The only constraints are those derivable from the time complexity specified for the operation.

See here for similar discussion about vectors.

Upvotes: 1

abarnert
abarnert

Reputation: 365617

When you do this:

s = s + "*";

You're doing two separate things: making a new temporary string, consisting of "*" concatenated onto the end of the contents s, and then copy-assigning that new string to s.

It's not the + that's shrinking, it's the =. When copy-assigning from one string to another, there's no reason to copy the capacity, just the actual used bytes.

Your commented-out code does this:

s += "*";

… is only doing one thing, appending "*" onto the end of s. So, there's nowhere for the "optimization" to happen (if it happened, it would be a pessimization, defeating the entire purpose of the exponential growth).

Upvotes: 2

Related Questions