Le moins Récemment Utilisé le cache à l'aide de C++

Je suis en train de mettre en œuvre LRU Cache à l'aide de C++ . Je voudrais savoir quelle est la meilleure conception pour les mettre en œuvre. Je sais LRU doit fournir find(), ajouter un élément et de supprimer un élément. La suppression doit supprimer la LRU élément. quel est le meilleur ADTs pour mettre en œuvre cette
Ex: Si j'utilise une carte avec élément que la valeur et le compteur de temps que la clé je peux de recherche en O(logn) du temps, de l'Insertion est O(n), la suppression est en O(logn).

double possible de LRU mise en œuvre dans la production de code
boost::multiindex où les touches sont "CLÉ" et "heure du dernier accès". En fait, les docs pour multiindex montrer comment faire un cache LRU (bien qu'ils l'appellent MRU)

OriginalL'auteur brett | 2010-09-03