std :: string и его автоматическое изменение размера памяти
Я довольно новичок в C ++, но я знаю, что вы не можете просто использовать память как бы ни был полезен класс std :: string. Например:
std::string f = "asdf";
f += "fdsa";
Как класс строки обрабатывает все больше и меньше? Я предполагаю, что он выделяет объем памяти по умолчанию и, если ему нужно больше, он новый больший блок памяти и копирует себя в это. Но разве не было бы неэффективно копировать всю строку каждый раз, когда ей нужно было изменить размер? Я не могу придумать другой способ, которым это могло бы быть сделано (но очевидно кто-то сделал).
И в этом отношении, как все классы stdlib, такие как вектор, очередь, стек и т. Д., Так прозрачно обрабатывают рост и сжатие?
3 ответа
Обычно существует алгоритм удвоения. Другими словами, когда он заполняет текущий буфер, он выделяет новый буфер, который в два раза больше, а затем копирует текущие данные. Это приводит к меньшему количеству операций выделения/копирования, чем альтернатива увеличения на один блок распределения.
Ваш анализ верен — неэффективно копировать строку каждый раз, когда нужно изменить ее размер. Вот почему общие советы не рекомендуют использовать шаблон. Используйте функцию reserve строки, чтобы попросить ее выделить достаточно памяти для того, что вы намереваетесь хранить в ней. Затем дальнейшие операции заполнят эту память. (Но если ваша подсказка окажется слишком маленькой, строка все равно будет увеличиваться автоматически.)
Контейнеры также обычно пытаются смягчить последствия частого перераспределения, выделяя больше памяти, чем им нужно. Обычный алгоритм заключается в том, что когда строка обнаруживает, что в ней недостаточно места, она удваивает размер своего буфера вместо того, чтобы просто выделять минимум, необходимый для хранения нового значения. Если строка увеличивается по одному символу за раз, этот алгоритм удвоения уменьшает временную сложность до амортизированного линейного времени (вместо квадратичного времени). Это также снижает подверженность программы фрагментации памяти.
Хотя я не знаю точной реализации std::string, большинство структур данных, которые должны обрабатывать динамический рост памяти, делают это, делая именно то, что вы говорите - выделять объем памяти по умолчанию, и если нужно больше, создайте больший блок и скопируйте себя.
Очевидную проблему неэффективности можно обойти, выделив больше памяти, чем нужно. Отношение используемой памяти к общей памяти вектора/строки/списка/и т. д. часто называют коэффициентом загрузки (также используется для хеш-таблиц в немного другом значении). Обычно это соотношение 1:2, то есть вы выделяете вдвое больше памяти, чем вам нужно. Когда у вас заканчивается место, вы назначаете новый объем памяти, вдвое превышающий текущий объем, и используете его. Это означает, что со временем, если вы продолжаете добавлять что-то в вектор/строку/и т. д., вам нужно копировать элемент все меньше и меньше (поскольку создание памяти является экспоненциальным, а вставка новых элементов, конечно, линейна), поэтому время, затрачиваемое на этот метод обработки памяти, не так велико, как вы думаете. В соответствии с принципами амортизированного анализа вы можете видеть, что вставка m элементов в вектор/строку/список с использованием этого метода является только Big-Theta m, а не m. 2.