game emtities container

[fewdiefie]

I need help implementing an efficient container class to hold my game entities, I did create a double linked list but when compared to the stl vector class, it was 4 times slower,

template <class T>
class LinkedList
{
public:
	struct Element
	{
		Element *next;
		Element *prev;
		T *data;
		
		Element(T *data)
		    :data{ data },
		    next{ nullptr },
		    prev{ nullptr }
		{
		}
		
		Element()
		    :data{ nullptr },
		    next{ nullptr },
		    prev{ nullptr }
		{
		}
		
		~Element()
		{
			if (prev)
			    prev->next = next;
			if (next)
			    next->prev = prev;
			
			if (data)
			    delete data;
		}
	};
	
	LinkedList()
	    :first{ nullptr },
	    last{ nullptr },
	    size{ 0 }
	{
	}
	
	~LinkedList()
	{
		Clear();
	}
	
	void Clear()
	{
		Element *e = first;
		while (e)
		{
			Element *temp = e;
			e = e->next;
			delete temp;
		}
		first = nullptr;
		last = nullptr;
		size = 0;
	}
	
	void Add(T *data)
	{
            Element *e = new Element{ data };

            if (first) {
                first = e;
                last = first;
            }
            else {
	        last->next = e;
	        e->prev = last;
                last = e;
            }
		
            size++;
	}
	
private:
	Element *first;
	Element *last;
	int size;
};

// LinkedList<int> list;
// list.Add(new int(4)); 

I need something faster than this and faster than std::vector

[helios]

What operations in particular are you trying to optimize?

[thmm]

You can try boost vector:
https://stackoverflow.com/questions/14128012/is-boostcontainervector-faster-than-stdvector-why

Can you show us some of your code.
There are many inefficient ways to use std::vector. Maybe you use some?

Have a look at the books of Scott Meyers on Amazon. He wrote some books on Effective C++

[fewdiefie]

I have a set of entities, each entity has a textured model , for optimization's sake, i have created an std::unordered_map<TexturedModel, vector<Entity>> to hold different entities using the same texture, and each frame I add all the entities to that unordered_map, render the entities an then clear the um

std::unordered_map<TexturedModel, vector<Entity>> ents;

void AddEntity(const Entity &entity)
{
    std::unordered_map<TexturedModel, vector<Entity>>::iterator it;

    it = ents.find(entity.TexturedModel);
    if (it != ents.begin())
    {
        // this entity's textured model has been found in the um
        it->second.Add(entity);
    }
    else
    {
        ents.insert(std::pair<TexturedModel, vector<Entity>>(entity.TexturedModel, vector<Entity>{ entity }));
    }
}

void Render()
{
    // some DX11 code

    RenderEntities(ents); // this func iterates over the um and uses the textured model once for every set of enrities that share it
    ents.clear();
}

100 objects get rendered smoothly, but adding more than that decreases my FPS exponentially

[fewdiefie]

@leamer2 ok thanks, I'll check the books

[helios]

First, why do you repopulate the map each frame? Surely you don't retexture every model every frame.

Second, you're copying the TexturedModel and Entity when you add them to the map. Do these classes implement a deep copy? If so, I'm not surprised your code is only able to handle 100 objects. You'd be copying either GPU objects or in-RAM geometry data just to render. That would have to be the worst possible way to go about doing it.
Even if the classes implement some kind of shallow copy, that's still absurdly wasteful. Just insert pointers to the objects and implement a hash function that dereferences the key.

Always, always check that you're using the available facilities as best as possible before seeking more esoteric solutions. What you've said here would be like asking where to buy an atomic clock, because your cell phone clock isn't accurate enough to tell you when it's lunchtime. Maybe, just maybe you might be using your clock wrong.