C динамическая длина строки

Question

Существуют разные способы создания динамических строк в C (длина которых постоянно меняется). После некоторого поиска в Google основной способ сделать это - использовать realloc () .

Я реализовал это, используя связанные списки с 32-байтовыми кусками для каждого узла.

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

РЕДАКТИРОВАТЬ Причина, по которой я это делаю, заключается в том, что я получаю динамические данные из сокета recv () , и искал гибкий способ их хранения без выделения огромное количество данных, которые не нужны.

Answer 1

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

Использование связанного списка - хорошая идея, но данные не являются непрерывными (например, нельзя передать всю структуру в printf), а индексирование требует больше вычислений (O (N)). Основным преимуществом является то, что добавляемыми строками (с обоих концов) является O (1).

Answer 2

Я думаю, что вы ищете Scatter-Gather I / O , функция, которую вы ищете, будет readv () .

Answer 3

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

Answer 4

Если вы используете realloc (), не добавляйте постоянное количество места в каждый realloc, потому что тогда стоимость создания строки длины n будет равна O (n ^ 2) (realloc, вероятно, выделит новый регион и скопировать туда данные, т.е. его сложность не постоянная, а O (n)). Самый простой способ сделать это - удвоить размер буфера на каждом realloc, тогда амортизированная стоимость все равно будет O (n).