Is std::deque the best option for storing my graphics objects?

Question

I am currently implementing an object buffer, which stores all the objects used in the game at one place. All other components of the game, like the user interface, the level loader, etc, add objects to this buffer and then the objects are accessed by the rendering engine to render them all at once.

I need to store the graphics object in the object buffer contiguously in memory, so that i can take advantage of cpu caching while rendering. I also need to have stable pointers to the objects stored in the buffer as they have to be editable by their pointers by the components that created them, like the user interface must be able to access the graphics it put into the buffer in response to mouse movement with a pointer to that graphic.

These are the reasons i could not use either std::lists, which are not contiguous, or std::vectors, which invalidate all pointers when they reallocate. One data container i found useful was the std::deque, which though doesn't have complete contiguity, does allow some and keeps pointers valid, but what i wanted to ask was is

is there any other data structure out there which is better at what i want?

As far as i understand deques, they are implemented as vectors of arrays of all definite sizes. Is there a data structure that is able to allocate arrays with increasing size, like vector does?

Answer 1

First, your concerns are definitely valid and this is not "premature optimization."

The problem is, std::deque::insert invalidates all iterators and references, so deque is not actually useful for this. What I did to solve this problem is create a wrapper data structure around std::vector (I called it a perma_vector) that stores a vector of std::pair<int, T>. The vector is in increasing order by integer. When you insert something, it pushes it at the end, with an integer one greater than the previous last element. This integer is wrapped in an "perma-ref" object and returned. The upshot of this is that you can pass in the "perma-ref" and look up an object in logarithmic time (via std::lower_bound). They are never invalidated unless the object itself is deleted.

Some concerns with this: You will have to put some thought into what interface you expose to maintain the data structure's invariants. You will probably have an interface similar to, but slightly smaller than, a std::vector. You will also have to write your own iterator class, (although you might be able to get around that with a two vectors instead of a vector of pairs.) Also, it might behoove you to make it easy to switch the underlying data structure. You might find that having a deque is better if you're adding or removing a lot of stuff.

PS. My code isn't that great and I'm not going to clean it up and post it unless this gets a ton of votes.

Answer 2

I am assuming you are using something like OpenGL for your graphics (Correct me if I am wrong about this), so a typical, minimal data structure for rendering a game object would be:

struct RenderData
{
    //Ctor
    RenderData(GameObject* p)
        :owner(p), 
         meshHandle(0), 
         numVerts(0) 
    {
        meshHandle = owner->getMesh();
        numVerts = owner->getVerts();
        transform = owner->getTransform();
        colour = owner->getColour();
    }
    // Member data
    GameObject* owner;
    unsigned int meshHandle; // This is the vertex array object (VAO) handle
    unsigned int numVerts; // Number of vertices in the mesh
    mat4 transform; // for homogeneous 3D transformations
    vec4 colour; //assumes RGBA
};

So when a new object is added to a collection of renderables, you emplace it, like so:

void addRenderable(GameObject* o)
{
    renderables.emplace_back(o);
}

Then, when you wish to render (render code ommitted):

void renderScene()
{
    for (size_t i = 0; i < renderables.size(); ++i)
    {
        renderObject(renderables[i]); //renderObject takes a const RenderData& as argument, 
        //or replace with rendering code here.
    }
}

This way, the memory in the vector is contiguous, and so the CPU can decide on the most efficient fetches from memory, reducing cache misses to a minimum.

If you need to remove a gameObject (and order is not important), then you need to ensure that the memory remains contiguous:

void remove(GameObject* p)
{
    // linear search and remove
    for (size_t i = 0; i < renderables.size(); ++i)
    {
        if (renderables[i].owner->getID()==p->getID())
        {
            renderables[i] = std::move(renderables.back());
            renderables.resize(renderables.size()-1);
            return;
        }
    }
}

Of course, this all assumes you wish to have a collection of renderables, that is persistent between frames, but you could still use this technique on a frame by frame basis, and populate the vector based on some rule/logic.

Because the struct I used in my example effectively proxy's for the actual game object, it is throwaway, so can be safely destroyed without affecting the actual gameobject, or causing memory leaks.