велосипедостроитель?

Для char** есть getline

> велосипедостроитель? Да, он самый.

> Для char** есть getline
Я про это знаю. Меня сейчас интересует эффективность реализации, а не методы работы. getline() к тому же, вроде бы, POSIX'ный, а я хочу переносимость (сам напишу :)).

> getline() к тому же, вроде бы, POSIX'ный
А POSIX перестал быть переносимым?

Очевидно, от проблемы зависит.

(это я про эффективность)

Производительность

> Есть два варианта, не знаю какой выбрать: или через связанные списки, или каждый раз делать realloc() для char** arr.

> Что быстрее в плане производительности?

Зависить от основных действий с массивом. На произвольном доступе списки однозначно проигрывают, зато для вставки/удаления элементов списки эффективнее.

Плюс, списки требуют больше памяти.

Ну можно реализовать аналог std::vector на Си. То есть realloc делать не на size+1, а 2 * size. Тогда проблем со вставкой не будет, потом не будет проблем с функциями, которые на вход хотят массив.

>Ну можно реализовать аналог std::vector на Си. 
>То есть realloc делать не на size+1, а 2 * size.

А еще можно 

size -> 2*size когда realsize=size 
size -> size/2 когда realsize*4 < size

Тогда при амартизационном анализe push_back, pop будут иметь 
учетную стоимость O(1) 

а что такое - "амартизационный анализ"?

>а что такое - "амартизационный анализ"

Вот предположим у нас есть структура данных, или более конкретно динамический массив с поддержкой операций push_back, pop_back. Если size=real_size, то для push_back требуется O(size), в других случаях O(1). Спрашивается а сколько потребуется времени чтобы сделать n операций.

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

cost(push_back)< с + F(новое состояние)-F(старое состояние)

cost(pop_back)< с + F(новое состояние)-F(старое состояние)

то если мы делаем n операция o_1, o_2, o_3, ..., то сумарная стоимось будет

сумма по i cost(o_i) < n*c+сумма по i F(после o_i)-F(до o_i)=n*c

Так как

сумма по i F(после o_i)-F(до o_i) = F(в начале) - F(в конце) = 0;

В данном случае в качестве F нужно взять k*abs(2*real_size-size)

Заметим кстати, что аллокированной памяти будет O(real_size).

Все подробности к Кормен, Лейзер, Ривест "Алгоритмы: построение и анализ". Этот пример от туда.

Предлагаю автору определиться, что ему нужно - динамический массив (вектор) или список. Под этими словами обычно понимают вполне конкретные структуры данных. В случае вектора элементы располагаются в памяти последовательно, благодаря чему эффективно выполняется операция индексирования, но дорого операции вставки элемента в середину и удаления из середины. Кроме того, операция добавления элемента может приводить к копированию всего массива.
Со списком ситуация обратная - операция индексирования достаточно дорогая, зато операции вставки / удаления дешевы.

Реализации на C можно посмотреть в GLib (http://www.gtk.org).

Да, кстати, если не пугают накладные расходы по памяти, то можно вполне соорудить более сложную структуру, типа красно-черного дерева или хеш-таблицы, хранящей узлы связного списка. Тогда и вставка/удаление/произвольный доступ будут логарифмические, последовательный доступ - линейный.

syomin :

> В случае вектора элементы располагаются в памяти последовательно, благодаря чему эффективно выполняется операция индексирования, но дорого операции вставки элемента в середину и удаления из середины. ... Со списком ситуация обратная - операция индексирования достаточно дорогая, зато операции вставки / удаления дешевы.

Это, конечно, классика. Но бывают и особые ситуации, зависящие от используемого алгоритма распределения памяти. Может быть и так, что realloc() от malloc() по накладным расходам не отличаются, а может быть и так, что индексирование списка сводится к операции сложения.

ИМХО просто глупо обсуждать поставленный вопрос в том том виде, как это было сделано. Очевидно, автор топика плохо отдает себе отчет в том, что он хочет, иначе хотя бы намекнул на проблему...

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