In the past week of coding/testing/profiling. I touched a few of the different STL container types.
Here is what I think about them:
1. STD::Vector. My favorite. Much like a standard c array, yet with a lot of methods attached to it. It is very quick. The ability to reserve space makes it absolutely effective in reducing memory bloat also saves me from having to manage the malloc/calloc/free.
2. STD::TR1::Unordered_Map. I use this on the HashNodesClass (branch object) storage, with only 40k - 100k keys it does a great job and is pretty fast. Seems to do a pretty good job managing it’s memory bloat and is pretty quick on lookups. I originally tried to use this as containers for tiles but wasn’t fast enough and the bloat was almost as bad as a std::map.
3. STD::Queue. I was playing with the idea of adding a cache method inside of the HashNodesClass class. Yet after a day of programming and testing, I found just using the random access method HashNodesClass::get was still quicker then going through the caching logic (even compared to a best case scenario of 100% cache hit rate on sequential reads). The checking of Queue.empty(), Queue.pop() and destructor of a std::pair<bool, unsigned int> all added up to 2 seconds for 20 million calls. Queue is pretty nice for its FIFO. I think if I were to play with caching again, I would try a STD::DeQueue (double ended queue).
4. Std::Map. For it’s ease of use and automatic clean up,indexing, sorting, it is the dull swiss army knife of C++ type storage. It’s great for anything that doesn’t require a LOT of data in it and require fast lookups. I learned a useful tidbit to avoid. Nested maps are insanely slow on deconstruction.
In closing, of the C++ STL types, the vector speed wins (if you can effectively access the index). Map is easier to manage. Unordered_map(hash_map) seems to fall squarely in the middle. Every tool has its purpose and I now have a slightly better understanding of them.