Re: best data structure for a caching class
g3rc4n@gmail.com wrote:
On Dec 15, 3:58 pm, tni <nob...@example.com> wrote:
Take a look at Boost MultiIndex:http://www.boost.org/doc/libs/1_37_0/libs/multi_index/doc/tutorial/in...
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;
};
[...]
but does that order them in when they where last accessed?
You would do something like (you may want slightly different behavior,
e.g. updating existing elements in the cache if the value can change):
template<class K, class T>
void Cache<K, T>::addEntry(const K& key, T value) {
CacheEntry<K, T> cache_entry;
cache_entry.key = key;
cache_entry.value = value;
std::pair<CacheMultiIdx::iterator,bool> ins_res =
cache.push_front(cache_entry);
if(!ins_res.second){ // element was already in cache;
// move to front of LRU list
cache.relocate(cache.begin(), ins_res.first);
} else { // new element
while(cache.size() > MAX_CACHE_SIZE) cache.pop_back();
}
}
template<class K, class T>
T Cache<K, T>::getEntry(const K& key) {
CacheMultiIdx::nth_index<1>::type& hash_idx = cache.get<1>();
CacheMultiIdx::nth_index<1>::type::iterator it = hash_idx.find(key);
if(it != hash_idx.end()) {
// move accessed element to front of LRU list
cache.relocate(cache.begin(), cache.project<0>(it));
return (*it).value;
}
return T();
}