Каково обоснование для строк с нулевым символом в конце?

281

Столько, сколько я люблю 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 и друзей).

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

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

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

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

Билли ОНил
источник
110
Я всегда думал, что для всех программистов C ++ это был обряд написания своей собственной библиотеки строк.
Джульетта
31
Что это значит ожидать рациональных объяснений сейчас. Я полагаю, вы хотите услышать обоснование для x86 или DOS дальше? Насколько мне известно, худшие технологии выигрывают. Каждый раз. И худшее строковое представление.
Джалф
4
Почему вы утверждаете, что строки префикса длины лучше? В конце концов, C стал популярным, потому что он использовал строки с нулевым символом в конце, что отличало его от других языков.
Даниэль С. Собрал
44
@Daniel: C стал популярным, потому что это простое, эффективное и переносимое представление программ, исполняемых на машинах фон Неймана, и потому, что оно использовалось для Unix. Конечно, это не потому, что он решил использовать строки с нулевым символом в конце. Если бы это было хорошее дизайнерское решение, люди бы скопировали его, а они нет. Они, конечно, скопировали почти все остальное из C.
Билли ONeal
4
Concat - это только O (m) с префиксом длины, если вы уничтожаете одну из строк. В остальном же скорость. Наиболее часто используемые строки C (исторически) были печать и сканирование. В обоих случаях нулевое завершение выполняется быстрее, поскольку оно сохраняет один регистр.
Даниэль С. Собрал

Ответы:

195

Из рта лошади

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

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

Ганс Пассант
источник
12
Другая релевантная цитата: «... семантика строк полностью подчиняется более общим правилам, регулирующим все массивы, и в результате язык проще описать ...»
AShelly
151

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

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

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

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

Роберт С Чаччо
источник
29
char *temp = "foo bar";является действительным утверждением на C ... эй! разве это не строка? разве это не завершено?
Яник Рошон
56
@Yanick: это просто удобный способ сообщить компилятору о создании массива char с нулем в конце. это не «строка»
Роберт С. Чаччо
28
@calavera: Но это могло бы означать просто «Создать буфер памяти с этим строковым содержимым и двухбайтовым префиксом»,
Billy ONeal
14
@Billy: хорошо, поскольку «строка» на самом деле является просто указателем на символ, который эквивалентен указателю на байт, как вы узнали бы, что буфер, с которым вы работаете, действительно предназначен для «строки»? вам потребуется новый тип, отличный от char / byte *, чтобы обозначить это. может быть структура?
Роберт С. Чаччо
27
Я думаю, что @calavera прав, у C нет типа данных для строк. Хорошо, вы можете рассматривать массив символов как строку, но это не значит, что это всегда строка (под строкой я подразумеваю последовательность символов с определенным значением). Бинарный файл - это массив символов, но эти символы ничего не значат для человека.
BlackBear
106

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

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

Преимущества (я вижу) Zero Termination Strings:

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

Kriss
источник
7
... продолжение ... Некоторые из ваших пунктов, я думаю, просто неверны, т. Е. Аргумент "все - файл". Файлы имеют последовательный доступ, строки C - нет. Префикс длины также может быть сделан с минимальным синтаксическим сахаром. Единственным разумным аргументом здесь является попытка управлять 32-битными префиксами на небольшом (то есть 8-битном) оборудовании; Я думаю, что это можно просто решить, сказав, что размер длины определяется реализацией. В конце концов, это то, чтоstd::basic_string делает.
Билли Онил
3
@Billy ONeal: на самом деле в моем ответе есть две разные части. Один о том, что является частью «основного языка Си», другой о том, что должны предоставлять стандартные библиотеки. Что касается поддержки строк, в базовом языке есть только один элемент: значение двойной кавычки заключено в кучу байтов. Я не очень счастлив, чем вы с поведением C. Я волшебным образом добавляю, что ноль в конце каждого двойного замыкания заключает в себе кучу байтов, это достаточно плохо. Я бы предпочел и явный \0в конце, когда программисты хотят этого вместо неявного. Предварительная длина намного хуже.
Крис
2
@Billy ONeal: это просто неправда, пользователи заботятся о том, что является ядром и что такое библиотеки. Самый большой момент, когда C используется для реализации ОС. На этом уровне нет доступных библиотек. C также часто используется во встроенных контекстах или для программирования устройств, где у вас часто бывают такие же ограничения. Во многих случаях Joes's, вероятно, вообще не следует использовать C в настоящее время: «Хорошо, вы хотите это на консоли? У вас есть консоль? Нет? Жаль ...»
kriss
5
@Billy "Ну, для 0,01% программистов на C, которые внедряют операционные системы, хорошо." Другие программисты могут пойти в поход. C был создан для написания операционной системы.
Даниэль С. Собрал
5
Зачем? Потому что он говорит, что это язык общего назначения? Говорит ли он, что люди, которые написали это, делали, когда это создавало? Для чего он использовался в течение первых нескольких лет своей жизни? Итак, что же это говорит о том, что я не согласен? Это язык общего назначения, созданный для написания операционной системы . Это отрицает это?
Даниэль С. Собрал
61

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

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

