Rearranging array for memory efficiency

Question

This is a question about a passage from this article on component based engine design.

I suggest having every game object exist within a single giant array. This keeps game objects together in memory, and even though deletion of a game object is of O(n) complexity, that O(n) operation traverses an array, and usually will turn out to be unnoticeable. A custom vector or array class can be created that avoids the O(n) operation entirely by taking the element at the end, and placing it into the deleted slot.

I'm trying to understand what kind of operation the author is talking about. If I'm getting the overall point correctly, it's that accessing elements that are closer together in memory is faster, so therefor it's desirable to reorder the array such that there aren't any holes left when a game object is deleted.

If that is what the author means, then how is it possible to implement? This is what I'm imagining:

void Factory::addObject(const std::string name) {
    objects.push_back(new GameObject(name));

void Facrory::removeObject(const std::string name) {
    for(auto itr = objects.begin(); itr != objects.end()) {
        GameObject* obj = *itr;
        if(obj->name == name) {
            delete obj;
            // grab GameObject from end
            GameObject* endObj = objects.back();
            objects.erase(--m_objects.end());
            itr = objects.insert(itr, endObj);
        // else increment itr and continue

But that can't be right because just rearranging the pointers doesn't change how the memory is organized. So the author must be talking about something I don't understand about memory management.

My question is:
Have I misunderstood what the author meant? If not, then please explain how the author is suggesting the rearrangement is supposed to be done.

Answer 1

This is a good question. I was trying to express that instead of holding an array of pointers to game objects, you can hold an array of game objects themselves, as pointed out by API-Beast in the comments of your question.

You can implement this swap operation like this, assuming the array holds structs with simple data (structs with ints, floats, etc., no free, no delete, no malloc, no new, no deep copies):

void Array::Release( index i )
{
    m_array[ i ] = m_array[ --m_size ];
}

Please note that it is important to be able to refer to an object by its index. In your question you are looking up an object by string, which means there's not a clear mapping from string to memory location. If you use an integer index you can understand exactly where in memory (in the array) the object is located. This lets you grow the array by allocating a bigger array, copying the old elements over, and freeing the new array. Old indices into the old array will still work with the new array memory.

This is just how the swap operation works. You'll need to somehow update the index of the moved object, which is where the idea of a handle becomes useful. Implementing handles is another different topic, but will probably be necessary for being able to move objects around in memory without any dangling pointers. The idea of utilizing the cache properly, handles, simple structs and copying the last element is talked about in detail in the next article on cache aware components.