Как справиться с удалением объекта при непрерывном размещении?

На самом деле это довольно просто, не используйте прямые ссылки. Используйте уровень косвенности, такой как идентификаторы. Например:

Допустим, у вас есть FooManager, который управляет всеми вашими «объектами» Foo (не объектами в смысле ООП, набором массивов для каждого свойства Foo). Насколько я понимаю, сейчас вы просто возвращаете индекс. Допустим, Foo #42 — это Foo, данные которого расположены по индексу 42 всех массивов. Теперь вы хотите удалить Foo #42, который пробивает дыру в вашем массиве. Вы можете переместить все остальные элементы массива, но тогда Foo #43 больше не указывает на фактический индекс 43.

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

В следующий раз, когда Foo нужно обновить из другого фрагмента кода, используется идентификатор. Таким образом, функция setBar FooManager вызывается с идентификатором 1337 и новым значением Bar в качестве аргументов. FooManager ищет 1337 в своей таблице идентификаторов, обнаруживает, что он все еще находится в индексе 42, и обновляет индекс 42 массива Bar новым значением Bar.

Теперь вот где эта система получает свое значение, давайте удалим Foo 1337. removeFoo FooManager вызывается с идентификатором 1337 в качестве аргумента. Он ищет 1337, он находится под индексом 42. Однако за это время было добавлено 10 новых Foos. Итак, теперь мы можем просто заменить значения с индексом 42 на значения с 52, эффективно переместив 52 на 42. Это вызвало бы большую проблему в старой системе, но теперь нам нужно только обновить таблицу индексов. Итак, мы ищем, какой ID указывает на 52 (скажем, 1401) и обновляем его до 42. В следующий раз, когда кто-то попытается обновить Foo с ID 1401, он ищет его в таблице индексов и обнаруживает, что он расположен по индексу 42.

Таким образом, мы храним данные в непрерывной памяти, удаление требует очень небольшого количества операций копирования данных (одна копия для каждого свойства Foo), а код «вне» FooManager даже не осознает, что что-то произошло. Это даже решает проблемы мертвой ссылки. Предположим, что какой-то код все еще имеет удаленный идентификатор 1337 (висячая ссылка, это плохо!), когда он пытается получить доступ/изменить его, FooManager просматривает его, видит, что 1337 не существует (больше) и может генерировать хорошее чистое предупреждение /error и стек вызовов, что позволяет вам напрямую определить, в каком коде все еще есть висячая ссылка!

Есть только один недостаток, это дополнительный поиск в таблице идентификаторов. Теперь хэш-таблица может быть очень быстрой, но это по-прежнему дополнительная операция при каждом изменении объекта Foo. Однако в большинстве случаев доступ извне менеджера случается гораздо реже, чем доступ внутри менеджера. Когда у вас есть BulletManager, он будет обновлять каждую пулю каждый кадр, но доступ к Bullet для изменения/запроса чего-либо и вызовы для создания/удаления пуль происходят с меньшей вероятностью. Однако, если это наоборот, вам, вероятно, следует обновить свои структуры данных, чтобы оптимизировать их для этой ситуации. Опять же, в такой ситуации уже не имеет большого значения, где находятся данные в памяти, поэтому вы можете жить либо с «дырами» в своих массивах, либо даже с использованием совершенно разных макетов данных.

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

РЕДАКТИРОВАТЬ: если вы поддерживаете внешние указатели в массиве, ими можно управлять с помощью интеллектуальных указателей, базовые адреса которых обновляются (shared_ptr::reset) при перемещении элемента массива. вы получите 2 параллельных массива одинаковой длины:

typedef std::vector<thing> thingVec;
thingVec things;

// smart pointers for each object
std::vector<boost::shared_ptr<thingVec::iterator>> references;

в вашей функции createThing вы бы вернули shared_ptr с пользовательским средством удаления (которое автоматически обновит массив после того, как все ссылки будут погашены):

http://www.boost.org/doc/libs/1_51_0/libs/smart_ptr/sp_techniques.html#static

интеллектуальные указатели могут указывать на структуры с несколькими полями, которые в конечном итоге хранятся в разных массивах, если пользовательское средство удаления знает, какие массивы сжимать при удалении элемента.