Каково обоснование для строк с нулевым символом в конце? - PullRequest
268 голосов
/ 11 декабря 2010

Столько, сколько я люблю C и C ++, я не могу не почесать голову при выборе строк с нулевым окончанием:

  • Длина строки с префиксом (т.е. Паскаль) существовала до C
  • Строки с префиксом длины ускоряют несколько алгоритмов, обеспечивая постоянный поиск по времени.
  • Строки с префиксом длины затрудняют возникновение ошибок переполнения буфера.
  • Даже на 32-битной машине, если вы позволите строке соответствовать размеру доступной памяти, строка с префиксом длины будет всего на три байта шире строки с нулевым символом в конце. На 16-битных машинах это один байт. На 64-битных компьютерах 4 ГБ - разумное ограничение длины строки, но даже если вы хотите расширить его до размера машинного слова, 64-битные машины обычно имеют достаточно памяти, что делает дополнительные семь байтов своего рода нулевым аргументом. Я знаю, что оригинальный стандарт C был написан для безумно плохих машин (с точки зрения памяти), но аргумент эффективности здесь меня не продает.
  • Практически все другие языки (например, Perl, Pascal, Python, Java, C # и т. Д.) Используют строки с префиксом длины. Эти языки обычно превосходят C в тестах работы со строками, потому что они более эффективны со строками.
  • C ++ исправил это немного с помощью шаблона std::basic_string, но массивы простых символов, ожидающие строки с нулевым символом в конце, все еще распространены. Это также несовершенно, поскольку требует выделения кучи.
  • Строки с нулевым символом в конце должны зарезервировать символ (а именно, ноль), который не может существовать в строке, в то время как строки с префиксом длины могут содержать встроенные нули.

Некоторые из этих вещей обнаружились совсем недавно, чем C, поэтому было бы разумно, чтобы C не знал о них. Тем не менее, некоторые были просты задолго до того, как появился С. Почему были выбраны строки с нулевым символом в конце вместо явно превосходящего префикса длины?

РЕДАКТИРОВАТЬ : Поскольку некоторые просили указать фактов (и им не понравились те, которые я уже предоставил) в моем пункте эффективности выше, они вытекают из нескольких вещей:

  • Concat, использующий строки с нулевым символом в конце, требует O (n + m) временной сложности. Длина префикса часто требует только O (м).
  • Длина с использованием строк с нулевым символом в конце требует O (n) временной сложности. Длина префикса O (1).
  • Длина и конкат являются наиболее распространенными строковыми операциями. Есть несколько случаев, когда строки с нулевым символом в конце могут быть более эффективными, но они встречаются гораздо реже.

Из ответов ниже приведены некоторые случаи, когда строки с нулевым символом в конце более эффективны:

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

Ничто из вышеперечисленного не встречается так часто, как длина и конкат.

В ответах ниже утверждается еще один:

  • Вам нужно обрезать конец строки

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

Ответы [ 17 ]

190 голосов
/ 11 декабря 2010

Изо рта лошади

Ни одна из BCPL, B или C не поддерживает символьные данные сильно в язык; каждый много относится к строкам как векторы целых чисел и дополняет общие правила несколькими конвенций. И в BCPL, и в B a строковый литерал обозначает адрес статическая область, инициализированная с символы строки, упакованные в клетки. В BCPL первый упакованный байт содержит количество символов в строка; в Б нет счета и строки завершаются особый характер, который B пишется *e. Это изменение было сделано частично чтобы избежать ограничения по длине строки, вызванной удержанием считать в 8- или 9-битном слоте и отчасти потому, что ведение счета казалось, по нашему опыту, меньше удобнее, чем использование терминатора.

Деннис М Ритчи, Развитие языка Си

150 голосов
/ 11 декабря 2010

C не имеет строки как части языка.«Строка» в C - это просто указатель на char.Так что, возможно, вы задаете не тот вопрос.

«Каково обоснование пропуска строкового типа» может быть более уместным.На это я хотел бы указать, что C не является объектно-ориентированным языком и имеет только базовые типы значений.Строка - это концепция более высокого уровня, которая должна быть реализована путем объединения значений других типов.C находится на более низком уровне абстракции.

в свете бушующего шквала ниже:

Я просто хочу отметить, что я не пытаюсь сказать, что это глупый или плохой вопросили что способ представления строк на языке C является лучшим выбором.Я пытаюсь уточнить, что вопрос будет более лаконичным, если принять во внимание тот факт, что в C нет механизма для дифференциации строки как типа данных от байтового массива.Является ли это лучшим выбором в свете производительности и памяти современных компьютеров?Возможно нет.Но задним числом всегда 20/20 и все такое:)

