Efficient string concatenation in C++

Question

I heard a few people expressing worries about "+" operator in std::string and various workarounds to speed up concatenation. Are any of these really necessary? If so, what is the best way to concatenate strings in C++?

Flatiron

Basically the + is NOT a concatentation operator (as it generates a new string). Use += for concatenation. – Telluric

Since C++11, there's an important point: operator+ can modify one of its operands & return it by-move if that operand was passed by rvalue reference. libstdc++ does this, for example. So, when calling operator+ with temporaries, it can achieve almost-as-good performance - perhaps an argument in favour of defaulting to it, for the sake of readability, unless one has benchmarks showing it is a bottleneck. However, a Standardised variadic append() would be both optimal and readable... – Contrary

Answer 1

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.

Equalitarian

Note: "STL" refers to a completely separate open-source library, originally by HP, some part of which were used as a basis for parts of the ISO Standard C++ Library. "std::string", however, was never part of HP's STL, so it's completely wrong to reference "STL and "string" together. – Effectuate

I wouldn't say it's wrong to use STL and string together. See sgi.com/tech/stl/table_of_contents.html – Equalitarian

When SGI took over maintenance of the STL from HP, it was retro-fitted to match the Standard Library (which is why I said "never part of HP's STL"). Nevertheless, the originator of std::string is the ISO C++ Committee. – Effectuate

Side note: The SGI employee who was in charge of maintaining the STL for many years was Matt Austern, who, at the same time, headed the Library subgroup of the ISO C++ Standardization Committee. – Effectuate

operator+ creates a new buffer which is slow but if you do x = x + y (where x and y are both std::string) you may get an additional string buffer copy in the operator=! ("may" means that there may be std::string implementations that share buffers). – Glossology

@Brian R. Bondy: "You can see that a new object is returned after each + ..." I am not sure I can "see". Is it because the function arguments are const while the return type is not? – Expansible

Can you please clarify or give some points to why You can use the stack for your buffers instead of the heap which is much more efficient.? Where does this efficiency difference comes from? – Pieter

@Pieter I think that's just badly explained, almost to the point that it should be edited out. Using .reserve() and .append() avoid extra heap allocations for temporaries from operator+, by ensuring the new contents are copied into the existing buffer of the destination string. However, that buffer may well already be on the heap, if the string is too long for the small-string optimisation (or the stdlib implementation, for whatever reason, doesn't use SSO). And merely being on the heap doesn't inherently make any difference to efficiency: it's allocating from the heap that's costly – Contrary

Since C++11, this misses an important point: operator+ can modify one of its operands & return it by-move if that operand was passed by rvalue reference. libstdc++ does this, for example. So, when calling operator+ with temporaries, it can achieve almost-as-good performance - perhaps an argument in favour of defaulting to it, for the sake of readability, unless one has benchmarks showing it is a bottleneck. However, a Standardised variadic append() would be optimal and readable... – Contrary

Note: dead link to "rope data structure". Here's the Wikipedia article: en.wikipedia.org/wiki/Rope_(data_structure) – Kayo

Answer 2

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);
}

Essex

A million? When are strings ever a million characters? – Highwrought

Answer 3

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.

Fiber

I had to check stdlib implementors really do this. :P libstdc++ for operator+(string const& lhs, string&& rhs) does return std::move(rhs.insert(0, lhs)). Then if both are temporaries, its operator+(string&& lhs, string&& rhs) if lhs has sufficient capacity available will just directly append(). Where I think this risks being slower than operator+= is if lhs does not have enough capacity, as then it falls back to rhs.insert(0, lhs), which not only must extend the buffer & add the new contents like append(), but also needs to shift along the original contents of rhs right. – Contrary

The other piece of overhead compared to operator+= is that operator+ still must return a value, so it has to move() whichever operand it appended to. Still, I guess that's a fairly minor overhead (copying a couple of pointers/sizes) compared to deep-copying the entire string, so it's good! – Contrary

Answer 4

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).

Lifeblood

I'm not quite sure why this was downvoted. The 50% figure is not required by the Standard, but IIRC that or 100% are common measures of growth in practice. Everything else in this answer seems unobjectionable. – Contrary

Months later, I suppose it's not all that accurate, since it was written long after C++11 debuted, and overloads of operator+ where one or both arguments is passed by rvalue reference can avoid allocating a new string altogether by concatenating into the existing buffer of one of the operands (albeit they might have to realloc if it has insufficient capacity). – Contrary

Answer 5

For most applications, it just won't matter. Just write your code, blissfully unaware of how exactly the + operator works, and only take matters into your own hands if it becomes an apparent bottleneck.

Tricostate

Of course it's not worth it for most cases, but this doesn't really answer his question. – Equalitarian

yeah. i agree just saying "profile then optimize" can be put as comment on the question :) – Fiber

Fair enough, but it is definitely needed for some applications. So in those applications the answer reduces to: 'take matters into your own hands' – Equalitarian

Sorry to be so critical. I just thought an explanation of why operator+ was not efficient would be needed for him to determine if in his case he needed to do it. – Equalitarian

Marking down as it doesn't answer the question – Stillas

