Comment by bruce343434
14 hours ago
Maybe I'm missing something, but I thought that when you "grow" an array or a string, eventually something under the hood needs to call realloc()? which allocates a bigger chunk of memory and copies the content O(n)? Why would it matter if you manually do alloc() and then memcpy() (replacing an immutable string with its concatenation) vs letting the runtime do it for you with realloc()?
There are two differences.
① A growable string type overallocates, so you only eventually need to reallocate. An immutable string type has an exact-size allocation, so you must make a new allocation every time.
② An immutable string type can’t use realloc() anyway unless you can prove nothing else holds a reference to it, it needs to use a new malloc().