101 голосов
/ 12 декабря 2010

Вопрос задается как вещь Length Prefixed Strings (LPS) против zero terminated strings (SZ), но в основном предоставляет преимущества строк с префиксом длины.Это может показаться подавляющим, но, честно говоря, мы должны также учитывать недостатки LPS и преимущества SZ.

Насколько я понимаю, этот вопрос можно даже понимать как предвзятый способ задать вопрос: «Каковы преимущества нулевых терминированных строк?».

Преимущества (я вижу) строк с нулевым завершением:

  • очень просто, нет необходимости вводить новые понятия в языке, массивы char / указатели на символы могут сделать.
  • базовый язык просто включает минимальный синтаксический сахар для преобразования чего-то между двойными кавычками в набор символов (на самом деле набор байтов).В некоторых случаях его можно использовать для инициализации вещей, совершенно не связанных с текстом.Например, формат файла изображения xpm является допустимым источником Си, который содержит данные изображения, закодированные в виде строки. Кстати,
  • , вы можете поставить ноль в строковом литерале, компилятор простотакже добавьте еще один в конце литерала: "this\0is\0valid\0C".Это строка?или четыре строки?Или несколько байтов ...
  • плоская реализация, без скрытого косвенного обращения, без скрытого целого числа.
  • без скрытого выделения памяти (ну, некоторые печально известные нестандартные функции, такие как strdup, выполняют выделение, ноэто в основном источник проблем).
  • без особых проблем для небольших или больших аппаратных средств (представьте себе бремя управления длиной префикса 32 бита на 8-битных микроконтроллерах или ограничения ограничения размера строки до 256 байт,это была проблема, с которой я действительно столкнулся в Turbo Pascal много лет назад).
  • реализация манипуляции со строками - всего лишь несколько очень простых библиотечных функций
  • , эффективных для основного использования строк: постоянное чтение текстапоследовательно с известного начала (в основном это сообщения пользователю).
  • завершающий ноль даже не обязателен, доступны все необходимые инструменты для манипулирования символами, например, байтами.Выполняя инициализацию массива в C, вы можете даже избежать терминатора NUL.Просто установите правильный размер.char a[3] = "foo"; является допустимым C (не C ++) и не ставит конечный ноль в.
  • , согласованном с точкой зрения Unix «все есть файл», включая «файлы», которые не имеют внутренней длины, такой какстандартный, стандартныйСледует помнить, что открытые примитивы чтения и записи реализованы на очень низком уровне.Это не библиотечные вызовы, а системные вызовы.И тот же API используется для двоичных или текстовых файлов.Примитивы чтения файлов получают адрес и размер буфера и возвращают новый размер.И вы можете использовать строки в качестве буфера для записи.Использование строкового представления другого типа подразумевает, что вы не можете легко использовать литеральную строку в качестве буфера для вывода, или вам придется заставить ее вести себя очень странно при приведении ее к char*.А именно, чтобы не возвращать адрес строки, а вместо этого возвращать фактические данные.
  • очень легко манипулировать текстовыми данными, считанными из файла на месте, без бесполезной копии буфера, просто вставьте нули справамест (ну, не совсем с современным C, так как строки в двойных кавычках являются массивами константных символов в настоящее время, как правило, хранятся в неизменяемом сегменте данных).
  • добавление некоторых значений int любого размера подразумевает проблемы с выравниванием.Начальная длина должна быть выровнена, но нет причин делать это для данных символов (и опять же, принудительное выравнивание строк может повлечь за собой проблемы при обработке их как набора байтов). Длина
  • известна ввремя компиляции для константных литеральных строк (sizeof).Так зачем кому-то хотеть хранить его в памяти, добавляя его к фактическим данным?
  • так, как С делает (почти) все, строки рассматриваются как массивы char. Поскольку длина массива не управляется C, это логическая длина не управляется ни для строк. Удивительно только то, что в конце добавлен 0 элемент, но это только на уровне основного языка при вводе строки между двойными кавычками. Пользователи могут прекрасно вызывать функции обработки строк, передавая длину, или даже использовать простую memcopy. SZ просто средство. В большинстве других языков длина массива управляется, это логично, что то же самое для строк.
  • в наше время, во всяком случае, однобайтовых наборов символов недостаточно, и вам часто приходится иметь дело с закодированными строками юникода, где количество символов сильно отличается от количества байтов. Это подразумевает, что пользователи, вероятно, захотят больше, чем «просто размер», но также и другую информацию. Сохранение длины не дает никакой пользы (особенно нет естественного места для их хранения) в отношении этой другой полезной информации.

