C-string как связанный список?

В c-строках нам нужно выделить разумный размер памяти. Чтобы избежать перераспределения в строковых операциях, мы можем использовать что-то вроде Stringbuilder в C# или Java или - в C - просто выделяем больше памяти для строки. Но все же это может быть проблемой, если мы заранее не знаем требования к памяти. У нас есть какая-то реализация, как связанный список? Я имею в виду, чтобы выделить список блоков памяти и методы c_str(), который создает с-строкой из ее узловC-string как связанный список?

liststring a(4); // requested block size 
a.append("hello "); 
a.append("world"); 
// should create three nodes, 4 bytes allocated for each 
// "hell" -> "o wo" -> "rld" 
a.c_str(); // "hello world";

Или мы используем другой подход, если мы хотим избежать перераспределений? Пожалуйста, объясните, если это плохая идея.

источник

2012-02-23 Jan Turoň

Когда вы вызываете c_str(), вам все равно нужно поместить строку в смежный буфер памяти, поэтому обычно считается, что с этой точки зрения это хорошая идея. Использование связанного списка блоков фиксированного размера также означает, что построение длинной строки будет тратить O (n) на распределение, тогда как обычная стратегия распределения по экспоненциальному увеличению для строк тратит O (log (n)) за счет потери большего объема памяти. –

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

Существует алгоритм, гарантирующий не использовать память более чем в четыре раза длины строки, и каждое перераспределение занимает в среднем значение «O (1)». Если текущий размер буфера равен «n», а длина строки не заполнена буфером, необходимо перераспределить буфер размером «2 * n». Если он стал меньше, чем 'n/4', то буфер размером n/2 должен быть перераспределен. – citxx

См. Статью по адресу Ropes для структуры данных, которая хранит строки в виде деревьев. Это похоже на вашу идею.

источник

2012-02-23 19:52:42 AShelly

Отлично, это именно то, что я искал! –

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

источник

2012-02-23 19:54:00 citxx

Я предполагаю, что вы имели в виду C++, а не C.

Стандартный класс для работы со строками в C++ является станд :: строка.

Строковые классы в Java или . NET неизменяемы. std :: string с другой стороны изменен, поэтому он ведет себя точно так же, как StringBuilder.

источник

2012-02-23 19:54:26 ZunTzu

Нет, я имею в виду C, но C++ тоже будет хорошо. std :: string не предоставляет функциональность, которую я хочу. Или это? –

Наверное, нет, поскольку все реализации, которые я знаю, смежны в памяти. См. Ответ AShelly: это то, что вы ищете. – ZunTzu

C-string как связанный список?

ответ

Смежные вопросы