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

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 использует их!

Итак, мой вопрос: есть ли какие-либо преимущества для null-term, которые мне не хватает?

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

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

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

Answer 6

Просто выбросить некоторые гипотетики:

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

Answer 7

От Джоэла Back to Basics:

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

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

Answer 8

Одним из преимуществ NUL байт, что если вы идете через строку символов по-символ, вам нужно только сохранить один указатель на адрес строки:

while (*s) 
{ 
    *s = toupper(*s); 
    s++; 
} 

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

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

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

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

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

Answer 9

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

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

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

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

Answer 10

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

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

Это создает структуру, которая имеет длину в начале, с ЭЛЕМЕНТ "персонажей, используемой в качестве полукокса * так же, как вы бы с током структура. Разница, однако, заключается в том, что вы можете выделить только один элемент в куче для каждой строки вместо двух. Выделяют ваши строки так:

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

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

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