Newsgroup: it.comp.lang.c++
Titolo: Struttura dati per cache

Devo implementare una cache associativa del tipo CHIAVE->VALORE, e volendo
usare la libreria standard pensavo a map<CHIAVE,VALORE> oppure
hash_map<CHIAVE,VALORE>.
Il problema è che tale cache deve contenere al massimo M elementi, e
raggiunto tale limite devono essere scartati i vecchi record secondo una
politica LRU (last recently used). La prima cosa che ho pensato è
aggiungere un campo, un int ad esempio, che aggiornato ad ogni lettura mi
permetta di tenere traccia degli accessi.
La domanda è: quando devo eliminare un elemento, come faccio a trovare
quello avente tale campo più alto (o più basso) ? Purtroppo l'unico metodo
è scorrere tutti gli elementi... e questo a regime potrebbe essere costoso,
visto che ogni nuovo inserimento comporta una eliminazione.
Avete qualche tecnica migliore ? Magari anche utilizzando una struttura dati
aggiuntiva per tenere traccia degli accessi, non so...
Ringrazio in anticipo !! :)
-- 
LF

 costoso, visto che ogni nuovo inserimento comporta una eliminazione.
Puoi fare così.
Costruisci un container associativo chiave/valore dove il valore è un 
puntatore a una struttura che
 1. incorpori un riferimento alla posizione del proprio "slot" nel 
container associativo (ad esempio, il valore di un iteratore di map<>)
 2. sia predisposta per partecipare ad una lista double-linked.
L'operazione di lookup quindi seguirà questo protocollo.
- cercare la chiave nella mappa
 - se la chiave non esiste 
     - creare una nuova instanza della struttura 
     - inserire il puntatore nella mappa
     - aggiornare il valore del riferimento allo "slot" (v. punto 1)
     - inserire l'istanza in testa alla lista
     - se la dimensione della mappa supera M
       - togliere dalla lista l'istanza in coda
       - rimuovere l'istanza dalla mappa utilizzando il 
          riferimento allo "slot"
       - distruggere l'istanza
 - se la chiave esiste
     - spostare l'istanza in testa alla lista
Se come mappa usiamo std::map<> e come riferimento allo "slot" un 
iteratore, le operazioni di ricerca/inserimento avranno complessità 
logaritmica, mentre tutte le altre operazioni (inserimento, rimozione e 
spostamento nella lista e rimozione dalla mappa) avranno complessità 
costante. (Nota che l'eliminazione di un elemento da una mappa 
non invalida gli iteratori che puntano ad altri elementi.)
Ricerca e inserimento nella mappa possono essere realizzate con un unica 
chiamata a 
  pair<iterator, bool> insert(const value_type& val);
Max

 Puoi fare così.
Anch'io avevo in mente qualcosa del genere ma non avevo ben chiaro come
implementarlo.
Grazie mille, il tuo aiuto mi è stato molto utile !!
-- 
LF

      - spostare l'istanza in testa alla lista
Sempre in riferimento agli oggetti della libreria standard, per far questo
devo eseguire una insert in testa seguita da una erase oppure esiste un
metodo per spostare direttamente un oggetto in una lista ?
Grazie ancora !! :)
-- 
LF

 metodo per spostare direttamente un oggetto in una lista ?
Che mi risulti no. Per questo ho suggerito l'uso di una lista "intrusiva" 
ad hoc, anziché utilizzare std::list.
Ho scritto due righe di codice. Se vuoi darci uno sguardo (e correggere 
eventuali errori)...
 
http://cassandra.comm2000.it/~maxim/pub/share/lru_cache_map.cpp
Max

 eventuali errori)...
Va benissimo, il gcc mi dà solo alcuni warning riguardo alle dichiarazioni
degli iteratori, che ho risolto aggiungendo typename...
Grazie !! :))
-- 
LF