Re: best data structure for a caching class

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

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<CacheEntr=

            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).