Решая различные задачи по программированию, нередко сталкиваешься с необходимостью ввода произвольной строки. Хорошо, если в задании указывается ограничение на максимальное количество символов, а если нет? Что делать, если нужно получить динамическую строку неопределённого заранее размера?
Иногда задачи позволяют самостоятельно предугадать примерное число символов, которых должно будет быть достаточно по крайней мере для сдачи программы приниающему. В этом случае используя обычным массивов с огромным числом элементов, например, из тысячи или из миллиона элементов. Вообще говоря, если это символы, то не так уж сильно это и страшно. В наше время компьютеры имеют огромные запасы памяти, так что миллион char'ов будет ему по зубам. Но что делать, если это будут не символы, а какие-нибудь более крупные объекты — целые структуры данных, содержащие более 100 байт вместо одного?
На помощь приходит динамическая память. Это такая область памяти, данные в которой резервируются не на этапе компиляции, а на этапе выполнения программы, причём сколько программист попросит, столько она и выдаст (если место позволяет, в нашем неидальном мире всё имеет предел).
Алгоритм получения строки произвольной длины
Алгоритм эффективного получения динамической строки заключается в следующем: сначала резервируется место под один символ (в случае пустой строки там окажется символ конца строки — '\0'), после чего считываются символы до определённого флага. Чаще всего это символ переноса строки — '\n' или конец файла EOF. Считанный символ помещается в строку на место с индексом len, который удачно является и текущей длиной нашей строки, и значение индекса увеличивается на единицу.
Если значение длины (текущего индекса) стало равно максимальному количеству символов строки (ёмкости), то в случае языка C при помощи функции realloc(char*, size_t) алгоритм получает новый участок памяти с сохранением всех элементов в строке, но с размером, увеличенным в два раза, после чего считывание продолжается.
При использовании же языка C++ необходимо вручную перераспределить память, создав для этого дополнительную строку удвоенного размера и скопировав в неё все данные из основной строки, удалить старый контейнер и подменить указатель.
Таким образом, размер контейнера (ёмкость, а не длина строки) будет меняться при перераспределении следующим образом: 1 - 2 - 4 - 8 - 16 - 32 - 64...
Почему нужно увеличивать именно вдвое? Нельзя ли увеличивать ёмкость строки на 1?
Можно, однако тогда при каждом добавлении символа в строку система будет тратить время на копировании всех введённых символов, что сведёт сложность добавления O(1) к O(n), а сложность всего алгоритма окажется уже не O(n), а O(n2). На 2-3 символах разницы "на глаз" не ощутить, однако на очень длинных строках увеличившееся время считывания будет гораздо заметнее.
Почему увеличение размера контейнера в два раза превращает сложность алгоритма в константу?
Потому что теперь для добавления элемента в новую позицию достаточно просто обратиться к нему по индексу, без всяких копирований и перераспределений, а процедура расширения динамической памяти будет выполняться тем реже, чем длиннее строка.
Сравните сами: для строки из 1000 элементов константный алгоритм сделает всего 9 перераспределений, в то время как линейное увеличение размера потребует 1000 перераспределений, что вряд ли можно назвать хорошей оценкой.
Реализация программы на С
#include <stdio.h>
#include <stdlib.h>
// посимвольное получение динамической строки с пробелами c получением её реальной длины
char *get_string(int *len) {
*len = 0; // изначально строка пуста
int capacity = 1; // ёмкость контейнера динамической строки (1, так как точно будет '\0')
char *s = (char*) malloc(sizeof(char)); // динамическая пустая строка
char c = getchar(); // символ для чтения данных
// читаем символы, пока не получим символ переноса строки (\n)
while (c != '\n') {
s[(*len)++] = c; // заносим в строку новый символ
// если реальный размер больше размера контейнера, то увеличим его размер
if (*len >= capacity) {
capacity *= 2; // увеличиваем ёмкость строки в два раза
s = (char*) realloc(s, capacity * sizeof(char)); // создаём новую строку с увеличенной ёмкостью
}
c = getchar(); // считываем следующий символ
}
s[*len] = '\0'; // завершаем строку символом конца строки
return s; // возвращаем указатель на считанную строку
}
int main() {
int len; // длина строки
char *s = get_string(&len); // считываем динамическую строку
printf("You've wrote: '%s', symbols: %d\n", s, len); // выводим строку и её длину
free(s); // освобождаем динамическую память
return 0;
}
Демонстрация работы программы считывания строки произвольной длины
Вот таким несложным способом можно получать строки, длина которых заранее не определна. Всем приятного программирования и оптимальных алгоритмов!
