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 |
