Re: best data structure for a caching class
On Dec 19, 2:47 am, "g3r...@gmail.com" <g3r...@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/tu=
torial/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;
};
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).
but does that order them in when they where last accessed?
A priori, no. But if I've understood the documentation
correctly, one possible "indexing" is order of insertion, so if
each time you access, you extract and re-insert, that should
work.
I'll admit that I'm not too familiar with the library. My first
reaction would have been to use an invasive double linked list
for the access ordering, keeping the elements themselves in a
set.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34