STL Lists and Resource Cache's

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • STL Lists and Resource Cache's

      First of all, I'd just like to say that this has been the single most helpful book in getting me into the swing of true Object-Oriented Programming (after moving from VB) and has taught me EVERYTHING I could have possibly asked so far. I can't believe how inexpensive the book is in comparison to a lot of higher priced... yet crapper.. books there are out there.

      Fanatical praise aside, I've started work on my first C++ game and am umming and erring about what to use for my Resource Management. Clearly an STL List is a bad idea because of the need for random access (for grabbing re-requested resource references and planting them back at the top of the list). So my thought is would using an STL map, or an STL map that maps the filenames to the corresponding entries in the STL list be a good idea? What are the downsides to this?

      Are there data structures you can suggest I research into that will be useful in this situation?

      Oh, and I decided to separate out the list into two lists, one which only gets dumped from if times get REALLY rough (containing files that are accessed all the time throughout the game [i.e. interface graphics]) and the other that contains the 'other stuff', things like character graphics or map data that isn't accessed so often and if need be can be dropped in favour of more recently requested resources. This is designed to speed up any traversing of the constantly changing list that need be done. Of course, if I implement a data structure with fast and available random access then this distinction may not be necessary.

      Of course, this being my first venture into the wide world of memory management AND C++, I'd be glad to hear any feedback and suggestions people might have on the subject :)

      Thanks.

      The post was edited 1 time, last by Mingoo ().

    • RE: STL Lists and Resource Cache's

      If you want crazy speed, and you probably do, create a hash for your resource names like is done with the event system event names in the book's example source code. This is a good compromise between ease of development and super fast access at runtime.

      Then, use an STL map to create a relationship between the resource hash ID and the data in memory.
      Mr.Mike
      Author, Programmer, Brewer, Patriot
    • std::list, std::map, and std::vector are used a lot by STL advocates...

      A std::vector is basically an array, but one that manages its own size and makes sure you don't assign something out of bounds. Accessing items in an array is quicker than finding it in a list, but removing items from this array can leave annoying holes if you don't repack the array after a removal. Access to a vector can be a O(1) operation.

      The std::list is best used when you need a structure that gets added to and removed from often enough that it turns out faster than an array. I often choose to use std::list to represent dynamic game elements in the world like bullets and enemies. Access to a list would be a O(n) operation.

      The std::map is what I use as a placeholder structure when I don't have time to implement my own hash map structure. It associates something to something so I could actually access objects by name from this map instead of iterating through a list until I find a name match. Because std::map uses a binary search tree as its internal data structure, access to a map is an O(log-base-2) operation... faster than a list, but slower than a vector. I really like the map structure!

      If you ever do implement that hash map, you get the benefits of the std::map, but with an access time of roughly O(1).

      Note that no matter what structure you use, iteration through all items in the structure through the use of an STL iterator is an O(n) operation... It is only the accessors to these structures (looking for a specific item) that varies.

      Also, using these structures in combination with smart pointers makes life a whole lot easier since you won't have to deal with issues that come from deleting objects (or forgetting to delete them) once they are removed from the list.

      Something else that might come in handy is that if you #include <algorithm>, you gain the ability to use some of STL's provided helper functions like "std::find".

      The post was edited 3 times, last by Kain ().