1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
| #ifndef LRUCACHE_HPP
#define LRUCACHE_HPP
#include <iostream>
#include <cassert>
#include <deque>
#include <algorithm>
// Pour un cache en utilisant une deque
template <typename Value_Type>
class LRUCache
{
public:
LRUCache (const std::size_t maxSize)
: maxSize (maxSize)
{
}
private:
// Quelques typedefs pour faciliter le travail...
typedef typename std::deque<Value_Type>::iterator deq_iterator;
typedef typename std::deque<Value_Type>::const_iterator deq_const_iterator;
// Taille maximale du cache
std::size_t maxSize;
// Les données en elle-même
std::deque<Value_Type> LRUList;
public:
// On cherche un élément
deq_iterator find (const Value_Type & value)
{
// On recherche l'élément
deq_iterator deq_iter = std::find (LRUList.begin(), LRUList.end(),
value);
// Si aucun élément n'a été trouvé, on retourne l'itérateur vers la fin
if (deq_iter == LRUList.end())
return deq_iter;
// Sinon, on replace l'élément au début de la liste
Value_Type val = *deq_iter;
LRUList.erase (deq_iter);
LRUList.push_front (val);
// On renvoit l'élément
return (LRUList.begin());
}
// Fonction pour insérer un élément
Value_Type insert (const Value_Type & value)
{
// On recherche si l'élément est déjà dans la liste
deq_iterator deq_iterator = find (value);
// Si l'élément n'est pas encore présent, on l'ajoute à la fin de la liste.
// S'il est présent, il sera automatiquement ajouté au début (MRU)
if (deq_iterator == LRUList.end())
LRUList.push_front (value);
// On vérifie si on ne dépasse pas la taille maximale du cache
if (LRUList.size() > maxSize)
{
// On récupère la valeur de l'élément qui va être supprimé
Value_Type val = LRUList.back();
// On supprime le dernier élément
LRUList.pop_back();
// On renvoit l'élément
return val;
}
// Sinon, on retourne l'élément qui vient d'être ajouté
return (LRUList.front());
}
// Pour accéder à un élément. Pour une raison que j'ignore, le code ne fonctionne
// pas avec un deque, j'ai donc été obligé de l'implémenter avec une list, qui
// n'offre pas d'accès direct
const Value_Type & operator[] (const std::size_t idx) const
{
assert (idx < maxSize);
return LRUList[idx];
}
// On affiche les éléments dans l'ordre, du plus récent au plus ancien
void Write () const
{
for (deq_const_iterator deq_const_iter = LRUList.begin() ;
deq_const_iter != LRUList.end() ; ++deq_const_iter)
{
std::cout << *deq_const_iter << std::endl;
}
}
};
#endif // LRUCACHE_HPP |
Partager