Для перераспределения строки при её увеличении для определения размера вновь выделенного блока вызывается следующее:

            // Grow exponentially, until we hit 1K.
            int nNewLength = pOldData->nAllocLength;
            if( nNewLength > 1024 )
            {
                nNewLength += 1024;
            }
            else
            {
                nNewLength *= 2;
            }

Выгоден ли такой подход? Если да, то когда и почему std::vector сделан не так?

Здравствуйте, Alexander G, Вы писали:

AG>Выгоден ли такой подход? Если да, то когда и почему std::vector сделан не так?

Лучшего варианта нет. Всё зависит от использования и требований по памяти/скорости.
Я думаю, что разработчики CString и std::vector<> просто ориентировались на различные паттерны использования.

Это неоднократно обсуждалось. Например здесь:
http://www.rsdn.ru/forum/cpp/1806588.aspx

Автор: Дядюшка Че
Дата: 27.03.06

А вот тут предлагается растить размер как 1.32*X
http://rsdn.ru/forum/cpp/2964501.1.aspx

Автор: remark
Дата: 26.05.08

Alexander G wrote:

> Выгоден ли такой подход? Если да, то когда и почему std::vector сделан
> не так?

Так это зависит от конкретных требований конкретного приложения.
Если ты добавляешь в строку по 1-ому символу -- это одно. Если
добавляешь по 8 килобайт -- это другое.

Здравствуйте, MasterZiv, Вы писали:

>> Выгоден ли такой подход? Если да, то когда и почему std::vector сделан
>> не так?

MZ>Так это зависит от конкретных требований конкретного приложения.
MZ>Если ты добавляешь в строку по 1-ому символу -- это одно. Если
MZ>добавляешь по 8 килобайт -- это другое.

Допустим, у меня документ, состоящий из объектов, содержащих CString, и надо передать выделенную часть в SetClipboardData. И, допустим, копируем в один проход, сразу в CString. Так, размер документа заранее неизвестен и на больших документах число копирований в памяти будет расти линейно от размера документа, т.е. количество скопированных байт — квадратично, даже если добавляемые CString по 8 килобайт.

Т.е. при произвольно больших строках рост по килобайту — невыгоден. Когда выгоден — неясно. Я не вижу большого выигрыша от того, что строка в 1200 символов займёт 3 КБ, а не 4, с учётом потери времени на чуть более длинных строках.

Здравствуйте, Alexander G, Вы писали:

MZ>>Так это зависит от конкретных требований конкретного приложения.
MZ>>Если ты добавляешь в строку по 1-ому символу -- это одно. Если
MZ>>добавляешь по 8 килобайт -- это другое.

AG>Допустим, у меня документ, состоящий из объектов, содержащих CString, и надо передать выделенную часть в SetClipboardData. И, допустим, копируем в один проход, сразу в CString. Так, размер документа заранее неизвестен и на больших документах число копирований в памяти будет расти линейно от размера документа, т.е. количество скопированных байт — квадратично, даже если добавляемые CString по 8 килобайт.

Теперь ты знаешь, что CString не предназначен для такого использования

AG>Т.е. при произвольно больших строках рост по килобайту — невыгоден. Когда выгоден — неясно. Я не вижу большого выигрыша от того, что строка в 1200 символов займёт 3 КБ, а не 4, с учётом потери времени на чуть более длинных строках.

Ты тут просто меняешь шило на мыло.
При экспоненциальном росте: количество копирований O(logN), издержки по памяти O(N).
При линейном росте: количество копирований O(N), издержки по памяти O(1).
Я думаю, представить сценарий, когда издержки по памяти O(1) вместо O(N), достаточно просто. CString даёт гарантию, что будет выброшено не более 1кб памяти (!), std::vector же допускает выбрасывание на ветер произвольного кол-ва памяти (мегабайт, 100 мегабайт, гигабайт — сколько угодно... ну, естественно, в зависимости от размера данных). Поэтому говорить о лучшей стратегии тут врядли уместно.

AG>Выгоден ли такой подход? Если да, то когда и почему std::vector сделан не так?
У std::vector по стандарту push_back должен исполнятся за константное амортизированное время
На CString никаких стандартов нету
Кроме того добавление элементов в CString операция обычно более редкая чем добавление в вектор.

Здравствуйте, remark, Вы писали:

R>Ты тут просто меняешь шило на мыло.
R>При экспоненциальном росте: количество копирований O(logN), издержки по памяти O(N).
R>При линейном росте: количество копирований O(N), издержки по памяти O(1).

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

Издержки по памяти O(N) против O(1) будут означать, что приложению может требоваться в К раз больше памяти, К меньше двух. Это не проблема по сравнению с возможным оверхедом на лишние копирования.

Здравствуйте, Alexander G, Вы писали:

AG>Я не совсем понимаю, почему в общем случае (CString же для повсеместного хранения строк) приоритет на экономию памяти. При малых объёмах на результат будет влиять гранулярность кучи, оверхед на блок кучи, фрагментация кучи, в результате выигрыш от такой экономии сомнителен. При больших объёмах речь уже будет идти не о выделенной зря памяти, а о выделенном зря диапазоне в адресном пространстве, физическая память которому не будет сопоставлена, т.к. к нему не будет обращений.

AG>Издержки по памяти O(N) против O(1) будут означать, что приложению может требоваться в К раз больше памяти, К меньше двух. Это не проблема по сравнению с возможным оверхедом на лишние копирования.

Откуда такая уверенность?

Я например сейчас работаю с клиентским приложением, в целом все операции достаточно лёгкие и скорость не является проблемой; а вот память как раз является — программа ела в несколько раз больше памяти, чем хотелось бы. В ходе оптимизации, в частности, было сделано, что бы строки выделяли *ровно* столько памяти, сколько нужно + убрана small string optimization (т.е. убран небольшой статический буфер из строк). В результате скорость как была удовлетворительной, так и осталась, а вот память существенно сократилась.
Поэтому для меня лично, это утверждение не столь очевидно.

К тому же сейчас оптимизируя память — оптимизируешь и производительность... но это уже отдельная история.

Alexander G wrote:

> Я не совсем понимаю, почему в общем случае (CString же для повсеместного
> хранения строк) приоритет на экономию памяти. При малых объёмах на

Потому что для реальной оптимизации выделения ты должен вызывать всё
равно GetBuffer/Release. Так к чему весь этот разговор вообще ?