What kind of data structure should I use for a resource container?

Question

I am curious what kind of container would be the best choice for a resource container. BTree, binary search tree or something else? What like is the priority of the operations over it? So best inserting performance or best searching performance or between them?

Are there any open source implementation over the net?

Answer 1

So, let's look first at your likely usage pattern.

• First, you want to be able to insert and remove in constant time. You don't want to be troubled by the number of other resources loaded.
• Second, once a resource has been loaded and queried, you can assume that whoever needs it has access to it (via smart pointer or somesuch); so, you don't have to worry about repeated banging on the manager.
• Third, you probably don't care what the order of the things in memory is.

This sounds like a perfect place to use a HashMap or something similar, mapping resource names to allocated resources.

That's the frontend, in-memory part of things. The backend on-disk solution is something else. I'd suggest using a flat pile of files, or something like PhysicsFS if you want features like a Quake-style .pak (really .zip) archive system.

Note that for some things, like textures, you want to have a way of handling losing the hardware-specific storage; for example, if a graphics card evicts your memory due to alt-tabbing or something weird you want to be able to reload it transparently. In that case, you probably will need to maintain some extra data instead of just a reference to the resource in memory.