Error joining strings in C++

Question

I'm trying to join all strings contained in an array in one single string so I've come up with this code:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

char *join_strings(const char *array[])
{
    int n_array (sizeof (array) / sizeof (const char *));

    int i;
    int total_length;
    char *joined;
    char *end;
    int *lengths;

    lengths = (int *)malloc (n_array * sizeof (int));
    if (!lengths) {
        fprintf (stderr, "Malloc failed.\n");
        exit (EXIT_FAILURE);
    }

    total_length = 0;

    for (i = 0; i < n_array; i++) {
        lengths[i] = strlen (array[i]);
        total_length += lengths[i];
    }

    joined = (char *)malloc(total_length + 1);

    if (!joined) {
        fprintf (stderr, "Malloc failed.\n");
        exit (EXIT_FAILURE);
    }

    end = joined;

    for (i = 0; i < n_array; i++) {
        int j;
        for (j = 0; j < lengths[i]; j++) {
            end[j] = array[i][j];
        }
        end += lengths[i];
    }
    end[total_length] = '\0';

    char *result = joined;

    free (lengths);
    free (joined);

    return result;
}

int main()
{
    const char *lol0 = "First";
    const char *lol1 = "Second";
    const char *fullString[] = { lol0, lol1 };
    const char *joined = join_strings(fullString);

    puts(joined);

    return 0;
}

But for some reason it only output "First", don't know the problem might be. :/ Thanks in advance!

Answer 1

sizeof(array) equals to sizeof(const char **) and n_array isn't accurately calculated.
You will have to pass the length of array as an argument.

There is another error. You must not do free (joined); in function join_strings since the buffer is still used.

Fixed code:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

char *join_strings(const char *array[], int n_array)
{

    int i;
    int total_length;
    char *joined;
    char *end;
    int *lengths;

    lengths = malloc (n_array * sizeof (int));
    if (!lengths) {
        fprintf (stderr, "Malloc failed.\n");
        exit (EXIT_FAILURE);
    }

    total_length = 0;

    for (i = 0; i < n_array; i++) {
        lengths[i] = strlen (array[i]);
        total_length += lengths[i];
    }

    joined = malloc(total_length + 1);

    if (!joined) {
        fprintf (stderr, "Malloc failed.\n");
        exit (EXIT_FAILURE);
    }

    end = joined;

    for (i = 0; i < n_array; i++) {
        int j;
        for (j = 0; j < lengths[i]; j++) {
            end[j] = array[i][j];
        }
        end += lengths[i];
    }
    end[total_length] = '\0';

    char *result = joined;

    free (lengths);

    return result;
}

int main()
{
    const char *lol0 = "First";
    const char *lol1 = "Second";
    const char *fullString[] = { lol0, lol1 };
    char *joined = join_strings(fullString, 2);

    puts(joined);
    free(joined);

    return 0;
}

Notes:

• This code is C, not C++. I removed casts for the return value of malloc, which seems to be hated in this site. This will lead to compile error in C++.
• to free the buffer, the type of joined in the main function shouldn't be const char*. gcc made warnings for it.

Answer 2

It's hard to be absolutely sure, but it's possible that performance-wise the win from knowing the lengths is less than the cost of allocating heap memory just to hold string lengths.

So, let's do it without that extra length-buffering, for fun:

char * join_strings(const char *array, size_t array_len)
{
  size_t out_len;

  for(size_t i = out_len = 0; i < array_len; ++i)
    out_len += strlen(array[i]);

  char *out = malloc(out_len + 1);
  if(out != NULL)
  {
    char *put = out;
    for(size_t i = 0; i < array_len; ++i)
    {
      for(const char *src = array[i]; *src;)
        *put++ = *src++;
    }
    *put = '\0';
  }
  return out;
}

The above is C99, by the way. I removed the error message, returning NULL might be enough. It's not tested, but shouldn't be too far from correct. :)

My point is basically that sometimes shorter code is easier to work with.

Answer 3

As indicated by MikeCAT, the following does not do what you think it is doing... but Why?

