Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

std::string and its automatic memory resizing

I'm pretty new to C++, but I know you can't just use memory willy nilly like the std::string class seems to let you do. For instance:

std::string f = "asdf";
f += "fdsa";

How does the string class handle getting larger and smaller? I assume it allocates a default amount of memory and if it needs more, it news a larger block of memory and copies itself over to that. But wouldn't that be pretty inefficient to have to copy the whole string every time it needed to resize? I can't really think of another way it could be done (but obviously somebody did).

And for that matter, how do all the stdlib classes like vector, queue, stack, etc handle growing and shrinking so transparently?

like image 736
Thomas T. Avatar asked Aug 24 '10 14:08

Thomas T.


People also ask

Does std::string store size?

std::string actually maintains the size as one of its data member. Think of std::string as a container that keeps a pointer to the actual data(a char*) and length of that data separate.

Are C++ strings dynamically allocated?

Strings Are Dynamically Allocated To implement this flexibility, strings are allocated dynamically. Dynamic allocation is expensive compared to most other C++ features, so no matter what, strings are going to show up as optimization hot spots.

How does std::string allocate memory?

The standard library string functions allocate a smallish work buffer. If more space is needed, then the library reallocates to a larger buffer. It's just as simple as it sounds.

Does std::string allocate on heap?

The string object itself is stored on the stack but it points to memory that is on the heap.


2 Answers

Usually, there's a doubling algorithm. In other words, when it fills the current buffer, it allocates a new buffer that's twice as big, and then copies the current data over. This results in fewer allocate/copy operations than the alternative of growing by a single allocation block.

like image 100
Steven Sudit Avatar answered Oct 15 '22 17:10

Steven Sudit


Your analysis is correct — it is inefficient to copy the string every time it needs to resize. That's why common advice discourages that use pattern. Use the string's reserve function to ask it to allocate enough memory for what you intend to store in it. Then further operations will fill that memory. (But if your hint turns out to be too small, the string will still grow automatically, too.)

Containers will also usually try to mitigate the effects of frequent re-allocation by allocating more memory than they need. A common algorithm is that when a string finds that it's out of space, it doubles its buffer size instead of just allocating the minimum required to hold the new value. If the string is being grown one character at a time, this doubling algorithm reduces the time complexity to amortized linear time (instead of quadratic time). It also reduces the program's susceptibility to memory fragmentation.

like image 20
Rob Kennedy Avatar answered Oct 15 '22 17:10

Rob Kennedy