Asp Forum - best data structure for a caching class

g3rc4n@gmail.com

12/14/2008 3:46:00 PM

i'm writing a class for caching lines of a text editor as accessing
the actually lines is expensive

now i know that caching works by whenever cache is accsed it's put the
the front of the list, then when the cahce is full it's either the one
at the end of the list of removed or one at the begging, for me it's
the one at the end

anyway i'm wondering whats the best std libary container for this? atm
i'm using a std::list<std::pair<key,T> >

template<typename E>
void assert_(const bool assertion, E e = E()){
if(!assertion)
throw e;
}

template<typename KEY, typename T>
class cache_table{
public:
typedef std::size_t size_type;
typedef KEY key_type;
typedef T cache_type;
typedef cache_type& cache_ref;
private:
typedef std::pair<key_type,cache_type> element_type;
typedef std::list<element_type> list_type;
typedef typename list_type::iterator LI;
typedef typename list_type::const_iterator CLI;
public:
struct invalid_cache : public std::exception{};

public:
cache_table(const size_type max_cache_size):
max_cache_size_((max_cache_size>1?max_cache_size:1)){
}
const bool is_cached(const key_type k){
return (find(k)!=cache_list_.end());
}
cache_ref get_cache(const key_type k){
LI iter(find(k));
assert_<invalid_cache>(iter!=cache_list_.end());
move_to_front(iter);
return cache_list_.begin()->second;
}
void put_cache(const key_type k, const cache_type& c){
add(element_type(k,c));
}
void remove_cache(const key_type k){
LI iter(find(k));
assert_<invalid_cache>(iter!=cache_list_.end());
cache_list_.erase(iter);
}
void clear(){
cache_list_.clear();
}
private:
LI find(const key_type k){
LI iter(cache_list_.begin());
for(;iter!=cache_list_.end();++iter)
if(iter->first == k)
break;
return iter;
}
void move_to_front(LI i){
element_type temp(*i);
cache_list_.erase(i);
cache_list_.push_front(temp);
}
void add(const element_type& e){
cache_list_.push_front(e);
if(cache_list_.size() > max_cache_size_)
cache_list_.pop_back();
}

const size_type max_cache_size_;
list_type cache_list_;
};

5 Answers

ebony.soft

12/15/2008 9:17:00 AM

On Dec 14, 6:46 pm, "g3r...@gmail.com" <g3r...@gmail.com> wrote:
> i'm writing a class for caching lines of a text editor as accessing
> the actually lines is expensive
>
> now i know that caching works by whenever cache is accsed it's put the
> the front of the list, then when the cahce is full it's either the one
> at the end of the list of removed or one at the begging, for me it's
> the one at the end
>
> anyway i'm wondering whats the best std libary container for this? atm
> i'm using a std::list<std::pair<key,T> >
>
> template<typename E>
> void assert_(const bool assertion, E e = E()){
> if(!assertion)
> throw e;
>
> }
>
> template<typename KEY, typename T>
> class cache_table{
> public:
> typedef std::size_t size_type;
> typedef KEY key_type;
> typedef T cache_type;
> typedef cache_type& cache_ref;
> private:
> typedef std::pair<key_type,cache_type> element_type;
> typedef std::list<element_type> list_type;
> typedef typename list_type::iterator LI;
> typedef typename list_type::const_iterator CLI;
> public:
> struct invalid_cache : public std::exception{};
>
> public:
> cache_table(const size_type max_cache_size):
> max_cache_size_((max_cache_size>1?max_cache_size:1)){
> }
> const bool is_cached(const key_type k){
> return (find(k)!=cache_list_.end());
> }
> cache_ref get_cache(const key_type k){
> LI iter(find(k));
> assert_<invalid_cache>(iter!=cache_list_.end());
> move_to_front(iter);
> return cache_list_.begin()->second;
> }
> void put_cache(const key_type k, const cache_type& c){
> add(element_type(k,c));
> }
> void remove_cache(const key_type k){
> LI iter(find(k));
> assert_<invalid_cache>(iter!=cache_list_.end());
> cache_list_.erase(iter);
> }
> void clear(){
> cache_list_.clear();
> }
> private:
> LI find(const key_type k){
> LI iter(cache_list_.begin());
> for(;iter!=cache_list_.end();++iter)
> if(iter->first == k)
> break;
> return iter;
> }
> void move_to_front(LI i){
> element_type temp(*i);
> cache_list_.erase(i);
> cache_list_.push_front(temp);
> }
> void add(const element_type& e){
> cache_list_.push_front(e);
> if(cache_list_.size() > max_cache_size_)
> cache_list_.pop_back();
> }
>
> const size_type max_cache_size_;
> list_type cache_list_;
>
>
>
> };- Hide quoted text -
>
> - Show quoted text -

