C: Каков наилучший и быстрый способ конкатенации строк

Ответ 1

Джоэл Спольский в своей статье

Это не проблема переходить по первой строке в первый раз; поскольку мы уже прошли по второй строке, время выполнения одного strcat является линейным по длине результата. Несколько strcat проблематично, потому что мы снова и снова переходим к ранее конкатенированным результатам. Он предоставляет эту альтернативу:

Как мы это исправим? Несколько программистов на смарт-С реализовали свои собственные mystrcat следующим образом:

char* mystrcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
     return --dest;
}

Что мы здесь сделали? За очень небольшую дополнительную плату мы возвращаем указатель на конец новой длинной строки. Таким образом, код, который эта функция может решить добавить дальше без повторного сканирования строка:

char bigString[1000];     /* I never know how much to allocate... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

Это, конечно, линейный по производительности, а не n-квадрат, поэтому он не страдает от деградации, когда у вас много материала для конкатенации.

Конечно, это то, что вы можете сделать, если хотите использовать стандартные строки C. Альтернативой, которую вы описываете для кеширования длины строки и использования специальной функции конкатенации (например, вызов strcat с несколько разными аргументами), является разновидностью вариации на строках Паскаля, которую Джоэл также упомянул:

Дизайнеры Паскаля знали об этой проблеме и "фиксировали" ее сохраняя количество байтов в первом байте строки. Они называются Паскаль Струны. Они могут содержать нули и не имеют нулевого завершения. Поскольку байт может хранить только числа от 0 до 255, Pascal строки ограничены длиной 255 байт, но поскольку они не являются нуль завершен, они занимают тот же объем памяти, что и ASCIZ строки. Самое замечательное в струнах Паскаля состоит в том, что у вас никогда не было чтобы иметь цикл, чтобы выяснить длину вашей строки. обнаружение длина строки в Pascal - это одна инструкция сборки целой петли. Это монументально быстрее.

...

Долгое время, если вы хотите поместить строковый литерал Pascal в свой C, вам пришлось написать:

char* str = "\006Hello!";

Да, вам приходилось подсчитывать байты вручную, самим и жестким кодом в первый байт вашей строки. Ленивые программисты сделают это, и имеют медленные программы:

char* str = "*Hello!";
str[0] = strlen(str) - 1;

Ответ 2

Если вы хотите, чтобы это было легко, быстро, вообще и безопасно, я предлагаю использовать функцию open_memstream() (она входит в стандарт POSIX-2008, к сожалению, она не попала в стандарт C11, подумал). Он работает следующим образом:

Сначала вы передадите ему адрес указателя и размер

char* result = NULL;
size_t resultSize = 0;
FILE* stream = open_memstream(&result, &resultSize);

возвращаемое значение является файловым потоком так же, как если бы вы использовали fopen() для открытия файла. Таким образом, вы можете использовать весь арсенал fprintf() и co. чтобы передавать все, что вам нравится в буфер памяти, который автоматически выделяется и управляется для вас. Самое главное, что он также отслеживает размер накопленной строки, поэтому нет необходимости пересканировать его для вычисления его размера.

for(int i = 0; i < 1000000; i++) {
    fprintf(stream, "current number is %d, or 0x%x\n", i, i);
}

Наконец, вы закрываете поток, который обновит ваш указатель результата и переменную размера, чтобы отразить фактическое количество записанных строковых данных.

fclose(stream);
//Now you have a zero terminated C-string in result, and also its size in resultSize.
//You can do with it whatever you like.
//Just remember to free it afterwards:
free(result);

Ответ 3

Предположим, что у вас есть две строки: s1 и s2 с длиной l1 и l2 Конкатенация означает, что вы должны сгенерировать новую строку s3 с длиной l1+l2. Сложность этой операции составляет O(l1+l2). С этой точки зрения strcat() представляется лучшим выбором.

Однако, если вы хотите указать состояние, что две строки конкатенированы, вам нужно только записать их указатели, что составляет O(1). Простой пример будет таким:

typedef struct ConcatStr {
    char* str1;
    char* str2;
} ConcatStr;
ConcatStr myStrcat( char* str1, char* str2 )
{
    ConcatStr cstr;
    cstr.str1 = str1;
    cstr.str2 = str2;
}

Ответ 4

Чтобы объединить несколько строк, код может использовать strlen() и memcpy(), которые часто являются хорошо оптимизированными функциями.

При таком подходе легко добавить недорогой предел size.
Учитывая реальную вероятность того, что буфер назначения может переполнить, в противном случае необходимо ограничение размера.

Время выполнения, пропорциональное сумме строк: O (len (S [0]) + len (S [1]) + len (S [2]) +...)

char *strsncat(char *dest, size_t size, char * strs[], size_t n) {
  assert(size > 0);
  size--;
  char *p = dest;
  while (n-- > 0) {
    size_t len = strlen(*strs);
    if (len >= size) {
      len = size;
    }
    size -= len;
    memcpy(p, *strs, len);
    strs++;
    p += len;
  }
  *p = '\0';
  return dest;
}

void cat_test(void) {
  char dest[10];
  char *strs[]  = { "Red", "Green", "Blue" };
  printf("'%s'\n",strsncat(dest, sizeof dest, strs, sizeof strs/sizeof strs[0]));
  // 'RedGreenB'
}

Ответ 5

Я использую этот вариант, который является скорее заменой замены для strcat, хотя не совсем:

char* mystrcat(char** dest, const char* src) {

    int i = 0;
    char cur;
    while(1) {
        cur = src[i];
        (*dest)[i] = cur;
        if(cur == 0) break;
        i++;
    }

    *dest += i;

    return *dest;
}

Возвращаемое значение здесь не имеет значения. Массив char char str[32] не содержит хранилища для фактического указателя на символы (чтобы снова получить указатель), чтобы вы могли:

char str[32];
char* pStr = str; //storage for pointer
mystrcat(&pStr, "bla");
mystrcat(&pStr, "de");
mystrcat(&pStr, "bla\n");
printf(str);

или

myfunction(char* pStr) {

    mystrcat(&pStr, "bla");
    mystrcat(&pStr, "de");
    mystrcat(&pStr, "bla\n");
}

char str[32];
myfunction(str);
printf(str);

потому что хранилище для указателя теперь создается в стеке для myfunction().

Версия с ограничением длины:

char* mystrcat(char** dest, const char* src, int max) {

    int i = 0;
    char cur;
    while(1) {
        if(i == max) {
            (*dest)[i] = 0;
            break;
        }
        cur = src[i];
        (*dest)[i] = cur;
        if(cur == 0) break;
        i++;
    }

    *dest += i;

    return *dest;
}

Ответ 6

Проверьте это

https://john.nachtimwald.com/2017/02/26/efficient-c-string-builder/

Это помогло мне скопировать char ** в буфер обмена в мгновение ока

    str_builder_t *sb;
     sb = str_builder_create();

                        int colcnt=0;
                        for (int i=0;i<nrF;i++)  // nrF = number of Fileds 
                    {
                            //strcat(DATA,sqlite_array[i]);
                     str_builder_add_str(sb, sqlite_array[i], 0); 
                            if (colcnt<nrofcolumns)  // my list view 
                                {
                            str_builder_add_str(sb, "\t", 0); 
                                colcnt++;

                            }
                                if (colcnt==nrofcolumns) 
                            {

                            str_builder_add_str(sb, "\n", 0); 
                                    colcnt=0;
                            }

                    }

    HANDLE  glob =GlobalAlloc(GMEM_FIXED,str_builder_len(sb)+1);
    memcpy(glob,str_builder_peek(sb),str_builder_len(sb)+1);
    OpenClipboard(NULL);
    EmptyClipboard();
    SetClipboardData(CF_TEXT,glob);
    CloseClipboard();