Efficient string concatenation in C++

std::string operator+ allocates a new string and copies the two operand strings every time. repeat many times and it gets expensive, O(n).

std::string append and operator+= on the other hand, bump the capacity by 50% every time the string needs to grow. Which reduces the number of memory allocations and copy operations significantly, O(log n).

I would not worry about it. If you do it in a loop, strings will always preallocate memory to minimize reallocations - just use operator+= in that case. And if you do it manually, something like this or longer

a + " : " + c

Then it's creating temporaries - even if the compiler could eliminate some return value copies. That is because in a successively called operator+ it does not know whether the reference parameter references a named object or a temporary returned from a sub operator+ invocation. I would rather not worry about it before not having profiled first. But let's take an example for showing that. We first introduce parentheses to make the binding clear. I put the arguments directly after the function declaration that's used for clarity. Below that, i show what the resulting expression then is:

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

Now, in that addition, tmp1 is what was returned by the first call to operator+ with the shown arguments. We assume the compiler is really clever and optimizes out the return value copy. So we end up with one new string that contains the concatenation of a and " : ". Now, this happens:

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Compare that to the following:

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

It's using the same function for a temporary and for a named string! So the compiler has to copy the argument into a new string and append to that and return it from the body of operator+. It cannot take the memory of a temporary and append to that. The bigger the expression is, the more copies of strings have to be done.

Next Visual Studio and GCC will support c++1x's move semantics (complementing copy semantics) and rvalue references as an experimental addition. That allows figuring out whether the parameter references a temporary or not. This will make such additions amazingly fast, as all the above will end up in one "add-pipeline" without copies.

If it turns out to be a bottleneck, you can still do

 std::string(a).append(" : ").append(c) ...

The append calls append the argument to *this and then return a reference to themselves. So no copying of temporaries is done there. Or alternatively, the operator+= can be used, but you would need ugly parentheses to fix precedence.

The extra work is probably not worth it, unless you really really need efficiency. You probably will have much better efficiency simply by using operator += instead.

Now after that disclaimer, I will answer your actual question...

The efficiency of the STL string class depends on the implementation of STL you are using.

You could guarantee efficiency and have greater control yourself by doing concatenation manually via c built-in functions.

Why operator+ is not efficient:

Take a look at this interface:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

You can see that a new object is returned after each +. That means that a new buffer is used each time. If you are doing a ton of extra + operations it is not efficient.

Why you can make it more efficient:

• You are guaranteeing efficiency instead of trusting a delegate to do it efficiently for you
• the std::string class knows nothing about the max size of your string, nor how often you will be concatenating to it. You may have this knowledge and can do things based on having this information. This will lead to less re-allocations.
• You will be controlling the buffers manually so you can be sure that you won't copy the whole string into new buffers when you don't want that to happen.
• You can use the stack for your buffers instead of the heap which is much more efficient.
• string + operator will create a new string object and return it hence using a new buffer.

Considerations for implementation:

• Keep track of the string length.
• Keep a pointer to the end of the string and the start, or just the start and use the start + the length as an offset to find the end of the string.
• Make sure the buffer you are storing your string in, is big enough so you don't need to re-allocate data
• Use strcpy instead of strcat so you don't need to iterate over the length of the string to find the end of the string.

Rope data structure:

If you need really fast concatenations consider using a rope data structure.

Reserve your final space before, then use the append method with a buffer. For example, say you expect your final string length to be 1 million characters:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}