Тем не менее, нет необходимости жаловаться в редком случае, когда стандартные строки C действительно неэффективны. Libs доступны. Если бы я следовал этой тенденции, я бы пожаловался, что стандарт C не включает в себя какие-либо функции поддержки регулярных выражений ... но на самом деле все знают, что это не настоящая проблема, так как для этого есть библиотеки. Поэтому, когда требуется эффективность работы со строками, почему бы не использовать такую ​​библиотеку, как bstring ? Или даже строки C ++?

РЕДАКТИРОВАТЬ : Недавно я посмотрел на D строк . Достаточно интересно увидеть, что выбранное решение не является ни префиксом размера, ни нулевым завершением. Как и в C, буквенные строки, заключенные в двойные кавычки, являются просто сокращением для неизменяемых массивов символов, а язык также имеет ключевое слово string, означающее это (неизменяемый массив символов).

Но D-массивы намного богаче, чем C-массивы. В случае статических массивов длина известна во время выполнения, поэтому нет необходимости хранить длину. У компилятора это есть во время компиляции. В случае динамических массивов длина доступна, но в документации D не указано, где она хранится. Насколько нам известно, компилятор может сохранить его в некотором регистре или в некоторой переменной, хранящейся далеко от данных символов.

В обычных массивах символов или не-литеральных строках нет конечного нуля, поэтому программист должен поставить его сам, если он хочет вызвать некоторую функцию C из D. В конкретном случае литеральных строк, однако компилятор D по-прежнему помещает ноль в конце каждой строки (чтобы упростить приведение к строкам C, чтобы было проще вызывать функцию C?), но этот ноль не является частью строки (D не считает ее размером строки).

Единственное, что меня несколько разочаровало, это то, что строки должны быть utf-8, но длина, по-видимому, по-прежнему возвращает количество байтов (по крайней мере, это верно для моего компилятора gdc) даже при использовании многобайтовых символов. Мне неясно, является ли это ошибкой компилятора или по назначению. (Хорошо, я, наверное, узнал, что произошло. Чтобы сказать компилятору D, что ваш источник использует utf-8, вы должны поставить какую-то глупую метку порядка байтов в начале. Я пишу глупо, потому что знаю, что это не делает редактор, особенно для UTF- 8, который должен быть совместим с ASCII).

60 голосов
/ 11 декабря 2010

Я думаю, у него есть исторические причины, и он нашел это в википедии :

Во время разработки языка С (и языков, из которых он был получен) память былачрезвычайно ограничен, поэтому использование только одного байта служебной информации для хранения длины строки было привлекательным.Единственная популярная альтернатива того времени, обычно называемая «строкой Паскаля» (хотя и использовавшаяся в ранних версиях BASIC), использовала старший байт для хранения длины строки.Это позволяет строке содержать NUL, и для поиска длины требуется только один доступ к памяти (O (1) (постоянное) время).Но один байт ограничивает длину 255. Это ограничение длины было гораздо более ограничительным, чем проблемы со строкой C, поэтому строка C в целом победила.

