Size limited cache

I was reading a bit from Knuth's Stanford GraphBase (SGB). He likes to do a lot of pointer handling. In TAOCP he says something along the lines: people avoid handling list themselves because there is a general perception that it is hard to do so; we'll try to dispell that myth. Also he has a paper entitled Dancing Links. Well, Knuth in general likes to do low-level and deep stuff.

Why am I writing about this? Because reading SGB made me a bit nostalgic: I use the Standard Template Library (STL) and very rarely do low level stuff myself. Out of nowhere I remembered that a few days ago I was thinking about how I'd implement a size limited cache with a Least Recently Used (LRU) eviction policy. You need such a beast when you want to cache the result of the last computetions of some function without eating too much memory. The LRU policy is the simplest and probably easiest to implement. The solution I came up at that time (but never implemented) used a map and a doubly linked list to offer O(lgN) operations. So I thought: OK, let me implement this list by hand instead of using STL's list. it should be easy enough and the result would be some code that I sometimes wanted to have handy, but that I never implemented because the effort didn't seem to be worth it. Now I was in the mood of handling pointers :)

Without much comments, here is the code:

   1:/*
   2:    Implementation of a size limited cache. It is based on STL's map.
   3: */
   4:
   5:#include <cassert>
   6:#include <iostream>
   7:#include <map>
   8:
   9:using namespace std;
  10:
  11:template <typename K, typename V>
  12:class Cache
  13:{
  14:private:
  15:    // --- Internal types ---
  16:    struct Node;
  17:    typedef typename map<K, Node*>::iterator It;
  18:    struct Node {
  19:        It it;
  20:        V v;
  21:        Node *L, *R;
  22:    };
  23:    
  24:public:
  25:    // --- Exception for outside ---
  26:    struct NotFound {};
  27:    
  28:public:
  29:    // --- Construction / Destruction ---
  30:    Cache(int sz) : sz(sz) 
  31:    {
  32:        assert (sz > 0);
  33:        q = new Node;
  34:        q->L = q->R = q;
  35:    }
  36:    
  37:    ~Cache()
  38:    {
  39:        Node *d = q, *t;
  40:        do {
  41:            t = d->R;
  42:            delete d;
  43:            d = t;
  44:        } while (d != q);
  45:    }
  46:    
  47:    // --- Put / Get / Rem interface ---
  48:    void Put(const K& k, const V& v)
  49:    {
  50:        Node* t;
  51:        It it = m.find(k);
  52:        if (it == m.end()) {
  53:            if (int(m.size()) == sz) {
  54:                m.erase(q->R->it);
  55:                q->R = q->R->R;
  56:                delete q->R->L;
  57:                q->R->L = q;
  58:            }
  59:            t = new Node;
  60:            t->it = m.insert(m.begin(), make_pair(k, t)); t->v = v;
  61:        } else {
  62:            t = it->second;
  63:            t->L->R = t->R;
  64:            t->R->L = t->L;
  65:        }
  66:        t->L = q->L;
  67:        t->R = q;
  68:        t->L->R = t;
  69:        t->R->L = t;
  70:    }
  71:    
  72:    V Get(const K& k)
  73:    {
  74:        It it = m.find(k);
  75:        if (it == m.end()) throw NotFound();
  76:        Node* t = it->second;
  77:        t->L->R = t->R;
  78:        t->R->L = t->L;
  79:        t->L = q->L;
  80:        t->R = q;
  81:        t->L->R = t;
  82:        t->R->L = t;
  83:        return t->v;
  84:    }
  85:    
  86:    void Rem(const K& k)
  87:    {
  88:        It it = m.find(k);
  89:        if (it == m.end()) throw NotFound();
  90:        Node* t = it->second;
  91:        t->L->R = t->R;
  92:        t->R->L = t->L;
  93:        delete t;
  94:        m.erase(it);
  95:    }
  96:    
  97:private:
  98:    // --- Internal data ---
  99:    map<K, Node*> m;
 100:    int sz;
 101:    Node* q;
 102:};
 103:
 104:int main()
 105:{
 106:    Cache<char, int> cache(3);
 107:    cache.Put('a', 2);
 108:    cache.Put('b', 'b');
 109:    cache.Put('c', 10);
 110:    cache.Put('d', 20); // a should be removed
 111:    try { cout << cache.Get('c') << endl; } catch (...) {}
 112:    try { cout << cache.Get('a') << endl; } catch (...) {}
 113:    try { cout << cache.Get('b') << endl; } catch (...) {}
 114:    try { cout << cache.Get('d') << endl; } catch (...) {}
 115:    cache.Put('e', 100); // c should be removed
 116:    try { cout << cache.Get('a') << endl; } catch (...) {}
 117:    try { cout << cache.Get('b') << endl; } catch (...) {}
 118:    try { cout << cache.Get('c') << endl; } catch (...) {}
 119:    try { cout << cache.Get('d') << endl; } catch (...) {}
 120:    try { cout << cache.Get('e') << endl; } catch (...) {}
 121:}
 122: