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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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