# NULL-терминированные строки

В начале 70-х Кен Томпсон, Деннис Ритчи и Брайан Керниган, работая над первыми версиями C и Unix, приняли решение, которое отзывается болью, страданиями, багами и неэффективностью до сих пор, спустя 50 лет.
Они решили, строки, как данные переменной длины, нужно представлять в виде последовательности, заканчивающейся терминирующим символом -- нулем. Так делали в ассемблере, а C ведь высокоуровневый ассемблер! Да и памяти у старенького PDP не много: лучше всего один байтик лишний на строку, чем 2, 4, а то и все 8 байтов для хранения размера в зависимости от платформы... Не, лучше байтик в конце!
Но в других языках почему-то предпочли хранить размер и ссылку/указатель на данные...

Ну что ж, посмотрим, к чему это привело

### Длина строки

Единственный способ узнать длину NULL-термирированной строки -- пройтись по ней и посчитать символы. Это требует линейного времени от длины строки.

```C++
const char* str = ...;
for (size_t i = 0 ; i < strlen(str); ++i) {
    ...
}
```

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

```C++
const char* str = ...;
const size_t len = strlen(str);
for (size_t i =0 ; i < len; ++i) {
    ...
}
```

Но ведь пример может быть и посложнее. В коде одной там популярной игры про деньги, разборки мафии и угон автомобилей обнаружили занятный пример парсинга большого массива чисел из json-строки с помощью `sscanf`

Выглядел он примерно (его получили путем реверс-инженеринга конечного бинарного файла) так

```C++
const char* config = ...;
size_t N = ...;

for (size_t i  =0 ; i < N; ++i) {
    int value = 0;
    size_t parsed = sscanf(config, "%d", &value);
    if parsed > 0 {
        config += parsed;
    }
}
```

Прекрасный и замечательный цикл! Тело его выполняется всего `N` раз, но на большинстве версий стандартной библиотеки C каждый раз требует `strlen(config)`  операций на интерацию. Ведь `sscanf` должен посчитать длину строки, чтоб случайно не выйти за ее пределы! А строка NULL-терминированная.

Вычисление длины строки -- невероятно часто всречающаяся операция. И один из самых первых кандидатов на оптимизацию -- посчитать ее один раз и хранить со строкою... Но зачем тогда NULL-терминатор? Только лишний байт в памяти!


### С++ и std::string

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

Но не совсем ура. Ведь огромное число C библиотек никуда не денется, и у большинства из них в интерфейсах используются NULL-терминированные строки.
Поэтому `std::string` тоже обязательно NULL-терминированные. Поздравляю, мы храним один лишний байт ради совместимости. А еще мы его храним неявно: `std::string::capacity()` на самом деле всегда на 1 меньше действительно выделенного блока памяти.

### C++ и std::string_view

"Используйте `std::string_view` в своих API и вам не придется писать перегрузки для `const char*` и `const std::string&` чтобы избежать лишнего копирования!"

Ага, конечно.

`std::string_view` это тоже указатель + длина строки. Но уже, в отличие от `std::string`, указатель не обязательно на NULL-терминированную строку (Ура, мы можем использовать `std::vector` и не хранить лишний байт!).

Но если вдруг за фасадом вашего удобного API со `string_view` скрывается обращение к какой-нибудь сишной библиотеке, требующей NULL-терминированную строку...

```C++
// Эта маленькая программа весело и задорно выведет

// Hello
// Hello World

// Хотите вы этого или нет.

void print_me(std::string_view s) {
    printf("%s\n", s.data());
}

int main() {
    std::string_view hello = "Hello World";
    std::string_view sub = hello.substr(0, 5);
    std::cout << sub << "\n";
    print_me(sub);
}
```

Чуть-чуть [изменим](https://godbolt.org/z/qPoeha4jc) аргументы

```C++
// Теперь эта маленькая программа весело и задорно выведет

// Hello
// Hello Worldnext (а может быть просто упадет с ошибкой сегментации)

// Хотите вы этого или нет.


void print_me(std::string_view s) {
    printf("%s\n", s.data());
}

int main() {
    char next[] = {'n','e','x','t'};
    char hello[] = {'H','e','l','l','o', ' ', 'W','o','r','l','d'};
    std::string_view sub(hello, 5);
    std::cout << sub << "\n";
    print_me(sub);
}
```


Функция не менялась, мы просто передали другие параметры и всё совсем сломалось! А это всего лишь `print`. С какой-то другой функцией может случиться что-то совершенно немыслимое, когда она пойдет за границы диапазона, заданного в `string_view`.

Что же делать?!

Нужно гарантировать NULL-терминированность. А для этого надо скопировать строку... Но ведь `std::string_view` мы же специально использовали в API, чтобы не копировать?!

Увы. Как только вы сталкиваетесь со старыми C API, оборачивая их, вы либо вынуждены писать две имплементации -- с сырым `char*` и c `const std::string&`.  Либо соглашаться на копирование на каком-то из уровней.

### Как бороться

Никак.

NULL-терминированные строки -- унаследованная неэффективность и возможность для ошибок, от которых мы уже, вероятно, никогда не избавимся. В наших силах лишь постараться не продолжать плодить зло:
В новых C-библиотеках стараться проектировать API, использующие пару указатель + длина, а не только лишь указатель на NULL-терминированную последовательность.

От этого наследия страдают программы на всех языках, вынужденные взаимодействовать с C API.
Rust, например, использует отдельные типы `CStr` и `CString` для подобных строк и переход к ним из нормального кода всегда сопровождается мучительными тяжелыми преобразованиями.

Использование NULL-терминатора встречается не только для текстовых строк. Так, например, библиотека [SRILM](http://www.speech.sri.com/projects/srilm/) активно использует 0-терминированные последовательности числовых идентификаторов, создавая этим дополнительные проблемы.
Семейство функций exec в Linux принимают NULL-терминированные последовательности указателей.
EGL использует для инициализации списки атрибутов, оканчивающиеся нулем.
И многие многие другие.

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