Hi
I suggest to use map family containers (map, multimap or hash_map).
std::list<std::pair<key, value> >
is like a map with the main benefit of map, fast retrieval I mean. You
can wrap one of these container in your
own table data structure. It is definitely faster than a list.

Good luck,
Saeed Amrollahi

g3rc4n@gmail.com

12/15/2008 1:16:00 PM

On Dec 15, 9:17 am, ebony.s...@gmail.com wrote:
> On Dec 14, 6:46 pm, "g3r...@gmail.com" <g3r...@gmail.com> wrote:
>
>
>
> > i'm writing a class for caching lines of a text editor as accessing
> > the actually lines is expensive
>
> > now i know that caching works by whenever cache is accsed it's put the
> > the front of the list, then when the cahce is full it's either the one
> > at the end of the list of removed or one at the begging, for me it's
> > the one at the end
>
> > anyway i'm wondering whats the best std libary container for this? atm
> > i'm using a std::list<std::pair<key,T> >
>
> > template<typename E>
> > void assert_(const bool assertion, E e = E()){
> > if(!assertion)
> > throw e;
>
> > }
>
> > template<typename KEY, typename T>
> > class cache_table{
> > public:
> > typedef std::size_t size_type;
> > typedef KEY key_type;
> > typedef T cache_type;
> > typedef cache_type& cache_ref;
> > private:
> > typedef std::pair<key_type,cache_type> element_type;
> > typedef std::list<element_type> list_type;
> > typedef typename list_type::iterator LI;
> > typedef typename list_type::const_iterator CLI;
> > public:
> > struct invalid_cache : public std::exception{};
>
> > public:
> > cache_table(const size_type max_cache_size):
> > max_cache_size_((max_cache_size>1?max_cache_size:1)){
> > }
> > const bool is_cached(const key_type k){
> > return (find(k)!=cache_list_.end());
> > }
> > cache_ref get_cache(const key_type k){
> > LI iter(find(k));
> > assert_<invalid_cache>(iter!=cache_list_.end());
> > move_to_front(iter);
> > return cache_list_.begin()->second;
> > }
> > void put_cache(const key_type k, const cache_type& c){
> > add(element_type(k,c));
> > }
> > void remove_cache(const key_type k){
> > LI iter(find(k));
> > assert_<invalid_cache>(iter!=cache_list_.end());
> > cache_list_.erase(iter);
> > }
> > void clear(){
> > cache_list_.clear();
> > }
> > private:
> > LI find(const key_type k){
> > LI iter(cache_list_.begin());
> > for(;iter!=cache_list_.end();++iter)
> > if(iter->first == k)
> > break;
> > return iter;
> > }
> > void move_to_front(LI i){
> > element_type temp(*i);
> > cache_list_.erase(i);
> > cache_list_.push_front(temp);
> > }
> > void add(const element_type& e){
> > cache_list_.push_front(e);
> > if(cache_list_.size() > max_cache_size_)
> > cache_list_.pop_back();
> > }
>
> > const size_type max_cache_size_;
> > list_type cache_list_;
>
> > };- Hide quoted text -
>
> > - Show quoted text -
>
> Hi
> I suggest to use map family containers (map, multimap or hash_map).
> std::list<std::pair<key, value> >
> is like a map with the main benefit of map, fast retrieval I mean. You
> can wrap one of these container in your
> own table data structure. It is definitely faster than a list.
>
> Good luck,
> Saeed Amrollahi

yeah but i need to order/reorder them, every time one is accesed so
they are ordered from last accesed to one accesed longest ago, i don't
think i can do that with a map?

tni

12/15/2008 3:59:00 PM

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

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

James Kanze

12/19/2008 9:03:00 AM

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/t......

> > 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ée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

coal

12/19/2008 4:54:00 PM

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/t......
> > > 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.
>

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

comp.lang.c++

best data structure for a caching class

g3rc4n@gmail.com

ebony.soft

g3rc4n@gmail.com

tni

James Kanze

coal

x Login to ForumsZone