Может ли реализация C использовать строки с префиксом длины под капотом?

Вы можете сохранить длину распределения. И malloc реализации действительно это делают (или, по крайней мере, некоторые).

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

Затем, если N-й символ равен '\0', N - 1 будет обозначать длину строки.

На самом деле нет, и поэтому это предложение не работает.

Если я заменяю символ в строке на 0, я фактически усекаю строку, и последующий вызов strlen для строки должен возвращать усеченную длину. (Обычно это делается прикладными программами, включая все сканеры, созданные (f)lex, а также функцию стандартной библиотеки strtok. Среди прочих.)

Более того, вполне законно вызывать strlen для внутреннего байта строки.

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

/* Split a string like 'key=value...' into key and value parts, and
 * return the value, and optionally its length (if the second argument
 * is not a NULL pointer). 
 * On success, returns the value part and modifieds the original string
 * so that it is the key.
 * If there is no '=' in the supplied string, neither it nor the value
 * pointed to by plen are modified, and NULL is returned.
 */
char* keyval_split(char* keyval, int* plen) {
  char* delim = strchr(keyval, '=');
  if (delim) {
    if (plen) *plen = strlen(delim + 1)
    *delim = 0;
    return delim + 1;
  } else {
    return NULL;
  }
}

Ничто принципиально не мешает вам сделать это в вашем приложении, если это было полезно (один из комментариев отметил это). Однако могут возникнуть две проблемы:

1. Вам придется заново реализовать все функции обработки строк, добавить my_strlen, my_strcpy и т. д., а также добавить функции создания строк. Это может раздражать, но это ограниченная проблема.

2. Вам придется останавливать людей при написании для системы, преднамеренно или автоматически обрабатывающих связанные массивы символов как «обычные» строки C и использующие для них обычные функции. Возможно, вам придется убедиться, что такие обычаи быстро ломаются.

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

Что-то вроде

typedef struct {
    size_t len;
    char* buf;
} String;
size_t my_strlen(String*);
...

может сработать, так как проверка типов разочарует (2) (если только кто-то не решил взломать что-то «для эффективности», и в этом случае вы мало что можете сделать).

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

Есть несколько проблем с этим подходом. Прежде всего, вы не сможете создавать произвольно длинные строки. Если вы зарезервируете только 1 байт для длины, ваша строка может содержать не более 255 символов. Конечно, вы можете использовать больше байтов для хранения длины, но сколько? 2? 4?

Что произойдет, если вы попытаетесь соединить две строки, каждая из которых находится на грани своих ограничений по размеру (т. е. если вы используете 1 байт для длины и пытаетесь соединить две строки по 250 символов друг с другом, что произойдет)? Вы просто добавляете больше байтов к длине по мере необходимости?

Во-вторых, где вы храните эти метаданные? Это как-то должно быть связано со строкой. Это похоже на проблему, с которой столкнулся Деннис Ритчи, когда он реализовывал массивы в C. Первоначально объекты массива хранили явный указатель на первый элемент массива, но когда он добавил в язык struct типы, он понял, что не Он не хотел, чтобы метаданные загромождали представление объекта struct в памяти, поэтому он избавился от них и ввел правило, согласно которому выражения массива в большинстве случаев преобразуются в выражения указателя.

Вы можете создать новый агрегатный тип, например

struct string
{
  char *data;
  size_t len;
};

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

Вы можете сохранить длину в начальном байте или байтах строки, но сколько вы резервируете? Вы могли бы использовать переменное количество байтов для хранения длины, но теперь вам нужен способ отличить байты длины от байтов содержимого, и вы не можете прочитать первый символ, просто разыменовав указатель. Такие функции, как strcat, должны знать, как обойти байты длины, как настроить содержимое, если количество байтов длины изменится и т. д.

У подхода с завершающим 0 есть свои недостатки, но он также чертовски прост в реализации и значительно упрощает манипулирование строками.

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

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

ns_output(my_file, "This is a test"); // ns -- new string

нужно было бы сказать что-то более похожее на:

MAKE_NEW_STRING(this_is_a_test, "This is a test");
ns_output(my_file, this_is_a_test);

где макрос MAKE_NEW_STRING создаст объединение анонимного типа, определит экземпляр с именем this_is_a_test и соответствующим образом инициализирует его. Поскольку многие строки будут иметь разные анонимные типы, проверка типов потребует, чтобы строки были объединениями, включающими элемент известного типа массива, а коду, ожидающему строки, должен быть предоставлен указатель на этот элемент, вероятно, с использованием чего-то вроде:

#define ns_output(f,s) (ns_output_func((f),(s).stringref))

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

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