Уплотнение на месте

Очевидный недостаток алгоритма Бейкера заключается в напрасной потере половины памяти. Существует и другой, мене очевидный недостаток - при каждом проходе все объекты копируются из одного места памяти в другое. Такое копирование может отрицательно повлиять на быстродействие программы. Обе проблемы решаются в другом алгоритме, который называется уплотнением на месте (compaction in place). Вместо двух половин существует единое пространство, а в процессе уплотнения все объекты смещаются вниз. На следующей диаграмме показано состояние памяти до и после уплотнения.

Копирование объектов должно происходить в правильном порядке, снизу вверх, в противном случае объекты будут накладываться друг на друга. Этого можно добиться двумя способами: отсортировать ведущие указатели перед началом перебора или изначально хранить их в отсортированном порядке.

Хранить ведущие указатели в двусвязном списке, отсортированном по адресу указываемого объекта, довольно просто - при условии, что вы готовы потратить лишнюю пару слов для указателей на следующий и предыдущий элемент. Шаблон ведущего указателя и  дескрипторы аналогичны тем, которыми мы пользовались до настоящего момента. Базовый класс VoidPtr был усовершенствован для хранения экземпляров в связанном списке.