По последним данным, на рынке продается по крайней мере 2 768 942 книги о С++, не говоря уже о всевозможных курсах, обучающих программах, журналах и семинарах с коктейлями. И все же в этом изобилии наблюдается удручающее однообразие.
Один из алгоритмов уплотнения жертвует неимоверным количеством (а точнее, половиной) памяти в интересах скорости. Процесс уплотнения понемногу вплетается в обычную работу программы. Этот алгоритм называется алгоритмом Бейкера (Baker's Algorithm).
Пул памяти делится на две половины, A и B. В любой момент времени одна из этих половин является активной (то есть в ней создаются новые объекты). Память выделяется снизу вверх, а в момент удаления объекта не делается никаких попыток вернуть занимаемую им память. Время от времени все активные объекты копируются из одной половины памяти в другую. В процессе копирования автоматически происходит уплотнение нижней части новой активной половины. Активным называется объект, для которого в стане ведущих указателей найдется ссылающийся на него ведущий указатель (в нашем случае VoidPtr).
Просматривать полку книг о С++ в книжном магазине ничуть не интереснее, чем литературу по бухгалтерии. В сущности, все книги пересказывают одно и то же и отличаются разве что по весу и количеству цветов в диаграммах и таблицах.