@Tricostate There's a perverted notion in the programming world that performance doesn't matter and we can just ignore the whole deal because computers keep getting faster. The thing is, that's not why people program in C++ and that's not why they post questions on stack overflow about efficient string concatenation. – Jamima

Answer 6

perhaps std::stringstream instead?

But I agree with the sentiment that you should probably just keep it maintainable and understandable and then profile to see if you are really having problems.

Storiette

stringstream is slow, see groups.google.com/d/topic/comp.lang.c++.moderated/aiFIGb6za0w – Symons

@Symons stringstream may be fast, see codeproject.com/Articles/647856/… – Karyoplasm

Answer 7

Unlike .NET System.Strings, C++'s std::strings are mutable, and therefore can be built through simple concatenation just as fast as through other methods.

Effectuate

Especially if you use reserve() to make the buffer big enough for the result before you start. – Jarlathus

i think he is talking about operator+= . it's also concatenating, although it's a degenerate case. james was a vc++ mvp so i expect he has some clue of c++ :p – Fiber

I don't doubt for a second that he has extensive knowledge on C++, just that there was a misunderstanding about the question. The question asked about the efficiency of operator+ which returns new string objects each time it is called, and hence uses new char buffers. – Equalitarian

yeah. but then he asked for the case operator+ is slow, what the best way is to do a concatenation. and here operator+= comes into game. but i agree james' answer is a little short. it makes it sound like we all could use operator+ and it's top efficient :p – Fiber

@BrianR.Bondy operator+ does not have to return a new string. Implementors can return one of its operands, modified, if that operand was passed by rvalue reference. libstdc++ does this, for example. So, when calling operator+ with temporaries, it can achieve the same or almost as good performance - which might be another argument in favour of defaulting to it unless one has benchmarks showing that it represents a bottleneck. – Contrary

Answer 8

In Imperfect C++, Matthew Wilson presents a dynamic string concatenator that pre-computes the length of the final string in order to have only one allocation before concatenating all parts. We can also implement a static concatenator by playing with expression templates.

That kind of idea have been implemented in STLport std::string implementation -- that does not conform to the standard because of this precise hack.

Overdone

Glib::ustring::compose() from the glibmm bindings to GLib does that: estimates and reserve()s the final length based upon the provided format string and the varargs, then append()s each (or its formatted replacement) in a loop. I expect this is a pretty common way of working. – Contrary

Answer 9

For small strings it doesn't matter. If you have big strings you'd better to store them as they are in vector or in some other collection as parts. And addapt your algorithm to work with such set of data instead of the one big string.

I prefer std::ostringstream for complex concatenation.

Kallick

what is a complex concatenation? – Yellows

Answer 10

As with most things, it's easier not to do something than to do it.

If you want to output large strings to a GUI, it may be that whatever you're outputting to can handle the strings in pieces better than as a large string (for example, concatenating text in a text editor - usually they keep lines as separate structures).

If you want to output to a file, stream the data rather than creating a large string and outputting that.

I've never found a need to make concatenation faster necessary if I removed unnecessary concatenation from slow code.

Mebane

Answer 11

Probably best performance if you pre-allocate (reserve) space in the resultant string.

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Usage:

std::string merged = concat("This ", "is ", "a ", "test!");

Ping

Answer 12

A simple array of characters, encapsulated in a class that keeps track of array size and number of allocated bytes is the fastest.

The trick is to do just one large allocation at start.

at

https://github.com/pedro-vicente/table-string

Benchmarks

For Visual Studio 2015, x86 debug build, substancial improvement over C++ std::string.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |  

Millen

The OP is interested in how to efficiently concatenate std::string. They are not asking for an alternative string class. – Contrary

Answer 13

You can try this one with memory reservations for each item:

namespace {
template<class C>
constexpr auto size(const C& c) -> decltype(c.size()) {
  return static_cast<std::size_t>(c.size());
}

constexpr std::size_t size(const char* string) {
  std::size_t size = 0;
  while (*(string + size) != '\0') {
    ++size;
  }
  return size;
}

template<class T, std::size_t N>
constexpr std::size_t size(const T (&)[N]) noexcept {
  return N;
}
}

template<typename... Args>
std::string concatStrings(Args&&... args) {
  auto s = (size(args) + ...);
  std::string result;
  result.reserve(s);
  return (result.append(std::forward<Args>(args)), ...);
}

Sulfaguanidine

Answer 14

Benchmark as per Visual Studio C/C++ 17.2.5 and Boost 1.79.0 on Ryzen 5600x:

n iter = 10
n parts = 10000000
total string result length = 70000000
Boost join: 00:00:02.105006
std::string append (Reserve): 00:00:00.485498
std::string append (simple): 00:00:00.679999
Note: times are cumulative sums over all iterations.

Conclusion: boost implementation not very good regarding performance. Using std::string's reserve not too impactful unless the final string length is at least around multiple tens of megabytes.

The simple append (without reserve) might even be faster in practice because the benchmark used an already initialized vector of string parts. In practice, that vector is often only necessary for the reserve/boost join variant and therefore an additional performance penalty for them.

Another run:

n iter = 100
n parts = 1000000
total string result length = 6000000
Boost join: 00:00:01.953999
std::string append (Reserve): 00:00:00.535502
std::string append (simple): 00:00:00.679002
Note: times are cumulative sums over all iterations.

Center