best data structure for a caching class

[g3rc4n]

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:air<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:air<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_;
};

 

[g3rc4n]

Hi
I suggest to use map family containers (map, multimap or hash_map).
std::list<std:air<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]

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


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>,

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

 

[g3rc4n]

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;

};

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?

 

[James Kanze]

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.

 

[tni]

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>,

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:air<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();
}

 

[Martin Eisenberg]

but does that order them in when they where last accessed?

LRU caching is just one way to get the data access speed your
application needs; insisting on its use may be putting the cart
before the horse. Here's some literature on text editors:

http://www.finseth.com/craft/
http://www.cs.unm.edu/~crowley/papers/sds/sds.html


Martin

 

[coal]

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