Re: best data structure for a caching class

Take a look at Boost
MultiIndex:http://www.boost.org/doc/libs/1_37_0/libs/multi_index/doc/tu=

Something like:

template<class K, class T>
struct CacheEntry {
     K key;
     T value;
};

using namespace boost::multi_index;

template<class K, class T>
class Cache {
     typedef boost::multi_index_container<
         CacheEntry<K, T>,
         indexed_by<sequenced<>, hashed_unique<member<CacheEntry<K, T>,
            K, &CacheEntry<K, T>::key> >
         >
     > CacheMultiIdx;
public:
     Cache();
     void addEntry(const K& key, T value);
     T getEntry(const K& key);
private:
     CacheMultiIdx cache;
};

You can also do that by hand, just use a map or hash table
that contains pointers (iterators work fine too, since they
are not invalidated when you reorganize the list) to your
list elements. Of course, you need to keep the the list and
map in sync (the boost multiindex container does that
automagically).