J'ai écrit un cache. Cela fait suite à cette discussion.

Je n'ai rien inventé, j'ai juste amélioré l'idée trouvée ici. Autant j'aime bien l'idée car simple, autant l'implémentation est assez lourde et peu pratique.

Voici une autre solution (pas encore de callback dont question dans l'autre discussion).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
template <typename T>
struct cache_value
{
	T & s_value;
	bool s_created;
 
	cache_value(T & value,bool created):s_value(value),s_created(created) {}
};
 
 
#ifdef USE_UNORDERED_SET
template <typename K, typename T, typename PrHash = boost::hash<K>, typename PrEqual = std::equal_to<K> >
#else
template <typename K, typename T, typename PrLess = std::less<K> >
#endif
class cache
{
	//The cache organize a MRU/LRU collection of cells in a bidirectional circular list.
	//The MRU cell is stored in f_mru_cell, the LRU cell is thus f_mru_cell->s_prev.
	//The cells are also stored in a std::set for a fast key search.
	struct cell
	{
		cell *s_prev,*s_next;
		K s_key;
		T s_value;
 
		cell(K key):s_key(key) {s_next=s_prev=this;}
 
		void attach_before(const cell *p)
		{
			p=p->s_prev;
			s_prev=(s_next=p->s_next)->s_prev;
			s_next->s_prev=s_prev->s_next=this;
		}
		void detach()
		{
			s_next->s_prev=s_prev;
			s_prev->s_next=s_next;
		}
	};
#ifdef USE_UNORDERED_SET
	struct cell_predhash
	{
		std::size_t operator()(const cell *p) const
			{ return PrHash()(p->s_key); }
	};
	struct cell_predequal
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrEqual()(pl->s_key,pr->s_key); }
	};
	typedef boost::unordered_set<cell *,cell_predhash,cell_predequal> cell_set;
#else
	struct cell_predless
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrLess()(pl->s_key,pr->s_key); }
	};
	typedef std::set<cell *,cell_predless> cell_set;
#endif
 
	unsigned f_maxCell;
 
	/* TODO: use my own allocator */
	cell *f_mru_cell;
	cell_set f_set;
 
public:
	cache(unsigned maxCell): f_maxCell(maxCell<1?1:maxCell),f_mru_cell((cell *)0)
#ifdef USE_UNORDERED_SET
		,f_set(maxCell<1?1:maxCell)
#endif
		{}
	//copy contructor, assign operator ?
	~cache() { clear(); }
 
	void clear()
	{
		if (f_mru_cell)
		{
			//delete cells from LRU to MRU
			cell *lru_cell=f_mru_cell->s_prev;
			cell *p=lru_cell;
			do
			{
				cell *ptmp=p->s_prev;
				//cell deleted !!! caller MUST be informed
				delete p;
				p=ptmp;
			}
			while (p!=lru_cell);
		}
		f_mru_cell=(cell *)0;
		f_set.clear();
	}
 
	void reset(unsigned maxCell)
	{
		clear();
		f_maxCell=(maxCell<1?1:maxCell);
#ifdef USE_UNORDERED_SET
		f_set.rehash(maxCell<1?1:maxCell);
#endif
	}
 
	cache_value<T> fetch(K key)
	{
		cell tmp(key);
		cell_set::iterator it=f_set.find(&tmp);
		if (it!=f_set.end())
		{
			//key is found
			//(f_mru_cell can't be NULL)
			cell *found_cell=*it;
			if (f_mru_cell!=found_cell)
			{
				//adjust cell list, found cell becomes MRU cell
				found_cell->detach();
				found_cell->attach_before(f_mru_cell);
				f_mru_cell=found_cell;
			}
 
			//return T and notify that key was already in cache
			return cache_value<T>(found_cell->s_value,false);
		}
		else
		{
			//key not found
			cell *new_cell;
 
            if (f_set.size()>=f_maxCell)
			{
				//cache size limit reached, remove LRU cell
				//(f_mru_cell can't be NULL)
				cell *lru_cell=f_mru_cell->s_prev;
				tmp.s_key=lru_cell->s_key;
				f_set.erase(&tmp);
				lru_cell->detach();
				//cell deleted !!! caller MUST be informed
				lru_cell->~cell();
 
				//create a new cell (actually reuse the just destroyed LRU cell)
				new_cell=new(lru_cell) cell(key);
			}
			else
			{
				//create a new cell
				new_cell=new cell(key);
			}
 
			//insert the new cell in list
			if (f_mru_cell!=(cell *)0)
				new_cell->attach_before(f_mru_cell);
 
			//set the new MRU cell
			f_mru_cell=new_cell;
 
			//insert also the new cell in the std::set
			f_set.insert(new_cell);
 
			//return the created T and notify that it wasn't yet in cache
			return cache_value<T>(new_cell->s_value,true);
		}
	}
 
	void display()
	{
		if (f_mru_cell)
		{
			//display cell key from LRU to MRU
			cell *lru_cell=f_mru_cell->s_prev;
			cell *p=lru_cell;
			do
			{
				cell *ptmp=p->s_prev;
				std::cout << p->s_key << '"' << (p->s_value) << '"' << " - ";
				p=ptmp;
			}
			while (p!=lru_cell);
		}
		std::cout << '(' << f_set.size() << ')' << std::endl;
	}
};
La méthode display() ne sert qu'à vérifier "l'âge" des clés. Voici un code de test:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
void cachefetch(cache<unsigned,std::string> & c,unsigned key)
{
	char* HARD_DISK[] =
	{
		"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"
	};
	cache_value<std::string> pair=c.fetch(key);
	if (pair.s_created)
		pair.s_value=HARD_DISK[key];
}
 
 
int main(int argc, char* argv[])
{
		cache<unsigned,std::string> c(5);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,2);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,3);
		c.display();
		cachefetch(c,4);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,5);
		c.display();
		cachefetch(c,8);
		c.display();
		c.reset(54);
		c.display();
return 0;
}
Le code utilise std::set<> de la STL uniquement, mais avec #define USE_UNORDERED_SET il utilise boost::unordered_set<>.

Vos avis ?
Merci.