31 голосов
/ 13 декабря 2010

Калавера - это право , но, поскольку люди, похоже, не понимают его, я приведу несколько примеров кода.

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

Если бы C имел тип string, такой как int или char, это был бы тип, который не 'не помещается в регистр или в стек и требует, чтобы распределение памяти (со всей его поддерживающей инфраструктурой) осуществлялось любым способом.Все это идет вразрез с основными принципами C.

Итак, строка в C выглядит так:

char s*;

Итак, давайте предположим, что это с префиксом длины.Давайте напишем код для объединения двух строк:

char* concat(char* s1, char* s2)
{
    /* What? What is the type of the length of the string? */
    int l1 = *(int*) s1;
    /* How much? How much must I skip? */
    char *s1s = s1 + sizeof(int);
    int l2 = *(int*) s2;
    char *s2s = s2 + sizeof(int);
    int l3 = l1 + l2;
    char *s3 = (char*) malloc(l3 + sizeof(int));
    char *s3s = s3 + sizeof(int);
    memcpy(s3s, s1s, l1);
    memcpy(s3s + l1, s2s, l2);
    *(int*) s3 = l3;
    return s3;
}

Другой альтернативой будет использование структуры для определения строки:

struct {
  int len; /* cannot be left implementation-defined */
  char* buf;
}

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

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

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

Теперь C может обрабатывать память в любом случае, а функции mem в библиотеке (даже в <string.h>) предоставляют все необходимые инструменты для обработки памяти какпара указателей и размеров.Так называемые «строки» в C были созданы только для одной цели: показывать сообщения в контексте написания операционной системы, предназначенной для текстовых терминалов.И для этого достаточно нулевого завершения.

19 голосов
/ 12 декабря 2010

Очевидно, что с точки зрения производительности и безопасности вы захотите сохранить длину строки во время работы с ней, а не многократно выполнять strlen или ее эквивалент. Однако хранение длины в фиксированном месте непосредственно перед содержимым строки является невероятно плохим дизайном. Как отметил в комментариях к ответу Санджита Йорген, это исключает возможность трактовать хвост строки как строку, что, например, делает невозможным использование многих общих операций, таких как path_to_filename или filename_to_extension, без выделения новой памяти (и, следовательно, возможности обработки ошибок и ошибок). И, конечно же, существует проблема, заключающаяся в том, что никто не может согласиться с тем, сколько байтов должно занимать поле длины строки (множество плохих языков «строки Паскаля» использовали 16-битные поля или даже 24-битные поля, которые исключают обработку длинных строк).

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

13 голосов
/ 12 декабря 2010

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

посмотрим в псевдокоде

function readString(string) // 1 parameter: 1 register or 1 stact entries
    pointer=addressOf(string) 
    while(string[pointer]!=CONTROL_CHAR) do
        read(string[pointer])
        increment pointer

всего 1 регистр использования

дело 2

 function readString(length,string) // 2 parameters: 2 register used or 2 stack entries
     pointer=addressOf(string) 
     while(length>0) do 
         read(string[pointer])
         increment pointer
         decrement length

всего 2 регистра использовано

Это может показаться недальновидным в то время, но учитывая бережливость кода и регистра (которые были ПРЕМИУМ в то время, когда вы знаете, они использовали перфокарту). Таким образом, будучи «быстрее» (когда скорость процессора можно считать в кГц), этот «хак» был чертовски хорош и легко переносим для процессора без регистрации.

Ради аргумента я реализую 2 обычные строковые операции

stringLength(string)
     pointer=addressOf(string)
     while(string[pointer]!=CONTROL_CHAR) do
         increment pointer
     return pointer-addressOf(string)

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