char *join_strings(const char *array[])
{
    int n_array (sizeof (array) / sizeof (const char *));

You are passing *fullString[] to your join_strings function, but what join_strings gets is effectively **fulString due to pointer decay. Any time you pass an array to a function (e.g. a[]) it will decay to a pointer (e.g. *a). The same is true for an array of pointers.

That is precisely the reason you see the main function syntax as:

int main (int argc, char *argv[])

or

int main (int argc, char **argv)

In fact, what main receives is the second case, but the syntax allowed is either. So when you pass *fullString[] to your join_strings function, pointer decay insures that join_strings receives **fullString. That makes the following:

    int n_array (sizeof (array) / sizeof (const char *));

effectively int n_array 8/8 or 1. The sizeof array / sizeof *array only works in the scope where array is declared and defined. Once you pass it to another function, pointer decay renders it incorrect.

However, your code is not far off otherwise. There were a few changes to make, but other than this bit of learning that was needed, you were close to a working string concatenation:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

char *join_strings (const char **array, size_t n_array)
{
    // int n_array (sizeof (array) / sizeof (const char *));

    size_t i;
    size_t total_length;
    char *joined;
    char *end;
    size_t *lengths;

    // lengths = (int *) malloc (n_array * sizeof (int));
    lengths = malloc (n_array * sizeof *lengths);
    if (!lengths) {
        fprintf (stderr, "Malloc failed.\n");
        exit (EXIT_FAILURE);
    }

    total_length = 0;

    for (i = 0; i < n_array; i++) {
        lengths[i] = strlen (array[i]);
        total_length += lengths[i];
    }

    joined = malloc (total_length + 1);

    if (!joined) {
        fprintf (stderr, "Malloc failed.\n");
        exit (EXIT_FAILURE);
    }

    end = joined;

    for (i = 0; i < n_array; i++) {
        size_t j;
        for (j = 0; j < lengths[i]; j++) {
            end[j] = array[i][j];
        }
        end += lengths[i];
    }
    // end[total_length] = '\0';   /* ALWAYS run valgrind (Note3) */
    joined[total_length] = '\0';

    // char *result = joined;

    free (lengths);
    // free (joined);

    return joined;
}

int main ()
{
    const char *lol0 = "First";
    const char *lol1 = "Second";
    const char *fullString[] = { lol0, lol1 };
/*const */char *joined = join_strings (fullString, sizeof fullString/sizeof *fullString);

    puts (joined);
    free (joined);

    return 0;
}

Note the change from int to size_t in your function for all your length and counter variables. You need to try and match your types to the actual ranges of numbers they will hold. Since there is no negative-length and you are only using positive counters to count up, size_t will help the compiler warn you when you might be trying to use the variables incorrectly.

Note2: don't cast the return on malloc. It is nothing more than the address to the start of a memory block. It doesn't have a type. Casting malloc provides zero benefit, but can mask errors or warnings the compiler would otherwise generate to warn you when you are about to do something dumb.

Note3: If you are allocating memory dynamically Always run your code through valgrind to insure you are using the memory properly. There is no excuse not to, it is dead-bang easy:

valgrind ./myprogname

It not only checks your allocations and frees, but it also check whether you attempt to access memory outside your allocated blocks. (if you compile with symbols enabled -g valgrind will show you the line numbers associated with the errors) Here valgrind shows:

==27700== Invalid write of size 1
==27700==    at 0x40090E: join_strings (ptrdecay.c:45)
==27700==    by 0x400960: main (ptrdecay.c:60)
==27700==  Address 0x51e00a6 is 10 bytes after a block of size 12 alloc'd
==27700==    at 0x4C29964: calloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==27700==    by 0x400838: join_strings (ptrdecay.c:29)
==27700==    by 0x400960: main (ptrdecay.c:60)

Huh? Look closely at how your were attempting to null-terminate end. What is the value of end at that time? Where does end[total_length] (or equivalently written *(end + total_length) ) put that null-terminator?

==27700==  Address 0x51e00a6 is 10 bytes after a block of size 12 alloc'd

There is one other warning you should fix, either by using calloc for joined or initializing its values to 0 before filling them. That is all valgrind is complaining about in:

==27647== Conditional jump or move depends on uninitialised value(s)
==27647==    at 0x4C2ACF8: strlen (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==27647==    by 0x4E9DE2B: puts (in /lib64/libc-2.18.so)
==27647==    by 0x40092B: main (ptrdecay.c:62)

The easiest way to eliminate this message is with:

    joined = calloc (1, total_length + 1);

Try it and see... When you fix all the issues and run valgrind again, you will see what you want to see everytime:

$ valgrind ./bin/ptrdecay
==27821== Memcheck, a memory error detector
==27821== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==27821== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==27821== Command: ./bin/ptrdecay
==27821==
FirstSecond
==27821==
==27821== HEAP SUMMARY:
==27821==     in use at exit: 0 bytes in 0 blocks
==27821==   total heap usage: 2 allocs, 2 frees, 28 bytes allocated
==27821==
==27821== All heap blocks were freed -- no leaks are possible
==27821==
==27821== For counts of detected and suppressed errors, rerun with: -v
==27821== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

Answer 4

Firstly, this code is horrible - all this manual malloc and bare const char * arrays are very poor style.

Secondly, you're just passing the address of the first array element. Despite the misleading [], both C and C++ decay the argument to a pointer in this case, and the array size information is lost.

However, if your array size is genuinely a compile-time constant rather than being dynamically allocated, it is possible to make this work without changing your effective interface:

template <size_t n_array>
char *join_strings(const char *(&array)[n_array])
{
    // other ghastly code omitted for aesthetic reasons
}

will be callable exactly as shown and (once you fix the double free bug) actually work.

A minimal solution in actual C++ would instead be:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <sstream>
#include <vector>

template <typename InputIterator>
std::string join_strings(InputIterator begin, InputIterator end) {
    std::ostringstream os;
    std::copy(begin, end, std::ostream_iterator<std::string>(os));
    return os.str();
}

int main() {
    std::vector<std::string> arr = {"First","Second"};
    std::string joined = join_strings(begin(arr), end(arr));
    std::cout << joined << '\n';
}

This will have some redundant allocations, but is actually correct, and just as importantly is vastly simpler. If you profile and genuinely need more speed, replace the ostringstream with a pre-sized std::string and append to it.