Столько, сколько я люблю 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 и друзей).
Ничто из вышеперечисленного не встречается так часто, как длина и конкат.
В ответах ниже утверждается еще одно:
- Вам нужно отрезать конец строки
но это неверно - это одинаковое количество времени для строк с нулевым символом в конце и длиной с префиксом. (Строки с нулевым символом в конце просто вставляют ноль там, где вы хотите, чтобы новый конец был, префиксы длины просто вычитают из префикса.)
источник
Ответы:
Из рта лошади
Деннис М Ричи, Развитие языка Си
источник
C не имеет строки как части языка. «Строка» в C - это просто указатель на char. Так что, возможно, вы задаете не тот вопрос.
«Какой смысл опускать строковый тип» может быть более уместным. На это я хотел бы указать, что C не является объектно-ориентированным языком и имеет только базовые типы значений. Строка - это концепция более высокого уровня, которая должна быть реализована путем объединения значений других типов. C находится на более низком уровне абстракции.
в свете бушующего шквала внизу:
Я просто хочу отметить, что я не пытаюсь сказать, что это глупый или плохой вопрос, или что способ представления строк на языке C - лучший выбор. Я пытаюсь уточнить, что вопрос был бы более лаконичным, если принять во внимание тот факт, что в C нет механизма для дифференциации строки как типа данных от байтового массива. Это лучший выбор в свете вычислительной мощности и мощности памяти современных компьютеров? Возможно нет. Но задним числом всегда 20/20 и все такое :)
источник
char *temp = "foo bar";
является действительным утверждением на C ... эй! разве это не строка? разве это не завершено?Вопрос задается как вещь
Length Prefixed Strings (LPS)
противzero terminated strings (SZ)
, но в основном раскрывают преимущества строк с префиксом длины. Это может показаться подавляющим, но, честно говоря, мы должны также учитывать недостатки LPS и преимущества SZ.Насколько я понимаю, вопрос можно даже понимать как предвзятый способ задать вопрос: «Каковы преимущества нулевых терминированных строк?».
Преимущества (я вижу) Zero Termination Strings:
"this\0is\0valid\0C"
. Это строка? или четыре строки? Или куча байтов ...char a[3] = "foo";
является допустимым C (не C ++) и не ставит конечный ноль в.char*
. А именно, чтобы не возвращать адрес строки, а вместо этого возвращать фактические данные.Тем не менее, нет необходимости жаловаться в редком случае, когда стандартные строки 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).
источник
std::basic_string
делает.\0
в конце, когда программисты хотят этого вместо неявного. Предварительная длина намного хуже.Я думаю, это имеет исторические причины и нашел это в википедии :
источник
Calavera этого права , но люди не похоже , чтобы получить свою точку зрения, я приведу некоторые примеры кода.
Сначала давайте рассмотрим, что такое C: простой язык, где весь код имеет довольно прямой перевод на машинный язык. Все типы вписываются в регистры и в стек, и для этого не требуется операционная система или большая библиотека времени выполнения, поскольку она предназначена для записи этих вещей (задача, которая прекрасно подходит, учитывая, что даже не вероятный конкурент по сей день).
Если бы C имел
string
тип, вродеint
илиchar
, это был бы тип, который не помещался в регистр или в стек и требовал бы распределения памяти (со всей его поддерживающей инфраструктурой) любым способом. Все из которых идут вразрез с основными принципами C.Итак, строка в C:
Итак, давайте предположим, что это с префиксом длины. Давайте напишем код для объединения двух строк:
Другой альтернативой будет использование структуры для определения строки:
На этом этапе все манипуляции со строками потребовали бы двух выделений, что на практике означает, что вы будете проходить через библиотеку для какой-либо обработки.
Самое смешное ... как Структуры , которые делают существуют в C! Они просто не используются для ежедневного отображения сообщений для обработки пользователем.
Итак, вот что делает Калавера: в Си нет строкового типа . Чтобы что-то с этим сделать, вам нужно взять указатель и декодировать его как указатель на два разных типа, и тогда он становится очень уместным, каков размер строки, и его нельзя просто оставить как «определенный реализацией».
Теперь C может обрабатывать память в любом случае, а
mem
функции в библиотеке (<string.h>
даже!) Предоставляют все необходимые инструменты для обработки памяти в виде пары указателей и размеров. Так называемые «строки» в C были созданы только для одной цели: показывать сообщения в контексте написания операционной системы, предназначенной для текстовых терминалов. И для этого достаточно нулевого завершения.источник
strlen
и друзьями. Что касается проблемы с «оставлением ее на усмотрение реализации», вы можете сказать, что префикс - это то, чтоshort
находится в поле назначения. Тогда все ваши кастинги все равно будут работать. 3. Я могу придумывать надуманные сценарии в течение всего дня, из-за которых та или иная система выглядит плохо.short
эффективно ограничивает размер строки, что, кажется, было единственной вещью, которой они не интересовались. Я сам, работая с 8-битными строками BASIC и Pascal, строками COBOL фиксированного размера и подобными вещами, быстро стал большим поклонником C-строк неограниченного размера. В настоящее время 32-битный размер будет обрабатывать любую практическую строку, но добавление этих байтов на ранних этапах было проблематичным.string
типу: она не знает символов. Это массив «char» («char» в машинном жаргоне - это такой же символ, как «слово» - это то, что люди называют словом в предложении). Строка символов - это концепция более высокого уровня, которая может быть реализована поверх массива,char
если вы ввели понятие кодирования.buf
требуется только выделение), либо используйтеstruct string {int len; char buf[]};
и выделите все это с одним выделением в качестве члена гибкого массива, и передайте его как astring*
. (Или, возможно,struct string {int capacity; int len; char buf[]};
по очевидным причинам производительности)Очевидно, что с точки зрения производительности и безопасности вы захотите сохранить длину строки во время работы с ней, а не выполнять ее повторно
strlen
или эквивалентную ей. Однако хранение длины в фиксированном месте непосредственно перед содержимым строки является невероятно плохим дизайном. Как отметил Йорген в комментариях к ответу Санджита, это исключает обращение с хвостом строки как строкой, что, например, делает многие общие операции похожимиpath_to_filename
илиfilename_to_extension
невозможными без выделения новой памяти (а также возникновения возможности сбоя и обработки ошибок). , И, конечно же, есть проблема, что никто не может согласиться с тем, сколько байтов должно занимать поле длины строки (много плохих «строк Паскаля»Конструкция C, позволяющая программисту выбирать, где / где / как хранить длину, гораздо более гибкая и мощная. Но, конечно, программист должен быть умным. Си наказывает за глупость программами, которые аварийно завершают работу, останавливаются или дают врагам корень.
источник
Ленивость, бережливость и переносимость регистров, учитывая сборочную интуицию любого языка, особенно C, который находится на один шаг выше сборки (таким образом наследуя большое количество унаследованного кода сборки). Вы согласитесь, что нулевой символ будет бесполезен в те дни ASCII, и он (и, вероятно, так же хорош, как контрольный символ EOF).
давайте посмотрим в псевдокоде
всего 1 использование регистра
случай 2
всего используется 2 регистра
Это может показаться недальновидным в то время, но учитывая бережливость кода и регистра (которые были ПРЕМИУМ в то время, когда вы знаете, они использовали перфокарту). Таким образом, будучи «быстрее» (когда скорость процессора можно считать в кГц), этот «хак» был чертовски хорош и легко переносим для процессора без регистрации.
Ради аргумента я буду реализовывать 2 обычные строковые операции
сложность O (n), где в большинстве случаев строка PASCAL равна O (1), потому что длина строки предварительно зависит от структуры строки (это также будет означать, что эта операция должна быть выполнена на более ранней стадии).
сложность 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-битный юникод получил небольшую и большую последовательность.
Конечно, у С тоже будут свои проблемы, но затронутые здесь вопросы будут очень мало затронуты.
источник
O(m+n)
с нулевыми строками,O(n)
типичными для всех остальных. ДлинаO(n)
с нулевыми строками,O(1)
везде. Присоединяйтесь:O(n^2)
с нулевыми строками,O(n)
везде. В некоторых случаях строки с нулевым символом в конце более эффективны (т. Е. Просто добавляют единицу в регистр указателя), но concat и length являются наиболее распространенными операциями (длина, по крайней мере, требуется для форматирования, вывода файла, отображения на консоли и т. Д.) , Если вы кешируете длину для амортизации,O(n)
вы просто отметили, что длина должна быть сохранена вместе со строкой.Во многих отношениях С был примитивным. И мне это понравилось.
Это был шаг вперед по сравнению с языком ассемблера, обеспечивающий почти одинаковую производительность с языком, который было намного легче писать и поддерживать.
Терминатор null прост и не требует специальной поддержки языка.
Оглядываясь назад, это не кажется удобным. Но я использовал язык ассемблера еще в 80-х, и в то время он казался очень удобным. Я просто думаю, что программное обеспечение постоянно развивается, а платформы и инструменты постоянно совершенствуются.
источник
Предположим на мгновение, что C реализовал строки способом Pascal, добавив к ним префикс по длине: является ли строка длиной 7 символов таким же ТИПОМ ДАННЫХ, как строка из 3 символов? Если ответ «да», то какой код должен генерировать компилятор, когда я назначаю первый последнему? Должна ли строка быть усечена или автоматически изменена? Если изменить размер, должна ли эта операция быть защищена блокировкой, чтобы сделать ее безопасной для потока? Сторона подхода C перешагнула все эти вопросы, нравится нам это или нет :)
источник
Каким-то образом я понял вопрос, заключающийся в том, что компилятор не поддерживает строки с префиксом длины в Си. В следующем примере показано, что, по крайней мере, вы можете запустить свою собственную библиотеку строк C, где длины строк подсчитываются во время компиляции, с помощью такой конструкции:
Это, однако, не приведет к проблемам, так как вам нужно быть осторожным, когда нужно конкретно освобождать этот указатель строки и когда он статически размещается (литеральный
char
массив).Редактировать: как более прямой ответ на вопрос, я считаю, что именно так C мог поддерживать обе длины строки (как постоянную времени компиляции), если вам это нужно, но все еще без лишних затрат памяти, если вы хотите использовать только указатели и нулевое завершение.
Конечно, кажется, что работа со строками с нулевым символом в конце была рекомендуемой практикой, поскольку стандартная библиотека в общем случае не принимает длины строк в качестве аргументов, и поскольку извлечение длины не так просто
char * s = "abc"
, как показано в моем примере.источник
char*
, многие методы, которые не ожидают нулевого завершения, также ожидают achar*
. Более существенное преимущество разделения типов будет связано с поведением Unicode. Может быть целесообразно, чтобы реализация строки поддерживала флаги того, известно ли, что строки содержат определенные виды символов, или известно, что они не содержат их [например, обнаружение 999 990-й кодовой точки в строке из миллиона символов, которая, как известно, не содержит любые символы за пределами основной многоязычной плоскости будут на порядки быстрее ...Во-первых, дополнительные 3 байта могут быть значительными издержками для коротких строк. В частности, строка нулевой длины теперь занимает в 4 раза больше памяти. Некоторые из нас используют 64-битные машины, поэтому нам нужно 8 байтов для хранения строки нулевой длины, или формат строки не справляется с самыми длинными строками, поддерживаемыми платформой.
Также могут возникнуть проблемы с выравниванием. Предположим, у меня есть блок памяти, содержащий 7 строк, например «solo \ 0second \ 0 \ 0four \ 0five \ 0 \ 0seventh». Вторая строка начинается со смещения 5. Аппаратное обеспечение может потребовать, чтобы 32-разрядные целые числа были выровнены по адресу, кратному 4, поэтому необходимо добавить заполнение, увеличивая издержки еще больше. С-представление очень эффективно по памяти в сравнении. (Эффективность памяти хорошая, например, она помогает повысить производительность кэша.)
источник
Нулевое завершение допускает быстрые операции на основе указателя.
источник
strlen
. Я бы сказал, что это небольшой недостаток.Еще один момент, о котором еще не говорилось: когда проектировался C, было много машин, в которых символ char не был восьмибитным (даже сегодня есть платформы DSP, где его нет). Если кто-то решит, что строки должны иметь префикс длины, сколько префикса длины символа 'char следует использовать? Использование двух наложило бы искусственное ограничение на длину строки для машин с 8-битным символом и 32-битным адресным пространством, в то же время тратя пространство на машины с 16-битным символом и 16-битным адресным пространством.
Если кто-то хотел разрешить эффективное хранение строк произвольной длины, и если 'char' всегда был 8-разрядным, то можно - за некоторые затраты в скорости и размере кода - определить схему, в которой строка будет иметь префикс с четным числом N будет иметь длину N / 2 байта, строка с префиксом нечетного значения N и четное значение M (чтение в обратном направлении) могут быть ((N-1) + M * char_max) / 2 и т. Д. И требуют, чтобы любой буфер утверждения о предоставлении определенного объема пространства для хранения строки должны позволять достаточному количеству байтов, предшествующих этому пространству, для обработки максимальной длины. Однако тот факт, что 'char' не всегда 8 бит, усложнит такую схему, поскольку число символов 'char', необходимое для хранения длины строки, будет варьироваться в зависимости от архитектуры процессора.
источник
sizeof(char)
.sizeof(char)
это один. Всегда. Можно иметь префикс, определяемый размером реализации, но это будет неудобно. Кроме того, нет никакого реального способа узнать, каким должен быть «правильный» размер. Если один содержит много 4-символьных строк, заполнение нулями приведет к накладным расходам 25%, в то время как префикс длины в четыре байта наложит накладные расходы 100%. Кроме того, время, потраченное на упаковку и распаковку четырехбайтовых префиксов длины, может превысить стоимость сканирования 4-байтовых строк на нулевой байт.size_t
префикс ( чертова память, черт побери , это будет самый разумный - разрешающий строки любой возможной длины, которые могут поместиться в память). На самом деле, это то, что делает D; массивыstruct { size_t length; T* ptr; }
, а строки просто массивыimmutable(char)
.Многие проектные решения, связанные с C, проистекают из того факта, что когда он был изначально реализован, передача параметров была несколько дорогой. Учитывая выбор между, например,
против
последний был бы немного дешевле (и, следовательно, предпочтительным), поскольку требовал передачи только одного параметра, а не двух. Если вызываемому методу не нужно знать базовый адрес массива или индекс внутри него, передача одного указателя, объединяющего два, будет дешевле, чем передача значений по отдельности.
Хотя существует много разумных способов, которыми C мог бы кодировать длины строк, подходы, которые были изобретены до этого времени, имели бы все требуемые функции, которые должны были бы работать с частью строки, чтобы принимать базовый адрес строки и желаемый индекс как два отдельных параметра. Использование нулевого байтового завершения позволило избежать этого требования. Хотя другие подходы были бы лучше с современными машинами (современные компиляторы часто передают параметры в регистрах, и memcpy можно оптимизировать способами strcpy () - эквиваленты не могут), достаточно производственного кода, использующего строки с нулевым байтом, которые трудно изменить на что-либо другое.
PS - В обмен на небольшое снижение скорости при выполнении некоторых операций и незначительные накладные расходы на более длинные строки было бы возможно иметь методы, работающие со строками, принимающие указатели непосредственно на строки, проверенные на ограничения строк строковые буферы или структуры данных, идентифицирующие подстроки другой строки. Функция типа "strcat" выглядела бы как [современный синтаксис]
Немного больше, чем метод K & R strcat, но он будет поддерживать проверку границ, чего нет у метода K & R. Кроме того, в отличие от текущего способа, можно было бы легко объединить произвольную подстроку, например
Обратите внимание, что время жизни строки, возвращаемой temp_substring, будет ограничено временем
s
иsrc
, которое когда-либо было короче (именно поэтому метод требуетinf
должен быть передан - если он был локальным, он умрет, когда метод вернется).С точки зрения стоимости памяти строки и буферы размером до 64 байт будут иметь один байт служебной информации (такой же, как строки с нулевым символом в конце); более длинные строки будут иметь немного больше (допустимо ли одно количество служебных данных между двумя байтами, а максимальный требуемый будет компромисс между временем и пространством). Специальное значение байта длины / режима будет использоваться для указания того, что строковой функции была дана структура, содержащая байт флага, указатель и длину буфера (которая затем может произвольно индексироваться в любую другую строку).
Конечно, K & R не реализовала ничего подобного, но, скорее всего, потому, что они не хотели тратить много усилий на обработку строк - область, где даже сегодня многие языки кажутся довольно анемичными.
источник
char* arr
указать на структуру формыstruct { int length; char characters[ANYSIZE_ARRAY] };
или подобную, которая все еще была бы пригодна для использования в качестве одного параметра.str[n]
ссылку на правильный символ. Это те вещи, о которых люди, обсуждающие это , не думают .По словам Джоэла Спольски в этом блоге ,
Увидев все остальные ответы здесь, я убежден, что даже если это правда, это только часть причины, по которой в C есть «строки» с нулевым символом в конце. Этот пост довольно убедительно показывает, как простые вещи, такие как строки, могут быть довольно сложными.
источник
.ASCIZ
был просто оператором ассемблера для построения последовательности байтов, за которой следовал0
. Это просто означает, что строка с нулем в конце была хорошо известной концепцией в то время. Это не означает, что строки с нулевым символом в конце были чем-то связанным с архитектурой PDP- *, за исключением того, что вы могли писать плотные циклы, состоящие изMOVB
(скопировать байт) иBNE
(ответвление, если последний скопированный байт не был нулевым).Не обязательно Обоснование, но контрапункт к кодированию длины
Некоторые формы динамического кодирования длины превосходят статическое кодирование длины в том, что касается памяти, все зависит от использования. Просто посмотрите на UTF-8 для доказательства. По сути, это расширяемый массив символов для кодирования одного символа. Это использует один бит для каждого расширенного байта. Окончание NUL использует 8 бит. Префикс длины, я думаю, можно разумно назвать бесконечной длиной, используя 64 бита. То, как часто вы сталкиваетесь с лишними битами, является решающим фактором. Только 1 чрезвычайно большая строка? Кого волнует, используете ли вы 8 или 64 бита? Много маленьких строк (т.е. строк английских слов)? Тогда ваши префиксные расходы составляют большой процент.
Строки с префиксом длины, позволяющие экономить время, не являются реальными вещами . Независимо от того, требуется ли указанная длина предоставленных данных, вы рассчитываете во время компиляции или вам действительно предоставляются динамические данные, которые вы должны закодировать как строку. Эти размеры вычисляются в некоторой точке алгоритма. Отдельные переменный для хранения размера с нулем строки может быть обеспечен. Что делает сравнение на спор по экономии времени. У одного просто есть дополнительный NUL в конце ... но если кодирование длины не включает этот NUL, то между ними буквально нет никакой разницы. Там не требуется никаких алгоритмических изменений. Просто предварительный проход, который вы должны сделать самостоятельно, вместо того, чтобы компилятор / среда выполнения делали это за вас. С в основном о том, чтобы делать вещи вручную.
Длина префикса, являющаяся необязательной, является точкой продажи. Мне не всегда нужна эта дополнительная информация для алгоритма, поэтому необходимость делать это для каждой строки делает мое время до вычислений + вычислений никогда не способным опускаться ниже O (n). (Т.е. аппаратный генератор случайных чисел 1-128. Я могу извлечь из «бесконечной строки». Допустим, он генерирует только символы так быстро. Поэтому длина нашей строки все время меняется. Но мое использование данных, вероятно, не волнует, как у меня много случайных байтов. Он просто хочет получить следующий доступный неиспользуемый байт, как только он сможет получить его после запроса. Я мог бы ждать на устройстве. Но у меня также мог бы быть предварительно прочитанный буфер символов. Сравнение длины ненужная трата вычислений. Нулевая проверка более эффективна.)
Длина префикса является хорошей защитой от переполнения буфера? То же самое относится и к использованию библиотечных функций и их реализации. Что если я передам искаженные данные? Мой буфер имеет длину 2 байта, но я говорю функции, что это 7! Пример: Если gets () предназначался для использования с известными данными, он мог иметь внутреннюю проверку буфера, которая проверяла скомпилированные буферы и malloc ()звонки и все еще следите за спец. Если он предназначался для использования в качестве канала для неизвестного STDIN для достижения неизвестного буфера, то очевидно, что невозможно определить размер буфера, что означает, что длина аргумента не имеет смысла, вам нужно что-то еще здесь, например, канарейка. В этом отношении вы не можете использовать префикс длины некоторых потоков и входных данных, вы просто не можете. Это означает, что проверка длины должна быть встроена в алгоритм, а не в волшебную часть системы набора текста. TL; DR с NUL-завершением никогда не должен был быть небезопасным, он просто оказался таким путем неправильного использования.
встречная точка: NUL-завершение раздражает двоичный файл. Вам нужно либо сделать префикс длины здесь, либо преобразовать байты NUL каким-либо образом: escape-коды, переназначение диапазонов и т. Д., Что, конечно, означает «больше использования памяти / уменьшенная информация / больше операций на байт». Длина префикса в основном выигрывает здесь войну. Единственным преимуществом преобразования является то, что не нужно писать никаких дополнительных функций для покрытия строк с префиксом длины. Это означает, что в ваших более оптимизированных подпрограммах sub-O (n) вы можете автоматически использовать их как O (n) -эквиваленты без добавления дополнительного кода. Недостатком является, конечно, трата времени / памяти / сжатия при использовании на тяжелых струнах NUL.В зависимости от того, сколько вашей библиотеки вы дублируете для работы с двоичными данными, может иметь смысл работать исключительно со строками с префиксом длины. Тем не менее, можно сделать то же самое со строками с префиксом длины ... -1 длина может означать NUL-концевые, и вы можете использовать NUL-концевые строки внутри концевых.
Concat: «O (n + m) против O (m)» Я предполагаю, что вы ссылаетесь на m как общую длину строки после объединения, потому что у них обоих должно быть минимальное количество операций (вы не можете просто прикрепить -на строке 1, что если вам нужно перераспределить?). И я предполагаю, что n - это мифическое количество операций, которые вам больше не нужно выполнять из-за предварительного вычисления. Если это так, то ответ прост: предварительно вычислить.ЕслиВы настаиваете, что у вас всегда будет достаточно памяти, чтобы не нуждаться в перераспределении, и это основа нотации big-O, тогда ответ еще более прост: выполните бинарный поиск по выделенной памяти для конца строки 1, ясно, что есть большой образец бесконечных нулей после строки 1, чтобы мы не беспокоились о realloc. Там легко добрались до логов (n) и я едва попробовал. Который, если вы помните, log (n), по сути, всегда равен 64 на реальном компьютере, что, в сущности, похоже на выражение O (64 + m), которое по существу равно O (m). (И да, эта логика использовалась для анализа реальных структур данных, используемых сегодня во время выполнения. Это не бред с моей головы.)
Concat () / Len () снова : запоминание результатов. Легко. Превращает все вычисления в предварительные вычисления, если это возможно / необходимо. Это алгоритмическое решение. Это не принудительное ограничение языка.
Передача строкового суффикса легче / возможна с завершением NUL. В зависимости от того, как реализован префикс длины, он может быть разрушительным для исходной строки, а иногда даже невозможен. Требовать копию и передать O (n) вместо O (1).
Передача аргумента / разыменование меньше для NUL-терминации по сравнению с префиксом длины. Очевидно, потому что вы передаете меньше информации. Если вам не нужна длина, то это экономит много места и позволяет оптимизировать.
Вы можете обмануть. Это действительно просто указатель. Кто сказал, что вы должны прочитать это как строку? Что если вы хотите прочитать его как один символ или как число с плавающей точкой? Что делать, если вы хотите сделать обратное и читать число с плавающей точкой как строку? Если вы осторожны, вы можете сделать это с NUL-терминацией. Вы не можете сделать это с префиксом длины, это тип данных, отчетливо отличающийся от указателя. Скорее всего, вам придется построить строку побайтно и получить длину. Конечно, если вы хотите что-то наподобие целого числа с плавающей точкой (возможно, внутри него есть NUL), вам все равно придется читать побайтово, но подробности оставлены на ваше усмотрение.
TL; DR Вы используете двоичные данные? Если нет, то NUL-завершение дает больше алгоритмической свободы. Если да, то количество кода против скорости / памяти / сжатия - ваша основная проблема. Смесь двух подходов или запоминание может быть лучшим.
источник
Я не покупаю ответ "С не имеет строки". Правда, C не поддерживает встроенные высокоуровневые типы, но вы все равно можете представлять структуры данных в C, и это и есть строка. Тот факт, что строка является просто указателем в C, не означает, что первые N байтов не могут иметь специального значения как длина.
Разработчики Windows / COM будут хорошо знакомы с
BSTR
типом, который в точности подобен этому - строка C с префиксом длины, где фактические символьные данные начинаются не с байта 0.Таким образом, кажется, что решение использовать нулевое окончание - это просто то, что люди предпочитают, а не необходимость языка.
источник
GCC принимает коды ниже:
char s [4] = "abcd";
и это нормально, если мы рассматриваем это как массив символов, а не как строку. То есть мы можем получить к нему доступ с помощью s [0], s [1], s [2] и s [3] или даже с помощью memcpy (dest, s, 4). Но мы получим беспорядочные символы, когда будем пытаться использовать put (s) или, что еще хуже, strcpy (dest, s).
источник