char*/string concatenation without copying?

Question

I would like to concatenate 2 strings in C or C++ without new memory allocation and copying. Is it possible?

Possible C code:

char* str1 = (char*)malloc(100);
char* str2 = (char*)malloc(50);
char* str3 = /* some code that concatenates these 2 strings
                without copying to occupy a continuous memory region */

Then, when I don't need them any more, I just do:

free(str1);
free(str2);

Or if possible, I would like to achieve the same in C++, using std::string or maybe char*, but using new and delete (possibly void operator delete ( void* ptr, std::size_t sz ) operator (C++14) on the str3).

There are a lot of questions about strings concatenation, but I haven't found one that asks the same.

Answer 1

No, it is not possible

In C, malloc operations return blocks of memory that have no relationship to each other. But in C, strings must be a continuous array of bytes. So there is no way to extend str1 without copying, let alone concatenate.

For C++, perhaps ropes may be of interest: See this answer.

Ropes are allocated in chunks that do not have to be contiguous. This supports O(1) concatenation. However, the accessors make it appear as a single string of bytes. I'm certain that to convert ropes back to std::string or C style strings will take a copy however, but this is probably the closest to what you want.

Also, it is probably a premature optimization to worry about the costs of copying a few strings around. Unless you are moving lots of data, it won't matter

Answer 2

Text concatenation is possible by writing your own string data structure. Easier in C++ than C.

struct My_String
{
  std::vector<char *> text_fragments;
};

You would have to implement all the text manipulation and searching algorithms based on this data structure. Nothing in the C library could be applied to the My_String structure. The std::string in C++ would not be compatible.

One of the issues is how to handle text modification. If one of the text fragments is a constant literal (that can't be modified), it would need to be copied before it could be modified. But copying is against the requirements. :-(

Answer 3

A "string" in C is a an array of chars with a null char at the end. And an array is "a data structure that lets you store one or more elements consecutively in memory". GNU C reference

You cannot concatenate two arrays that are not in consecutive memory blocks without copying one of them. You can do it however without allocating new memory. E.g.

char* str1 = malloc(100);  // size 100 bytes, uninitialised
str1[0] = '\0';            // string length 0, size of str1 100
strcat(str1, "a");         // string length 1, size of str1 still 100
strcat(str1, "b");         // string length 2, size of str1 still 100

You could if you want retrieve chars of 2 strings as if they were one without copying or reallocating. Here is an example function to do that (simple example, don't use in production code)

char* str1 = (char*)malloc(100);
char* str2 = (char*)malloc(50);

char get_char(int i) {
    if (i > 0 && i < 100) {
        return str1[i];
    }
    if (i >= 100 && i < 150) {
        return str2[i-100];
    }
    return 0;
}

But in such a case you couldn't have a char* str3 to perform pointer arithmetic with and access all 150 chars.

Answer 4

Tags C and C++ are contradictory. In C, I'd recommend exploring realloc. You can code something along following lines:

char* str = malloc(50);
str = realloc(ptr, 55);

If you are lucky, the realloc call will not reallocate new memory and just 'extened' the already allocated segment, but there is no guarantee for this. This way you at at least have a shot of avoiding reallocations of the string. You will still have to copy contents of the second string into neweley allocated memory.