Bonjour,

Pour l'implémentation d'un algorithme de réorganisation de l'ordre de vertices, j'ai du modéliser un cache LRU (Least Recently Used), avec une taille limite, l'obligation de n'avoir qu'un seul élément identique (comme dans un set). Si jamais un élément déjà existant dans le cache est ajouté, il est tout simplement remis en tête du cache. Si la valeur est ajoutée correctement sans que d'autres soient dégagées du cache, cette même valeur est renvoyée, sinon, c'est la valeur qui sort du cache qui est renvoyée. Je savais pas comment faire autrement, mais il me fallait obligatoirement récupérer les éléments renvoyés.

Ca utilise un deque, je pense que ça doit être assez performant (toutes les fonctions utilisées sont de complexité constante, à part pour la fonction find (je pense qu'avec un unordered_set ça pourrait être plus performant, mais mon implémentation 'ne dispose pas) :

// Fonction implémentant de manière efficace un cache LRU (Least Recently Used)

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
#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