Почему строки с нулевым символом в конце? Или: завершено нулем против символов + длина хранения

Question

Я пишу переводчик языка на C, а мой тип string содержит атрибут length, например:

struct String
{
    char* characters;
    size_t length;
};

Из-за этого мне приходится тратить много времени в моем интерпретаторе на ручную обработку этого типа строки, поскольку C не имеет встроенной поддержки для нее. Я подумал о переходе на простые строки с нулевым символом в конце только для соответствия базовому C, но, похоже, есть много причин не делать этого:

Проверка границ встроена, если вы используете «длину» вместо поиска нулевого значения.

Вы должны пройти всю строку, чтобы найти ее длину.

Вы должны выполнить дополнительные действия для обработки нулевого символа в середине строки, заканчивающейся нулем.

Строки с нулевым символом в конце плохо работают с Unicode.

Строки, не оканчивающиеся нулем, могут содержать больше символов, то есть символы «Hello, world» и «Hello» могут храниться в одном и том же месте, но разной длины. Это нельзя сделать с помощью строк с нулевым символом в конце.

Срез строки (примечание: строки на моем языке неизменны). Очевидно, что вторая медленнее (и более подвержена ошибкам: подумайте о добавлении проверки ошибок begin и end в обе функции).

struct String slice(struct String in, size_t begin, size_t end)
{
    struct String out;
    out.characters = in.characters + begin;
    out.length = end - begin;

    return out;
}

char* slice(char* in, size_t begin, size_t end)
{
    char* out = malloc(end - begin + 1);

    for(int i = 0; i < end - begin; i++)
        out[i] = in[i + begin];

    out[end - begin] = '\0';

    return out;
}

После всего этого я больше не думаю о том, следует ли мне использовать строки с нулевым символом в конце: я думаю о том, почему C использует их!

Итак, мой вопрос: есть ли какие-то преимущества от нулевого завершения, которое я пропускаю?

Answer 1

От Джоэла Назад к основам :

Почему C-строки работают таким образом? Это потому, что микропроцессор PDP-7, на котором были изобретены UNIX и язык программирования C, имел строковый тип ASCIZ. ASCIZ означает «ASCII с Z (ноль) в конце».

Это единственный способ хранить строки? Нет, на самом деле, это один из худших способов хранения строк. Для нетривиальных программ, API, операционных систем, библиотек классов следует избегать строк ASCIZ, таких как чума.

Answer 2

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

Строки с нулевым символом в конце часто приводят к снижению производительности, по очевидной причине, что время, необходимое для определения длины, зависит от длины. С другой стороны, они являются стандартным способом представления строк в C, поэтому у вас нет другого выбора, кроме как поддерживать их, если вы хотите использовать большинство библиотек C.

Answer 3

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

Answer 4

Одно из преимуществ строк с нулевым символом в конце состоит в том, что если вы проходите строку за символом, вам нужно всего лишь сохранить один указатель для адресации строки:без часовых, вам нужно хранить два бита состояния: указатель и индекс:

while (i < s.length)
{
    s.data[i] = toupper(s.data[i]);
    i++;
}

... или текущий указатель и предел:

s_end = s + length;
while (s < s_end)
{
    *s = toupper(*s);
    s++;
}

при использовании процессорарегистры были дефицитным ресурсом (и компиляторы хуже распределяли их), это было важно.Теперь не так много.

Answer 5

Немного оффтоп, но есть более эффективный способ создания строк с префиксом длины, чем тот, который вы описываете. Создайте структуру, подобную этой (действительна в C99 и выше):

struct String 
{
  size_t length;
  char characters[0];
}

Это создает структуру, которая имеет длину в начале, с элементом 'characters', используемым как символ *, так же, как вы это делаете с вашей текущей структурой. Разница, однако, заключается в том, что для каждой строки можно выделить только один элемент в куче вместо двух. Распределите ваши строки следующим образом:

mystr = malloc(sizeof(String) + strlen(cstring))

Например, длина структуры (которая является просто size_t) плюс достаточно места, чтобы поставить после нее фактическую строку.

Если вы не хотите использовать C99, вы также можете сделать это с помощью «символов символов [1]» и вычесть 1 из длины строки для выделения.

Answer 6

Длина тоже имеет свои проблемы.

• Длина занимает дополнительное место (сейчас это не проблема, но большой фактор 30 лет назад).

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

• С NUL-оканчивающейся строкой вы все равно можете использовать длину или сохранять указатель на последний символ, поэтому, если вы делаете много строковых манипуляций, вы все равно можете равняться производительности string-with-length.

• Строки с NUL-окончанием намного проще - терминатор NUL - это просто соглашение, используемое методами, такими как strcat, для определения конца строки. Таким образом, вы можете хранить их в обычном массиве символов вместо использования структуры.

Answer 7

Просто выбрасываю некоторые гипотезы:

• нет способа получить "неправильную" реализацию строк с нулевым символом в конце. Однако стандартизированная структура может иметь специфичные для поставщика реализации.
• никаких структур не требуется. Строки с нулевым окончанием являются, так сказать, «встроенными», поскольку являются особым случаем символа *.

Answer 8

Вы абсолютно правы, что 0-завершение - это метод, который плохо подходит для проверки типов и производительности для части операций. Ответы на этой странице уже суммируют происхождение и использование для него.

Мне понравилось, как Delphi хранит строки. Я считаю, что он поддерживает длину / максимальную длину перед строкой (переменной длины). Таким образом, строки могут заканчиваться нулем для совместимости.

Мои проблемы с вашим механизмом: - дополнительный указатель - неизменность в основных частях вашего языка; обычно строковые типы не являются неизменяемыми, поэтому, если вы когда-нибудь пересмотрите их, это будет сложно. Вам необходимо реализовать механизм «создать копию при изменении» - использование malloc (вряд ли эффективно, но может быть включено сюда просто для удобства?)

Удачи; Написание собственного интерпретатора может быть очень познавательным в понимании в основном грамматики и синтаксиса языков программирования! (по крайней мере, это для меня)

Answer 9

Хотя я предпочитаю метод array + len в большинстве случаев, есть веские причины для использования с нулевым символом в конце.

Взять 32-битную систему.

Для хранения 7-байтовой строки
char * + size_t + 8 байт = 19 байт

Для хранения 7-байтовой строки с нулевым значением
символ * + 8 = 16 байт.

Массивы с нулевым сроком действия не должны быть неизменяемыми, как это делают ваши строки. Я могу счастливо обрезать к-строку, просто поместив нулевой символ. Если вы кодируете, вам нужно будет создать новую строку, которая включает в себя выделение памяти.

В зависимости от использования строк, ваши строки никогда не смогут соответствовать производительности, возможной с c-строками, в отличие от ваших строк.

Answer 10

Я думаю, что основная причина в том, что стандарт не говорит ничего конкретного о размере любого типа, кроме char. Но sizeof (char) = 1, и этого явно недостаточно для размера строки.