Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
114 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Requirements revisited

Let's define the operations we want the cache to perform.

  • Creation and initialization
    We'd like to specify the cache size upon its creation - that is the maximal number of keys it stores.

  • Lookup
    We'd like to ask the cache for a key and get the value, or an indication that this key doesn't exist in the cache.

  • Insertion
    We'd like to add keys to the cache. If the key already exists in the cache, its value will be updated with the latest value. If there's no such key in the cache, it will be added to the cache. If the cache is full, the LRU key will be removed to make space for the new key.


We certainly need a data structure that lets us look up values for keys efficiently. This will be the core cache table. We can use the C++ standard map container for this purpose - it provides logarithmic lookup and insertion (O(log N) where N is the cache size).

But how do we implement LRU removal? We can keep some count of "recent access time stamp" for each key, but how do we know which to throw away? Going over the whole cache to find the LRU key is a O(N) operation - too slow.

We solve this using a very common programming trick - we sacrifice space for time. Such problems are usually solved by using another data structure that provides the special requirement quickly and is kept fully coherent with the main data structure. What we need here, for example, is a priority queue - keys sorted in a linear structure with the most recent key in some known location - like the front of the queue, which lets us remove it quickly.

This leaves the question of how to implement the queue. We could go for a simple array, but that won't do (can you figure out why?). The problem is that when there's a lookup on some cache key, it immediately becomes the most-recently-used key and should be marked as such, for example by being moved to the back of the queue. This operation is called splicing - take an item from the middle of a container and put it in the end. Splicing in arrays is expensive (O(N)), which is unacceptable.

Fortunately, there is a solution - a linked list. In a linked list insertion and removal at both ends is O(1), and so is splicing, given that we already have a pointer/handle to the key we want to splice. But that can be arranged by holding such a pointer in the main cache data structure.

So, we'll go for two data structures: a map for the table, and a list (another container in the C++ standard library) for the recent-usage queue. For each key, the table will hold the value and a pointer to the key in the queue, which makes it trivial to mark it as recent on lookups.

So, enough babbling, let's get to the code.


The source code package provided with this column contains a file named cache.h - this is the implementation of the cache (it is wholly in a .h file because it's templated):

template <typename key_type, typename value_type>
class cache

Our cache can work for any key type and value type, given to it at creation as template arguments. Here is a portion of the cache class that lists its data members:

typedef typename list<key_type>::iterator list_iter;
struct cached_value
  cached_value(value_type value_, list_iter cache_i_) 
    : value(value_), cache_i(cache_i_)

  value_type value;
  list_iter cache_i;
typedef typename map<key_type, cached_value>::iterator table_iter; 
unsigned maxsize;
list<key_type> lru_list;
map<key_type, cached_value> table;

maxsize is the maximal size given to the cache at creation. table is the main cache table - for each key, it holds a value and a pointer to the queue. lru_list is the queue - a list sorted by recent use (with the most recently used key in the front).

Note that the class also defines a cache_statistics subtype. This is to collect statistics of cache usage. The implementation of statistics is simple enough that I won't mention it in the column. It can be very useful, however, when you plan to use the cache for your needs and want to analyze its performance.

Lookup of keys in the cache is done as follows:

value_type* find(const key_type& key)
  table_iter ti = table.find(key);


  if (ti == table.end())
    return 0;


  list_iter li = ti->second.cache_i;
  lru_list.splice(lru_list.begin(), lru_list, li);

  return &(ti->second.value);

The key is looked up in the table which has efficient lookups. If the key wasn't found, we simply return 0. If the key was found, we have to splice the accessed key out of its place in the queue and place it in the front - since now this key is the most recently used. Then, we return the value of the key.

Insertion is just a little more complex:

void insert(const key_type& key, const value_type& value)
  value_type* valptr = find(key);

  if (valptr)
    *valptr = value;
    cached_value cv(value, lru_list.begin());
    table.insert(make_pair(key, cv));

    if (lru_list.size() > maxsize)
      key_type lru_key = lru_list.back();


First we look for the key in the table. Note that the local cache function find() is used here, because if we do find the element we want it marked as MRU.

If the key was found, we just update its value and return. More interesting is what happens when the key is not found - here the insertion takes place. After adding the key to the cache, we check to see if the cache size is exceeded. If it is, we throw out the key that's in the back of lru_list which is, if you recall, the LRU key - just what we need!

Using the cache

  Requirements revisited
  Using the cache

  Source code
  Printable version
  Discuss this article

The Series
  Part 1
  Part 2
  Part 3
  Part 4
  Part 5
  Part 6
  Part 7
  Part 8