strcat () против sprintf () внутри цикла

Question

У меня есть программа, которая удаляет все переменные внутри строки.Эти переменные начинаются с '$'.Так, например, если я приведу строку типа [1,2, $ 1, $ 2], она должна вернуть просто [1,2].

Однако, какой цикл лучше для производительности?

Это:

while (token != NULL)
{
    if (*token != '$')
    {
        sprintf(dst, "%s,%s", dst, token);
    }
    token = strtok(NULL, "], ");
}

или это:

while (token != NULL)
{
    if (*token != '$')
    {
        strcat(dst, token);
        strcat(dst, ",");
    }
    token = strtok(NULL, "], ");
}

Answer 1

Ни один из подходов не является приемлемым:

• с передачей sprintf того же указателя, что и для пункта назначения, а источник для спецификатора формата %s имеет неопределенное поведение.Кроме того, sprintf не может предотвратить переполнение буфера, если целевой массив недостаточно велик.

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

Вот альтернативный подход:

char src[LINE_SIZE];
char dst[LINE_SIZE + 1];  /* dst is large enough for the copy */
int pos = 0;

token = strtok(src, "], ");
while (token != NULL) {
    if (*token != '$') {
        pos += sprintf(dst + pos, "%s,", token);
    }
    token = strtok(NULL, "], ");
}

Answer 2

1. strtok является деструктивным, поэтому входная строка не будет использоваться после выполнения этого кода.В таком случае, вы могли бы также сделать преобразование на месте.Это имеет несколько преимуществ, одним из которых является то, что вам не нужно выделять какую-либо память (потому что конечная строка не может быть длиннее исходной строки).Это также требует немного дополнительной бухгалтерии, но это дает еще одно преимущество: время выполнения результирующей функции линейно по размеру ввода.Перезапуск сканирования выходного буфера с начала на каждой итерации - как это делают оба ваших решения - делает функцию квадратичной по длине строки.[Примечание 1] Использование квадратичного алгоритма гораздо серьезнее, чем незначительные различия в стоимости альтернативных вызовов стандартной библиотеки.

2. Как уже упоминали разные люди, это неопределенное поведение для вызоваsprintf таким образом, что между выходным буфером и одной из строк, подлежащих печати, есть перекрытие.Таким образом, использование sprintf некорректно, хотя может показаться, что оно работает в некоторых реализациях.

3. Ни strcat, ни sprintf не защищает вас от переполнения буфера.Вы можете использовать snprintf (поместив новую строку в конец накопленного буфера, вместо того, чтобы перезаписывать начало буфера самим собой на каждой итерации), или вы можете использовать strncat, но в обоих случаях вам потребуетсячтобы сделать некоторые дополнительные бухгалтерии.

Итак, вот быстрая реализация алгоритма, предложенного в первом пункте.Обратите внимание, что он не вызывает malloc() и не выделяет строку в стеке.Также обратите внимание, что он использует memmove вместо memcpy для перемещения недавно обнаруженного токена в строке во избежание проблем, если токен и его назначение будут перекрываться.(memmove допускает перекрытие; memcpy, strcpy и strcat нет.)

/* Compresses the string str in place by removing leading and trailing separator
 * characters (which are the characters in 'fs') and replacing any interior
 * sequence of separator characters with a single instance of 'ofs'.
 * Returns 'str'.
 */
char* compress(char* str, const char* fs, char ofs) {
  char* out = str;
  char* token = strtok(str, fs);
  while (token != NULL) {
    size_t tlen = strlen(token);
    memmove(out, token, tlen);
    out += tlen;
    *out++ = ofs;
    token = strtok(NULL, fs);
  }
  /* Overwrite the last delimiter (if there was one) with a NUL */
  if (out != str) --out;
  *out = 0;
  return str;
}

Примечания API:

• В отличие от оригинала, это не сбрасывает токены, начинающиеся с $.Это было бы тривиально добавить.

• Кроме того, в отличие от оригинала, эта функция позволяет избежать трейлинга ,.Опять же, это было бы легко изменить, если бы была веская причина.(Однако завершающая запятая означает, что строки только с одним токеном будут в конечном итоге на один символ длиннее, поэтому гарантию на месте сделать нельзя.)

• Я решил вернутьсяадрес начала сжатой строки (который совпадает с адресом входного буфера), чтобы соответствовать различным стандартным интерфейсам C.Однако во многих случаях было бы более полезно вернуть out (который является адресом конечного NUL), чтобы разрешить дальнейшую конкатенацию без необходимости вычислять новую длину строки.Кроме того, можно вернуть новую длину строки, как sprintf делает (return out - str;)

• Этот API честен в том, что он уничтожает исходную строку (перезаписываяэто с преобразованным);Функции, которые просто вызывают strtok на своем входе, но возвращают отдельный вывод, могут вызвать незначительные ошибки, потому что вызывающей стороне не очевидно, что исходная строка уничтожена.Несмотря на то, что невозможно восстановить строку после вызова strtok, ее легко преобразовать на месте в неразрушающий алгоритм, просто скопировав исходную строку:

  /* Returns freshly allocated memory; caller is responsible for freeing it */
  char* compress_and_copy(const char* str, const char* fs, char ofs) {
    return compress(strdup(str), fs, ofs);
  }
  

• Конечно, возможно, что оригинальная не упрощенная функция не имела функции, гарантирующей, что она будет создавать более короткую строку;например, это может быть расширение сегментов, начиная с $, заменяя их значением переменной.В этом случае необходимо будет создать новую строку.

  В некоторых случаях, возможно, даже в большинстве случаев, выходной сигнал все равно будет короче входного.Но следует сопротивляться искушению выполнить преобразование на месте, если это возможно, и выделять новую строку только в случае необходимости.Хотя это может быть более эффективным, оно усложняет правила распределения собственности;в конечном итоге вам приходится говорить «вызывающая сторона владеет возвращенной строкой, только если она отличается от исходной строки», что является неуклюжим и подвержено случайным действиям.

  Так что, если это фактический вариант использования, оптимальное решение (изперспектива чистого дизайна API) - использовать strspn() и strcspn() для неразрушающего обхода исходной строки.Это немного больше работы, потому что нужно еще больше бухгалтерии;с другой стороны, он устраняет необходимость повторного вычисления strlen(token) после идентификации токена.

Примечания:

1. Технически, время пропорциональнок произведению длины строки и количества токенов, но в худшем случае (когда токены короткие) это фактически O (n ² ).

Answer 3

Согласно C11 стандарту 7.21.6.6 p2 , описывающему sprintf:

Если копирование происходит между перекрывающимися объектами, поведение не определено.

Итак, ваш первый фрагмент вызывает неопределенное поведение при копировании из dst в dst.Подход strcat не имеет этой проблемы.