Re: best data structure for a caching class

From:

coal@mailvault.com

Newsgroups:

comp.lang.c++

Date:

Fri, 19 Dec 2008 08:53:42 -0800 (PST)

Message-ID:

<d24d916c-8a06-4e38-a139-e231c0ea5f84@w39g2000prb.googlegroups.com>

On Dec 19, 3:02 am, James Kanze <james.ka...@gmail.com> wrote:

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

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

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

That's right. I'm surprised this library hasn't been added to
the standard. It's more important than some of the other
Boost libraries that have been or are being added.

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.

Boost Intrusive could also be used.

Brian Wood
www.webEbenezer.net