Хачик
источник
2
@muntoo Хм ... совместимость?
Хачик
19
@muntoo: потому что это сломало бы огромное количество существующего кода на C и C ++.
Билли ONEAL
10
@muntoo: парадигмы приходят и уходят, но устаревший код навсегда. Любая будущая версия C должна будет продолжать поддерживать строки с нулем в конце, в противном случае устаревший код на 30+ лет придется переписать (что не произойдет). И пока старый способ доступен, это то, что люди будут продолжать использовать, так как это то, с чем они знакомы.
Джон Боде
8
@muntoo: Поверь мне, иногда я хотел бы. Но я все же предпочел бы строки с нулевым символом в конце строки Pascal.
Джон Боде
2
Разговор об унаследованном ... Строки C ++ теперь должны быть завершены NUL.
Джим Балтер
32

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

Сначала давайте рассмотрим, что такое 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;
}

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

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

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

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

Даниэль С. Собрал
источник
2
1. +1. 2. Очевидно, что если бы поведение языка по умолчанию было выполнено с использованием префиксов длины, были бы другие способы сделать это проще. Например, все ваши приведения были бы скрыты звонками strlenи друзьями. Что касается проблемы с «оставлением ее на усмотрение реализации», вы можете сказать, что префикс - это то, что shortнаходится в поле назначения. Тогда все ваши кастинги все равно будут работать. 3. Я могу придумывать надуманные сценарии в течение всего дня, из-за которых та или иная система выглядит плохо.
Билли ONEAL
5
@Billy Суть библиотеки достаточно верна, за исключением того факта, что C был разработан для минимального использования библиотеки или вообще без него. Например, использование прототипов не было обычным делом на ранних этапах. Сказать, что префикс shortэффективно ограничивает размер строки, что, кажется, было единственной вещью, которой они не интересовались. Я сам, работая с 8-битными строками BASIC и Pascal, строками COBOL фиксированного размера и подобными вещами, быстро стал большим поклонником C-строк неограниченного размера. В настоящее время 32-битный размер будет обрабатывать любую практическую строку, но добавление этих байтов на ранних этапах было проблематичным.
Даниэль С. Собрал
1
@ Билли: Во-первых, спасибо, Дэниел ... ты, кажется, понимаешь, к чему я клоню. Во-вторых, Билли, я думаю, ты все еще не понимаешь, что здесь делается. Я, например, не спорю о плюсах и минусах префиксных строковых типов данных с их длиной. То, что я говорю, и что Даниил очень четко подчеркнул, это то, что в реализации C было принято решение не обрабатывать этот аргумент вообще . Строки не существуют в том, что касается базового языка. Решение о том, как обрабатывать строки, остается за программистом ... и нулевое завершение становится популярным.
Роберт С Чаччо
1
+1 мной. Еще одну вещь, которую я хотел бы добавить; структура, как вы предлагаете, пропускает важный шаг к реальному stringтипу: она не знает символов. Это массив «char» («char» в машинном жаргоне - это такой же символ, как «слово» - это то, что люди называют словом в предложении). Строка символов - это концепция более высокого уровня, которая может быть реализована поверх массива, charесли вы ввели понятие кодирования.
Фрерих Раабе
2
@ DanielC.Sobral: Кроме того, структура, которую вы упоминаете, не требует двух выделений. Либо используйте его так, как он есть в стеке (так что bufтребуется только выделение), либо используйте struct string {int len; char buf[]};и выделите все это с одним выделением в качестве члена гибкого массива, и передайте его как a string*. (Или, возможно, struct string {int capacity; int len; char buf[]};по очевидным причинам производительности)
Mooing Duck
20

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

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

