Datenstruktur fuer Caching
-
Hallo Leute!
Ich benoetige einen fixed-size Cache, der aelteste Elemente loescht, sobald die Groesse erreicht ist, wie in einer Queue. Allerdings moechte ich die Elemente anhand eines Keys einfuegen und suchen koennen. Bisher habe ich dafuer boost.multi_index verwendet, allerdings funktioniert dieser nicht mit movable-only Typen (aka unique_ptr), weshalb ich einen Workaround mit mutable schreiben musste.
Irgendwelche Vorschlaege, wie man das ohne Workaround, vielleicht sogar ausschliesslich mit Standard-Mitteln effizient hinbekommt?
Gruesse,
Der Kellerautomat
-
Ich kenne mich mit movable-only Typen nicht so gut aus, aber vielleicht funktioniert das hier:
eine map als Container für den Typen, parallel eine queue, in dem du die Keys enthälts? Wenn die Queue voll ist, nimmst du dir das erste Element und hast damit gleich den Key, um das Objekt aus der map zu löschen.
-
Ich habe einen LRU/LFU folgendermaßen implementiert:
eine list aus iteratoren in eine map und die map aus Key und iterator in die list.
dafür lässt sich super boost intrusive container nehmen - das spart allokationen.Die list gibt die reihenfolge an in der die Elemente gelöscht werden soll. bei LRU wird der iterator wieder einfach nach hinten gespliced und bei LFU hat die list neben einem iterator in die map auch einen counter der bei jedem Zugriff erhöht wird und bei jedem Zugriff wird das Elemente in der liste verschoben (falls notwendig) so dass das lfu element imer am ende ist.
-
Shade Of Mine schrieb:
dafür lässt sich super boost intrusive container nehmen - das spart allokationen.
+1 für intrusive container
spart nicht nur allokationen, auch kopfschmerzen wenn man versucht das ganze exception-safe zu implementieren.
-
Vielen Dank fuer eure Tipps. LRU-Cache war das Stichwort, das ich gesucht habe.
