std::string и его автоматическое изменение размера памяти

Я довольно новичок в C++, но я знаю, что вы не можете просто использовать память волей-неволей, как это позволяет делать класс std::string. Например:

std::string f = "asdf";
f += "fdsa";

Как строковый класс справляется с увеличением и уменьшением размера? Я предполагаю, что он выделяет объем памяти по умолчанию, и если ему нужно больше, он news выделяет больший блок памяти и копирует себя в него. Но не было бы довольно неэффективно копировать всю строку каждый раз, когда нужно изменить ее размер? Я действительно не могу придумать другой способ, которым это можно было бы сделать (но, очевидно, кто-то это сделал).

И в этом отношении, как все классы stdlib, такие как вектор, очередь, стек и т. д., так прозрачно обрабатывают рост и сжатие?


c++ string memory std dynamic-resizing
person Thomas T.    schedule 24.08.2010    source источник

Ответы (3)


arrow_upward
8
arrow_downward

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

person Steven Sudit    schedule 24.08.2010
comment
Значит, он должен копировать себя при каждом выделении памяти? - person Thomas T.; 24.08.2010
comment
Абсолютно. Избежать этого невозможно, хотя вы, безусловно, можете минимизировать это, увеличив начальную емкость. - person Steven Sudit; 24.08.2010
comment
Хорошо, большое спасибо. Мой класс не так устарел, как я думал :) - person Thomas T.; 24.08.2010
comment
@Thomas T: Да, но это не является серьезной проблемой. C#, например, копирует строку после каждой операции над строкой, а не только тогда, когда требуется больше памяти; тем не менее C# по-прежнему остается достаточно эффективным языком. - person Billy ONeal; 24.08.2010
comment
@Billy, в головы программистов на C # также вбито, что они должны часто использовать StringBuilder вместо String. - person Rob Kennedy; 24.08.2010
comment
Это не должно быть удвоение, любой другой фактор также в порядке. Например, Microsoft предпочитает 1.5, по крайней мере, в своей реализации std::vector. - person fredoverflow; 24.08.2010
comment
@FredOverflow - не каждый другой фактор подходит. 1.0000001, например, вряд ли будет эффективным :p. Но да, такие факторы, как 1,5, также обеспечивают приемлемую эффективность. Это сводится к попытке уменьшить накладные расходы памяти, снижая коэффициент загрузки, а также пытаясь избежать слишком большого количества копий, поскольку они занимают время. Это уравновешивание, как и многие вычисления. - person Stephen; 24.08.2010
comment
@ Роб Кеннеди: Это правда. Просто говорю, что неразумно копировать строку в результате увеличения ее распределения. - person Billy ONeal; 24.08.2010
comment
@Billy: может быть. Например, во времена ASP/VB объединение BSTR было огромным источником медлительности именно потому, что каждый раз требовалось перераспределение и копирование. StringBuilder в .NET исправляет это, но только если вы умеете его использовать. Как оказалось, StringBuilder тоже использует алгоритм удвоения. - person Steven Sudit; 24.08.2010
comment
@Stephen: Вы меня неправильно поняли. Обратите внимание на слова увеличение выделения — я не говорю о неизменяемых строках. О, и StringBuilder не использует алгоритм удвоения; внутри он похож на веревку. (По крайней мере, согласно исследованию исходного кода Reflector) - person Billy ONeal; 24.08.2010
comment
@Билли: Это Стивен. Не то чтобы я был особенно чувствителен к этому, но если вы напишете неправильно, SO не уведомит меня. В любом случае то, что вы сказали о StringBuilder, является новым для .NET 4.0. В версии 3.5 это просто строка, хотя она использует внутренние методы, чтобы сделать ее действительно изменяемой. - person Steven Sudit; 24.08.2010
comment
@Steven: извините за проблему с переименованием. :П - person Billy ONeal; 24.08.2010
comment
На самом деле некоторое время назад на c++.comp.lang.moderated обсуждался фактор роста. Измерения показали, что использование коэффициента меньше 2 было лучше, потому что распределители обычно заканчивали тем, что выделяли мощность 2-байтового блока, и, следовательно, было лучше расти медленнее, чем это. Я помню, что Александреску был замешан, думаю, желающие могут поискать. - person Matthieu M.; 24.08.2010
comment
@Matt: То, что я видел, - это попытки сопоставить распределение с детализацией блоков распределения, чтобы количество символов плюс любые накладные расходы были чуть ниже предела. - person Steven Sudit; 24.08.2010

arrow_upward
8
arrow_downward

Ваш анализ верен — неэффективно копировать строку каждый раз, когда нужно изменить ее размер. Вот почему общие советы не рекомендуют использовать шаблон. Используйте функцию строки reserve, чтобы попросить ее выделить достаточно памяти для того, что вы намерены хранить в нем. Затем дальнейшие операции заполнят эту память. (Но если ваша подсказка окажется слишком маленькой, строка все равно будет увеличиваться автоматически.)

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

person Rob Kennedy    schedule 24.08.2010

arrow_upward
3
arrow_downward

Хотя я не знаю точной реализации std::string, большинство структур данных, которые должны обрабатывать динамический рост памяти, делают это, делая именно то, что вы говорите, — выделяйте объем памяти по умолчанию, и если требуется больше, создайте больший блок. и скопируйте себя.

Чтобы обойти очевидную проблему неэффективности, нужно выделить больше памяти, чем вам нужно. Отношение используемой памяти к общему объему памяти вектора/строки/списка/и т. д. часто называют коэффициентом загрузки (также используется для хеш-таблиц в несколько ином значении). Обычно это соотношение 1:2, то есть вы выделяете вдвое больше памяти, чем вам нужно. Когда у вас заканчивается место, вы назначаете новый объем памяти, вдвое превышающий текущий объем, и используете его. Это означает, что со временем, если вы продолжаете добавлять что-то в вектор/строку/и т. д., вам нужно копировать элемент все меньше и меньше (поскольку создание памяти является экспоненциальным, а вставка новых элементов, конечно, линейна), поэтому время, затрачиваемое на этот метод обработки памяти, не так велико, как вы думаете. В соответствии с принципами амортизированного анализа вы можете видеть, что вставка m элементов в вектор/строку /list, использующий этот метод, является только Big-Theta m, а не m2.

person Stephen    schedule 24.08.2010
comment
@Steven - В таком случае я разрываюсь. Выше есть люди, утверждающие, что C# копирует строку после каждого движения, и обычно это не считается медленным... Но мой теоретический ум, конечно, сходит с ума! п ^ 2! п ^ 2! Аргх!... XD. Я удалю записку, я думаю. - person Stephen; 24.08.2010
comment
C# string (или, скорее, .NET System.String) не напрямую сравним с std::string. В .NET 3.5 ближе всего была StringBuilder, представляющая собой изменяемый набор символов, который позволял модифицировать непрерывный буфер на месте. Это также позволяло создавать неизменяемые снимки с помощью ToString(). В .NET 4.0 есть класс с таким же именем и общими возможностями, но его реализация сегментирована, поэтому он имеет меньше общего с std::string. Ключевым моментом является то, что, несмотря на это, простое добавление к string не считается приемлемым. - person Steven Sudit; 24.08.2010