Am längsten nicht verwendetes Objekt / LRU

Diese oder abgewandelte Datenstrukturen finden sich in vielen Speichermanagementteilen von Betriebsystemen, Grafik-/Audiokernen von Spielen und auch im "Zuletzt geöffnet"-Menüpunkt der Mehrzahl der Dateibearbeitungsprogramme wieder. Hierdurch kann unter anderem, die Benutzung knapper Resourcen eingeschränkt werden.

Beispiel (Quellcode): lru.cpp
Download (Quellcode): lru.zip

Beschreibung

LRU / Am längsten nicht verwendetes Objekt während des Befüllens Die Datenstruktur bildet eine Liste, bei denen die Referenzen (oder auch die Objekte) mit begrenzter Anzahl gehalten werden. Wird ein Objekt benutzt, wird die Objektreferenz an den Anfang der Liste verschoben. Ist die Referenz noch nicht in der Liste, wird sie an den Anfang der Liste eingefügt. Ist die Liste zu lang, werden die Objekte am Listenende verworfen.

Abwandlungen:

Alternativ kann anstelle der Verschiebung der benutzen Objektreferenz an die erste Position, auch eine schrittweise Umpositionierung stattfinden. So nähert sich die Referenz langsamer den Listenkopf, was je nach Fall bessere Ergebnisse erzielen kann.
Es müssen nicht Listenelemente gezählt werden, es können auch Metadaten aus den Objekten sein, die über die zu löschenden Objekte entscheiden.
Die Datenstruktur kann auch eine schnelle Suchfunktion für Objekte enthalten, falls die Objekte nicht selbst auf die Datenstruktur zugreifen können.

Durch den Beispielcode

Der Beispielcode, enthält zwei Klassen (C++), die den Behälter und Elemente definieren:

der Konstruktor für den Behälter
```
CLRUContainer(size_t nSize) : m_nSize(nSize) {}
```
```
52
```
Beim Erzeugen der Klasse, wird die Länge der Liste festgelegt.
Anlegen eines Elements
```
void Register(_TYPE* pElement)
```
```
59
```
Das Element wird am Anfang der Liste eingefügt und das letzte ggf. verworfen.
Entfernen eines Elements
```
void Unregister(_TYPE* pElement)
```
```
67
```
Das Objekt wird verworfen und die Listenposition freigegeben.
Benutzen eines Elements
```
void MoveToFront(_TYPE* pElement)
```
```
72
```
Schiebt das Element wieder an den Anfang der Liste,

Codeanmerkungen

Die Aufrufparameter des Programms werden als Objekt hinzugefügt oder verwendet:

for(int n=1; n<argc; n++)

So ergibt

./lru a b c d d b e f b

die Ausgabe

LRU test...

  5 elements:
     1. b
     2. f
     3. e
     4. d
     5. c