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

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

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

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

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

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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