>>135じゃないけどシンプルにいくなら
{
map<key,value> data; // 本来のデータ
map<key,list<key>::iterator> lruindex; //
list<key> lrulist; // LRUリスト
... // mapと同じインターフェイス
}
みたいなクラスで要素の追加・削除・参照とかの時にLRUリスト見て処理すればいい