C String Concatenation

C String Concatenation

	strcat (strcpy (d, s1), s2);

To perform the concatenation, one pass over s1 and one pass over s2 is all that is necessary in addition to the corresponding pass over d that happens at the same time, but the call above makes two passes over s1. Let's break up the calls into two statements.

        char *d1 = strcpy (d, s1); // pass 1 over s1
        strcat (d1, s2); // pass 2 over the copy of s1 in d

Because strcpy returns the value of its first argument, d, the value of d1 is the same as d. For simplicity, the examples that follow use d instead of storing the return value in d1 and using it. In the strcat call, determining the position of the last character involves traversing the characters just copied to d1. The cost of doing this is linear in the length of the first string, s1. The cost is multiplied with each appended string, and so tends toward quadratic in the number of concatenations times the lengths of all the concatenated strings. This inefficiency is so infamous to have earned itself a name: Schlemiel the Painter's algorithm. (See also 1.)

It's important to point out that in addition to being inefficient, strcat and strcpy are notorious for their propensity for buffer overflow because neither provides a bound on the number of copied characters.

Attempts to overcome limitations

When the lengths of the strings are unknown and the destination size is fixed, following some popular secure coding guidelines to constrain the result of the concatenation to the destination size would actually lead to two redundant passes. For example, following the CERT advisory on the safe uses of strncpy() and strncat() and with the size of the destination being dsize bytes, we might end up with the following code.

	strncpy (d, s1, dsize - 1);      // pass 1 over s1 plus over d up to dsize - 1
	d[dsize - 1] = '\0';             // remember to nul-terminate
	size_t n = strlen (d);           // pass 2 over copy of s1 in d
	strncat (d, s2, dsize - n - 1);  // pass 3 over copy of s1 in d

Note that unlike the call to strncat, the call to strncpy above does not append the terminating NUL character to d when s1 is longer than d's size. It's a common mistake to assume it does. In addition, when s1 is shorter than dsize - 1, the strncpy funcion sets all the remaining characters to NUL which is also considered wasteful because the subsequent call to strncat will end up overwriting them.

In a futile effort to avoid some of the redundancy, programmers sometimes opt to first compute the string lengths and then use memcpy as shown below. This approach, while still less than optimally efficient, is even more error-prone and difficult to read and maintain.