CODEWITHSUNDEEP
c++template-meta-programming
JohnB
JohnB

Reputation: 13713

Template library for string providing efficient concatenation

Is there an equivalent to the blitz++ library for strings (i.e. a library which improves performance of string construction/manipulation by delaying string building until the whole expression is read)?

Blitz++ improves the speed of matrix/vector operations by template metaprogramming, constructing a "syntax tree" at compile time from expressions like A + B + C and then evaluating the syntax tree. This method could, for example, improve the performance of string concatenation, since after having seen an expression like s1 + s2 + s3, the size of the result will be known, such that then memory allocation and copying can be done in one step, rather than first allocating memory for s1 + s2, copying, allocating memory for (s1 + s2) + s3, and then copying again.

Upvotes: 4

Views: 148

Answers (1)

rubenvb
rubenvb

Reputation: 76519

I know QString uses expression templates to determine the final string's size and efficiently allocates this beforehand. I think the underlying code isn't that hard, and could be made to work with most existing string classes. From the Qt 4.8 manual:

QStringBuilder uses expression templates and reimplements the '%' operator so that when you use '%' for string concatenation instead of '+', multiple substring concatenations will be postponed until the final result is about to be assigned to a QString. At this point, the amount of memory required for the final result is known. The memory allocator is then called once to get the required space, and the substrings are copied into it one by one.

Take a look at the wiki on the subject for an example on the technique.

Note that this does interfere with stuff like decltype(a+b) or auto c = a+b where the expression template operator+ is used, as the type returned is a proxy type, and not the original type of a or b.

Upvotes: 1

Related Questions