R .. GitHub СТОП, ПОМОГАЯ ЛЬДУ
источник
+1. Было бы неплохо иметь стандартное место для хранения длины, хотя бы тем из нас, кто хочет что-то вроде префикса длины, не приходилось везде писать тонны «клеевого кода».
Билли Онил
2
Нет никакого стандартного места относительно строковых данных, но вы, конечно, можете использовать отдельную локальную переменную (пересчитывать ее, а не передавать ее, когда последняя не удобна, а первая не слишком расточительна) или структуру с указателем к строке (а еще лучше - флаг, указывающий, «владеет» ли структура указателем для целей выделения или является ли это ссылкой на строку, принадлежащую в другом месте. И, конечно, вы можете включить в структуру гибкий элемент массива для гибкости выделения Строка со структурой, когда она вам подходит
R .. GitHub ОСТАНОВИТЬ, ПОМОГАЯ ЛЬДУ
13

Ленивость, бережливость и переносимость регистров, учитывая сборочную интуицию любого языка, особенно 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-битный юникод получил небольшую и большую последовательность.

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

dvhh
источник
2
@deemoowoor: Concat: O(m+n)с нулевыми строками, O(n)типичными для всех остальных. Длина O(n)с нулевыми строками, O(1)везде. Присоединяйтесь: O(n^2)с нулевыми строками, O(n)везде. В некоторых случаях строки с нулевым символом в конце более эффективны (т. Е. Просто добавляют единицу в регистр указателя), но concat и length являются наиболее распространенными операциями (длина, по крайней мере, требуется для форматирования, вывода файла, отображения на консоли и т. Д.) , Если вы кешируете длину для амортизации, O(n)вы просто отметили, что длина должна быть сохранена вместе со строкой.
Билли ОНил
1
Я согласен с тем, что в сегодняшнем коде этот тип строки неэффективен и подвержен ошибкам, но, например, для отображения консоли не обязательно знать длину строки, чтобы отобразить ее эффективно, вывод файла не должен был знать о строке длина (только выделение кластера на ходу), и форматирование строки в это время было сделано с фиксированной длиной строки в большинстве случаев. В любом случае, вы должны писать плохой код, если ваш конкатат в C имеет сложность O (n ^ 2), я почти уверен, что могу написать один в сложности O (n)
dvhh
1
@dvhh: я не сказал n ^ 2 - я сказал m + n - он все еще линейный, но вам нужно искать конец исходной строки, чтобы выполнить конкатенацию, тогда как с префиксом длины поиск не выполняется необходимо. (Это на самом деле просто еще одно следствие длины, требующей линейного времени)
Билли ONeal
1
@Billy ONeal: из простого любопытства я сделал grep в моем текущем C-проекте (около 50000 строк кода) для вызовов функций манипуляции со строками. strlen 101, strcpy и варианты (strncpy, strlcpy): 85 (у меня также есть несколько сотен литеральных строк, используемых для сообщения, подразумеваемых копий), strcmp: 56, strcat: 13 (и 6 - это конкатенации к строке нулевой длины для вызова strncat) , Я согласен, что префикс длины ускорит вызовы к strlen, но не к strcpy или strcmp (возможно, если strcmp API не использует общий префикс). Самое интересное, что касается приведенных выше комментариев, это то, что strcat встречается очень редко.
Крис
1
@supercat: не совсем, посмотрите на некоторые реализации. Короткие строки используют буфер на основе короткого стека (без выделения кучи), куча используется только тогда, когда они становятся больше. Но не стесняйтесь представить реальную реализацию вашей идеи как библиотеки. Обычно проблемы проявляются только тогда, когда мы добрались до деталей, а не в общем дизайне.
Крис
9

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

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

Терминатор null прост и не требует специальной поддержки языка.

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

Джонатан Вуд
источник
Я не вижу ничего более примитивного в строках с нулевым символом в конце, чем что-либо еще. Паскаль предшествует C и использует префикс длины. Конечно, он был ограничен 256 символами на строку, но простое использование 16-битного поля решило бы проблему в подавляющем большинстве случаев.
Билли Онил
Тот факт, что количество символов ограничено, является именно тем типом проблем, о которых вам нужно подумать при выполнении чего-либо подобного. Да, вы могли бы сделать это длиннее, но тогда байты имели значение. И будет ли 16-битное поле достаточно длинным для всех случаев? Да ладно, вы должны признать, что нулевой термин является концептуально примитивным.
Джонатан Вуд
10
Либо вы ограничиваете длину строки, либо ограничиваете содержимое (без нулевых символов), либо вы соглашаетесь с дополнительными издержками в количестве от 4 до 8 байтов. Там нет бесплатного обеда. На момент начала нулевая завершенная строка имела смысл. В сборке я иногда использовал верхний бит символа, чтобы отметить конец строки, сохранив еще один байт!
Марк Рэнсом
Точно, Марк: Там нет бесплатного обеда. Это всегда компромисс. В наши дни нам не нужно идти на подобные компромиссы. Но тогда этот подход казался таким же хорошим, как и любой другой.
Джонатан Вуд
8

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

Cristian
источник
2
Эээ .. нет, это не так. Подход C вообще не позволяет назначать строку длиной 7 символов для строки длиной 3 символа.
Билли Онил
@Billy ONeal: почему бы и нет? Насколько я понимаю, в этом случае все строки имеют одинаковый тип данных (char *), поэтому длина не имеет значения. В отличие от Паскаля. Но это было ограничением Паскаля, а не проблемой строк с префиксом длины.
Оливер Мейсон
4
@ Билли: Я думаю, что вы только что изложили точку зрения Кристиана. С занимается этими вопросами, вообще не решая их. Вы все еще думаете на языке C, на самом деле содержащем понятие строки. Это просто указатель, так что вы можете назначить его как угодно.
Роберт С Чаччо
2
Это как ** матрица: «нет строки».
Роберт С Чаччо
1
@calavera: я не вижу, как это доказывает что-либо. Вы можете решить это таким же образом с помощью префикса длины ... т.е. вообще не разрешать присваивание.
Билли ОНил
8

Каким-то образом я понял вопрос, заключающийся в том, что компилятор не поддерживает строки с префиксом длины в Си. В следующем примере показано, что, по крайней мере, вы можете запустить свою собственную библиотеку строк 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", как показано в моем примере.

Pyry Jahkola
источник
Проблема в том, что библиотеки не знают о существовании вашей структуры и по-прежнему неправильно обрабатывают такие вещи, как встроенные нули. Кроме того, это не совсем отвечает на вопрос, который я задал.
Билли Онил
1
Это правда. Таким образом, большая проблема в том, что нет лучшего стандартного способа предоставления интерфейсов со строковыми параметрами, чем обычные старые строки с нулевым окончанием. Я по-прежнему утверждаю, что есть библиотеки, которые поддерживают подачу пар длины указателя (ну, по крайней мере, вы можете создать из них st ++ :: string C ++).
Pyry Jahkola
2
Даже если вы храните длину, вы никогда не должны разрешать строки со встроенными нулями. Это основной здравый смысл. Если ваши данные могут содержать нули, вы никогда не должны использовать их с функциями, которые ожидают строки.
R .. GitHub ОСТАНОВИТЬ ЛЬДА
1
@supercat: С точки зрения безопасности, я бы приветствовал эту избыточность. В противном случае невежественные (или лишенные сна) программисты заканчивают тем, что конкатенируют двоичные данные и строки и передают их в вещи, которые ожидают строки с нулевым символом в конце ...
R .. GitHub STOP HELPING ICE
1
@R ..: Хотя методы, которые ожидают строки с нулевым символом в конце, обычно ожидают a char*, многие методы, которые не ожидают нулевого завершения, также ожидают a char*. Более существенное преимущество разделения типов будет связано с поведением Unicode. Может быть целесообразно, чтобы реализация строки поддерживала флаги того, известно ли, что строки содержат определенные виды символов, или известно, что они не содержат их [например, обнаружение 999 990-й кодовой точки в строке из миллиона символов, которая, как известно, не содержит любые символы за пределами основной многоязычной плоскости будут на порядки быстрее ...
суперкат
6

«Даже на 32-битной машине, если вы позволите строке соответствовать размеру доступной памяти, строка с префиксом длины будет всего на три байта шире строки с нулевым символом в конце».

Во-первых, дополнительные 3 байта могут быть значительными издержками для коротких строк. В частности, строка нулевой длины теперь занимает в 4 раза больше памяти. Некоторые из нас используют 64-битные машины, поэтому нам нужно 8 байтов для хранения строки нулевой длины, или формат строки не справляется с самыми длинными строками, поддерживаемыми платформой.

Также могут возникнуть проблемы с выравниванием. Предположим, у меня есть блок памяти, содержащий 7 строк, например «solo \ 0second \ 0 \ 0four \ 0five \ 0 \ 0seventh». Вторая строка начинается со смещения 5. Аппаратное обеспечение может потребовать, чтобы 32-разрядные целые числа были выровнены по адресу, кратному 4, поэтому необходимо добавить заполнение, увеличивая издержки еще больше. С-представление очень эффективно по памяти в сравнении. (Эффективность памяти хорошая, например, она помогает повысить производительность кэша.)

Brangdon
источник
Я полагаю, что обратился ко всему этому в вопросе. Да, на платформах x64 32-битный префикс не может вместить все возможные строки. С другой стороны, вам никогда не понадобится строка, такая большая, как строка с нулевым символом в конце, потому что для выполнения чего-либо вам нужно изучить все 4 миллиарда байтов, чтобы найти конец почти для каждой операции, которую вы можете захотеть сделать с ней. Кроме того, я не говорю, что строки с нулевым символом в конце всегда являются злом - если вы строите одну из этих блочных структур, и ваше конкретное приложение ускоряется с помощью такой конструкции, продолжайте. Я просто хотел бы, чтобы поведение языка по умолчанию не делало этого.
Билли ОНил
2
Я процитировал эту часть вашего вопроса, потому что, на мой взгляд, он недооценил проблему эффективности. Удвоение или увеличение требований к памяти (на 16-битной и 32-битной памяти соответственно) может привести к значительным потерям производительности. Длинные строки могут быть медленными, но, по крайней мере, они поддерживаются и продолжают работать. Мой другой вопрос, о выравнивании, вы вообще не упоминаете.
Брангдон
С выравниванием можно справиться, указав, что значения за пределами UCHAR_MAX должны вести себя так, как если бы они были упакованы и распакованы с использованием доступа к байтам и сдвига битов. Соответствующим образом спроектированный тип строки может предложить эффективность хранения, по существу сопоставимую с строками с нулевым символом в конце, и в то же время разрешить проверку границ для буферов без дополнительных затрат памяти (используйте один бит в префиксе, чтобы сказать, заполнен ли буфер); нет и последний байт не равен нулю, то байт будет представлять собой оставшееся пространство Если буфер не полон , а последний байт равен нулю, то последние 256 байт будет неиспользованным, так что ....
Supercat
... в этом пространстве можно хранить точное количество неиспользуемых байтов с нулевой стоимостью дополнительной памяти). Стоимость работы с префиксами будет компенсирована возможностью использовать такие методы, как fgets () без необходимости передавать длину строки (поскольку буферы будут знать, насколько они велики).
Суперкат
4

Нулевое завершение допускает быстрые операции на основе указателя.

Санджит Салуджа
источник
5
А? Какие «быстрые операции с указателями» не работают с префиксом длины? Что еще более важно, другие языки, которые используют префикс длины, быстрее, чем манипуляции со строками.
Билли ONEAL
12
@billy: С помощью строк с префиксом длины вы не можете просто взять указатель строки и добавить к нему 4, и ожидать, что он все еще будет действительной строкой, потому что у нее нет префикса длины (в любом случае, не является допустимым).
Йорген Сигвардссон
3
@j_random_hacker: конкатенация намного хуже для строк asciiz (O (m + n) вместо потенциально O (n)), и concat встречается гораздо чаще, чем любые другие операции, перечисленные здесь.
Билли ОНил
3
есть одна tiiny операции мало что становится все более дорогим со строками с завершающим нулевыми: strlen. Я бы сказал, что это небольшой недостаток.
Джалф
10
@Billy ONeal: все остальные также поддерживают регулярные выражения. Ну и что ? Используйте библиотеки, для которых они созданы. С о максимальной эффективности и минимализме, не включая батареи. Инструменты C также позволяют очень легко реализовать длину строки с префиксом, используя структуры. И ничто не запрещает вам реализовывать программы для работы со строками, управляя собственной длиной и буферами символов. Это обычно то, что я делаю, когда я хочу повысить эффективность и использовать C, не вызывая горстку функций, которые ожидают ноль в конце буфера символов, не проблема.
Крис
4

Еще один момент, о котором еще не говорилось: когда проектировался C, было много машин, в которых символ char не был восьмибитным (даже сегодня есть платформы DSP, где его нет). Если кто-то решит, что строки должны иметь префикс длины, сколько префикса длины символа 'char следует использовать? Использование двух наложило бы искусственное ограничение на длину строки для машин с 8-битным символом и 32-битным адресным пространством, в то же время тратя пространство на машины с 16-битным символом и 16-битным адресным пространством.

Если кто-то хотел разрешить эффективное хранение строк произвольной длины, и если 'char' всегда был 8-разрядным, то можно - за некоторые затраты в скорости и размере кода - определить схему, в которой строка будет иметь префикс с четным числом N будет иметь длину N / 2 байта, строка с префиксом нечетного значения N и четное значение M (чтение в обратном направлении) могут быть ((N-1) + M * char_max) / 2 и т. Д. И требуют, чтобы любой буфер утверждения о предоставлении определенного объема пространства для хранения строки должны позволять достаточному количеству байтов, предшествующих этому пространству, для обработки максимальной длины. Однако тот факт, что 'char' не всегда 8 бит, усложнит такую ​​схему, поскольку число символов 'char', необходимое для хранения длины строки, будет варьироваться в зависимости от архитектуры процессора.

Supercat
источник
Префикс может легко иметь размер, определяемый реализацией, как и прежде sizeof(char).
Билли ONEAL
@BillyONeal: sizeof(char)это один. Всегда. Можно иметь префикс, определяемый размером реализации, но это будет неудобно. Кроме того, нет никакого реального способа узнать, каким должен быть «правильный» размер. Если один содержит много 4-символьных строк, заполнение нулями приведет к накладным расходам 25%, в то время как префикс длины в четыре байта наложит накладные расходы 100%. Кроме того, время, потраченное на упаковку и распаковку четырехбайтовых префиксов длины, может превысить стоимость сканирования 4-байтовых строк на нулевой байт.
суперкат
1
О да. Ты прав. Префикс может легко быть чем-то отличным от char, хотя. Все, что могло бы привести в соответствие требования выравнивания на целевой платформе, было бы хорошо. Я не пойду туда, хотя - я уже доказывал это до смерти.
Билли ONEAL
Предполагая, что строки имеют префикс длины, вероятно, самым разумным будет size_tпрефикс ( чертова память, черт побери , это будет самый разумный - разрешающий строки любой возможной длины, которые могут поместиться в память). На самом деле, это то, что делает D; массивы struct { size_t length; T* ptr; }, а строки просто массивы immutable(char).
Тим Час
@ TimČas: Если строки не должны быть выровнены по словам, стоимость работы с короткими строками на многих платформах будет зависеть от необходимости упаковки и распаковки длины; Я действительно не считаю это практичным. Если кто-то хочет, чтобы строки были независимыми от содержимого байтовыми массивами произвольного размера, я думаю, что было бы лучше хранить длину отдельно от указателя на символьные данные и иметь язык, позволяющий получать обе части информации для литеральных строк. ,
суперкат
2

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

void add_element_to_next(arr, offset)
  char[] arr;
  int offset;
{
  arr[offset] += arr[offset+1];
}

char array[40];

void test()
{
  for (i=0; i<39; i++)
    add_element_to_next(array, i);
}

против

void add_element_to_next(ptr)
  char *p;
{
  p[0]+=p[1];
}

char array[40];

void test()
{
  int i;
  for (i=0; i<39; i++)
    add_element_to_next(arr+i);
}

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

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

PS - В обмен на небольшое снижение скорости при выполнении некоторых операций и незначительные накладные расходы на более длинные строки было бы возможно иметь методы, работающие со строками, принимающие указатели непосредственно на строки, проверенные на ограничения строк строковые буферы или структуры данных, идентифицирующие подстроки другой строки. Функция типа "strcat" выглядела бы как [современный синтаксис]

void strcat(unsigned char *dest, unsigned char *src)
{
  struct STRING_INFO d,s;
  str_size_t copy_length;

  get_string_info(&d, dest);
  get_string_info(&s, src);
  if (d.si_buff_size > d.si_length) // Destination is resizable buffer
  {
    copy_length = d.si_buff_size - d.si_length;
    if (s.src_length < copy_length)
      copy_length = s.src_length;
    memcpy(d.buff + d.si_length, s.buff, copy_length);
    d.si_length += copy_length;
    update_string_length(&d);
  }
}

Немного больше, чем метод K & R strcat, но он будет поддерживать проверку границ, чего нет у метода K & R. Кроме того, в отличие от текущего способа, можно было бы легко объединить произвольную подстроку, например

/* Concatenate 10th through 24th characters from src to dest */

void catpart(unsigned char *dest, unsigned char *src)
{
  struct SUBSTRING_INFO *inf;
  src = temp_substring(&inf, src, 10, 24);
  strcat(dest, src);
}

Обратите внимание, что время жизни строки, возвращаемой temp_substring, будет ограничено временем sи src, которое когда-либо было короче (именно поэтому метод требуетinf должен быть передан - если он был локальным, он умрет, когда метод вернется).

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

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

Supercat
источник
Нет ничего, что могло бы помешать char* arrуказать на структуру формы struct { int length; char characters[ANYSIZE_ARRAY] };или подобную, которая все еще была бы пригодна для использования в качестве одного параметра.
Билли ОНил
@BillyONeal: две проблемы с этим подходом: (1) это позволило бы только передать строку целиком, тогда как настоящий подход также позволяет пропускать хвост строки; (2) он будет тратить значительное пространство при использовании с небольшими струнами. Если бы K & R захотели потратить некоторое время на струны, они могли бы сделать вещи более надежными, но я не думаю, что они предполагали, что их новый язык будет использоваться через десять лет, а тем более - сорок.
суперкат
1
Этот бит о соглашении о вызовах - это просто история, не имеющая отношения к реальности ... она не учитывалась в дизайне. И соглашения о вызовах на основе регистров уже были «изобретены». Кроме того, подходы, такие как два указателя, не были опцией, потому что структуры не были первого класса ... только примитивы были назначаемыми или проходимыми; копирование структуры не дошло до UNIX V7. Необходимость в memcpy (который также не существует) просто для копирования указателя строки - шутка. Попробуйте написать полную программу, а не только изолированные функции, если вы делаете вид, что создаете язык.
Джим Балтер
1
«это скорее всего потому, что они не хотели тратить много усилий на обработку строк» ​​- ерунда; вся область приложения ранней UNIX была обработкой строк. Если бы не это, мы бы никогда не услышали об этом.
Джим Балтер
1
«Я не думаю, что« символьный буфер начинается с целого, содержащего длину », больше не волшебно» - это если вы собираетесь сделать str[n]ссылку на правильный символ. Это те вещи, о которых люди, обсуждающие это , не думают .
Джим Балтер
2

По словам Джоэла Спольски в этом блоге ,

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

Увидев все остальные ответы здесь, я убежден, что даже если это правда, это только часть причины, по которой в C есть «строки» с нулевым символом в конце. Этот пост довольно убедительно показывает, как простые вещи, такие как строки, могут быть довольно сложными.

Benk
источник
2
Смотри, я уважаю Джоэла за многие вещи; но это то, что он спекулирует. Ответ Ханса Пассанта исходит непосредственно от изобретателей Си.
Билли ОНил
1
Да, но если то, что говорит Спольский, вообще верно, то это было бы частью «удобства», о котором они говорили. Отчасти поэтому я включил этот ответ.
BenK
AFAIK .ASCIZбыл просто оператором ассемблера для построения последовательности байтов, за которой следовал 0. Это просто означает, что строка с нулем в конце была хорошо известной концепцией в то время. Это не означает, что строки с нулевым символом в конце были чем-то связанным с архитектурой PDP- *, за исключением того, что вы могли писать плотные циклы, состоящие из MOVB(скопировать байт) и BNE(ответвление, если последний скопированный байт не был нулевым).
Адриан W
Предполагается показать, что C старый, дряблый, дряхлый язык.
Чист
2

Не обязательно Обоснование, но контрапункт к кодированию длины

  1. Некоторые формы динамического кодирования длины превосходят статическое кодирование длины в том, что касается памяти, все зависит от использования. Просто посмотрите на UTF-8 для доказательства. По сути, это расширяемый массив символов для кодирования одного символа. Это использует один бит для каждого расширенного байта. Окончание NUL использует 8 бит. Префикс длины, я думаю, можно разумно назвать бесконечной длиной, используя 64 бита. То, как часто вы сталкиваетесь с лишними битами, является решающим фактором. Только 1 чрезвычайно большая строка? Кого волнует, используете ли вы 8 или 64 бита? Много маленьких строк (т.е. строк английских слов)? Тогда ваши префиксные расходы составляют большой процент.

  2. Строки с префиксом длины, позволяющие экономить время, не являются реальными вещами . Независимо от того, требуется ли указанная длина предоставленных данных, вы рассчитываете во время компиляции или вам действительно предоставляются динамические данные, которые вы должны закодировать как строку. Эти размеры вычисляются в некоторой точке алгоритма. Отдельные переменный для хранения размера с нулем строки может быть обеспечен. Что делает сравнение на спор по экономии времени. У одного просто есть дополнительный NUL в конце ... но если кодирование длины не включает этот NUL, то между ними буквально нет никакой разницы. Там не требуется никаких алгоритмических изменений. Просто предварительный проход, который вы должны сделать самостоятельно, вместо того, чтобы компилятор / среда выполнения делали это за вас. С в основном о том, чтобы делать вещи вручную.

  3. Длина префикса, являющаяся необязательной, является точкой продажи. Мне не всегда нужна эта дополнительная информация для алгоритма, поэтому необходимость делать это для каждой строки делает мое время до вычислений + вычислений никогда не способным опускаться ниже O (n). (Т.е. аппаратный генератор случайных чисел 1-128. Я могу извлечь из «бесконечной строки». Допустим, он генерирует только символы так быстро. Поэтому длина нашей строки все время меняется. Но мое использование данных, вероятно, не волнует, как у меня много случайных байтов. Он просто хочет получить следующий доступный неиспользуемый байт, как только он сможет получить его после запроса. Я мог бы ждать на устройстве. Но у меня также мог бы быть предварительно прочитанный буфер символов. Сравнение длины ненужная трата вычислений. Нулевая проверка более эффективна.)

  4. Длина префикса является хорошей защитой от переполнения буфера? То же самое относится и к использованию библиотечных функций и их реализации. Что если я передам искаженные данные? Мой буфер имеет длину 2 байта, но я говорю функции, что это 7! Пример: Если gets () предназначался для использования с известными данными, он мог иметь внутреннюю проверку буфера, которая проверяла скомпилированные буферы и malloc ()звонки и все еще следите за спец. Если он предназначался для использования в качестве канала для неизвестного STDIN для достижения неизвестного буфера, то очевидно, что невозможно определить размер буфера, что означает, что длина аргумента не имеет смысла, вам нужно что-то еще здесь, например, канарейка. В этом отношении вы не можете использовать префикс длины некоторых потоков и входных данных, вы просто не можете. Это означает, что проверка длины должна быть встроена в алгоритм, а не в волшебную часть системы набора текста. TL; DR с NUL-завершением никогда не должен был быть небезопасным, он просто оказался таким путем неправильного использования.

  5. встречная точка: NUL-завершение раздражает двоичный файл. Вам нужно либо сделать префикс длины здесь, либо преобразовать байты NUL каким-либо образом: escape-коды, переназначение диапазонов и т. Д., Что, конечно, означает «больше использования памяти / уменьшенная информация / больше операций на байт». Длина префикса в основном выигрывает здесь войну. Единственным преимуществом преобразования является то, что не нужно писать никаких дополнительных функций для покрытия строк с префиксом длины. Это означает, что в ваших более оптимизированных подпрограммах sub-O (n) вы можете автоматически использовать их как O (n) -эквиваленты без добавления дополнительного кода. Недостатком является, конечно, трата времени / памяти / сжатия при использовании на тяжелых струнах NUL.В зависимости от того, сколько вашей библиотеки вы дублируете для работы с двоичными данными, может иметь смысл работать исключительно со строками с префиксом длины. Тем не менее, можно сделать то же самое со строками с префиксом длины ... -1 длина может означать NUL-концевые, и вы можете использовать NUL-концевые строки внутри концевых.

  6. Concat: «O (n + m) против O (m)» Я предполагаю, что вы ссылаетесь на m как общую длину строки после объединения, потому что у них обоих должно быть минимальное количество операций (вы не можете просто прикрепить -на строке 1, что если вам нужно перераспределить?). И я предполагаю, что n - это мифическое количество операций, которые вам больше не нужно выполнять из-за предварительного вычисления. Если это так, то ответ прост: предварительно вычислить.ЕслиВы настаиваете, что у вас всегда будет достаточно памяти, чтобы не нуждаться в перераспределении, и это основа нотации big-O, тогда ответ еще более прост: выполните бинарный поиск по выделенной памяти для конца строки 1, ясно, что есть большой образец бесконечных нулей после строки 1, чтобы мы не беспокоились о realloc. Там легко добрались до логов (n) и я едва попробовал. Который, если вы помните, log (n), по сути, всегда равен 64 на реальном компьютере, что, в сущности, похоже на выражение O (64 + m), которое по существу равно O (m). (И да, эта логика использовалась для анализа реальных структур данных, используемых сегодня во время выполнения. Это не бред с моей головы.)

  7. Concat () / Len () снова : запоминание результатов. Легко. Превращает все вычисления в предварительные вычисления, если это возможно / необходимо. Это алгоритмическое решение. Это не принудительное ограничение языка.

  8. Передача строкового суффикса легче / возможна с завершением NUL. В зависимости от того, как реализован префикс длины, он может быть разрушительным для исходной строки, а иногда даже невозможен. Требовать копию и передать O (n) вместо O (1).

  9. Передача аргумента / разыменование меньше для NUL-терминации по сравнению с префиксом длины. Очевидно, потому что вы передаете меньше информации. Если вам не нужна длина, то это экономит много места и позволяет оптимизировать.

  10. Вы можете обмануть. Это действительно просто указатель. Кто сказал, что вы должны прочитать это как строку? Что если вы хотите прочитать его как один символ или как число с плавающей точкой? Что делать, если вы хотите сделать обратное и читать число с плавающей точкой как строку? Если вы осторожны, вы можете сделать это с NUL-терминацией. Вы не можете сделать это с префиксом длины, это тип данных, отчетливо отличающийся от указателя. Скорее всего, вам придется построить строку побайтно и получить длину. Конечно, если вы хотите что-то наподобие целого числа с плавающей точкой (возможно, внутри него есть NUL), вам все равно придется читать побайтово, но подробности оставлены на ваше усмотрение.

TL; DR Вы используете двоичные данные? Если нет, то NUL-завершение дает больше алгоритмической свободы. Если да, то количество кода против скорости / памяти / сжатия - ваша основная проблема. Смесь двух подходов или запоминание может быть лучшим.

черный
источник
9 был своего рода неосновным / неправильно представлен. Длина префикса не имеет этой проблемы. Длина, передаваемая как отдельная переменная. Мы говорили о префиксе, но я увлекся. Все еще хорошо подумать, поэтому я оставлю это там. : d
Black
1

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

Разработчики Windows / COM будут хорошо знакомы с BSTRтипом, который в точности подобен этому - строка C с префиксом длины, где фактические символьные данные начинаются не с байта 0.

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

Мистер Бой
источник
-3

GCC принимает коды ниже:

char s [4] = "abcd";

и это нормально, если мы рассматриваем это как массив символов, а не как строку. То есть мы можем получить к нему доступ с помощью s [0], s [1], s [2] и s [3] или даже с помощью memcpy (dest, s, 4). Но мы получим беспорядочные символы, когда будем пытаться использовать put (s) или, что еще хуже, strcpy (dest, s).

kkaaii
источник
@Adrian W. Это допустимый C. Строки точной длины имеют специальный регистр, и NUL для них опущен. Как правило, это неразумная практика, но может быть полезно в таких случаях, как заполнение структур заголовков, использующих «строки» FourCC.
Кевин Тибедо
Ты прав. Это допустимый C, он скомпилируется и ведет себя так, как описано в kkaaii. Причина отрицательных голосов (не моя ...), скорее всего, в том, что этот ответ никак не отвечает на вопрос ОП.
Адриан Ш