concatString(string1,string2)
     length1=stringLength(string1)
     length2=stringLength(string2)
     string3=allocate(string1+string2)
     pointer1=addressOf(string1)
     pointer3=addressOf(string3)
     while(string1[pointer1]!=CONTROL_CHAR) do
         string3[pointer3]=string1[pointer1]
         increment pointer3
         increment pointer1
     pointer2=addressOf(string2)
     while(string2[pointer2]!=CONTROL_CHAR) do
         string3[pointer3]=string2[pointer2]
         increment pointer3
         increment pointer1
     return string3

сложность O (n) и добавление длины строки не изменит сложности операции, хотя я допускаю, что это займет в 3 раза меньше времени.

С другой стороны, если вы используете строку PASCAL, вам придется перепроектировать свой API для учета длины регистра и порядка следования битов, строка PASCAL получила хорошо известное ограничение в 255 символов (0xFF), поскольку длина была сохранена в 1 байт (8 бит), и если вам нужна более длинная строка (16 бит -> что угодно), вам придется учитывать архитектуру на одном уровне вашего кода, что в большинстве случаев будет означать несовместимые строковые API, если вы хотите более длинную строку.

Пример: * * тысяча двадцать-пять

Один файл был записан с вашей предварительно добавленной строкой api на 8-битном компьютере, а затем должен был быть прочитан, скажем, на 32-битном компьютере, что ленивая программа посчитает, что ваши 4 байта - это длина строки, а затем выделите много памяти затем пытается прочитать это много байтов. В другом случае считывание 32-байтовой строки PPC (с прямым порядком байтов) в x86 (с прямым порядком байтов), конечно, если вы не знаете, что одно записано другим, может вызвать проблемы. 1 байт (0x00000001) станет 16777216 (0x0100000), что составляет 16 МБ для чтения 1-байтовой строки. Конечно, вы могли бы сказать, что люди должны договориться об одном стандарте, но даже 16-битный Unicode имеет маленький и большой порядок байтов.

Конечно, у С тоже будут свои проблемы, но затронутые здесь проблемы будут очень мало затронуты.

9 голосов
/ 12 декабря 2010

Во многих отношениях С был примитивным.И мне это понравилось.

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

Оглядываясь назад, это не кажется удобным.Но я использовал язык ассемблера еще в 80-х, и в то время он казался очень удобным.Я просто думаю, что программное обеспечение постоянно развивается, а платформы и инструменты постоянно совершенствуются.

8 голосов
/ 12 декабря 2010

Предполагая на мгновение, что C реализовал строки способом Pascal, с префиксом их по длине: строка длиной 7 символов совпадает с типом данных DATA TYPE как строка из 3 символов? Если ответ «да», то какой код должен генерировать компилятор, когда я назначаю первый последнему? Должна ли строка быть усечена или автоматически изменена? Если изменить размер, должна ли эта операция быть защищена блокировкой, чтобы сделать ее безопасной для потока? Сторона подхода C перешагнула все эти вопросы, нравится нам это или нет :)

7 голосов
/ 12 декабря 2010

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

#define PREFIX_STR(s) ((prefix_str_t){ sizeof(s)-1, (s) })

typedef struct { int n; char * p; } prefix_str_t;

int main() {
    prefix_str_t string1, string2;

    string1 = PREFIX_STR("Hello!");
    string2 = PREFIX_STR("Allows \0 chars (even if printf directly doesn't)");

    printf("%d %s\n", string1.n, string1.p); /* prints: "6 Hello!" */
    printf("%d %s\n", string2.n, string2.p); /* prints: "48 Allows " */

    return 0;
}

Это, однако, не вызовет никаких проблем, так как вы должны быть осторожны, когда конкретно освобождаете этот строковый указатель и когда он статически размещается (литерал char массив).

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

Конечно, похоже, что работа со строками с нулевым завершением была рекомендуемой практикой, поскольку стандартная библиотека в общем случае не принимаетдлины строк в качестве аргументов, и поскольку извлечение длины не такой простой код, как char * s = "abc", как показывает мой пример.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...