Newsgroup: it.comp.lang.c++
Titolo: _M_node in STL::MAP

ho il seguente MAP
map<const char*, char*, f_cmp_string> store;
e il suo iteratore
typedef map<const char*, char*, f_cmp_string>  ::iterator mio_iterator;
ho popolato correttamente la struttura,
essettuo una ricerca e salvo la variabile X
mio_iterator X=(store.find("pippo")._M_node);
la domanda è: avendo la variabile X in che modo è possibile puntare
direttamente alla struttura che contiene la stringa "pippo" senza
effettuare nuovamente una ricerca?
grazie

 direttamente alla struttura che contiene la stringa "pippo" senza
*X e' un reference alla tua stringa; altrimenti qualsiasi cosa
legittima tu possa voler fare alla tua mappa richiede un puntatore,
ovvero ad esempio X.
Vorse faresti meglio a spiegare cosa cerchi di ottenere.
Ciao,
Nicola

Nicola Musatti ha scritto:

grazie per la risposta,
cercherò di essere piu chiaro:
ho 2 strutture una MULTIMAP e una MAP
le due strutture sono in relazione fra di loro medianti delle chiavi
MULTIMAP:
"a1"->"b1"
"a1"->"b2"
"a2"->"b2"
"a3"->"b3"
MAP:
"b1"->"pippo"
"b2"->"topolino"
"b3"->"pluto"
quello che devo fare è trovare il secondo campo di TAB partendo dal
primo di MULTIMAP,
ad esempio
cerco "a1" in multimap e trovo 2 item ("b1" e "b2") complessità di
ricerca (O(log N))
cerco "b1" e "b2" in map ed ottengo "pippo" e "topolino" complessità
di ricerca 2*(O(log N))
la complessità totale è (O(log N)) + 2*(O(log M))
dove N è la cardinalità di MULTIMAP ed M la cardinalità di MAP
se in multimap avessi trovato 5000 item legati ad "a1" la complessità
sarebbe
(O(log N)) + 5000*(O(log M))
per abbattere questa complessità vorrei associare agli itmem di
MULTIMAP i riferimenti (puntatori ?)
degli item di MAP
cioè:
MULTIMAP:
"a1"->["b1",0x001]
"a1"->["b2",0x002]
"a2"->["b2",0x002]
"a3"->["b3",0x004]
MAP:
"b1"->"pippo" 				(0x001)
"b2"->"topolino" 			(0x002)
"b3"->"pluto" 				(0x004)
in questo caso la complessità sarebbe (O(log N))+2 perchè non dovrei
piu' ricercare "b1" e "b2"
in MAP in quanto avrei già questi riferimenti in MULTIMAP
ciao

 piu' ricercare "b1" e "b2"
La scrittura "(O(log N))+2" non ha molto senso, a voler essere pignoli.
Kiuhnm

 dove N è la cardinalità di MULTIMAP ed M la cardinalità di MAP
Hai diverse alternative, che dipendono da cos'altro devi fare con le
tue mappe. Una e' avere solo la multimappa, dichiarata:
std::multimap<char *, std::pair<char *, char *> >;
Avresti quindi
"a1"->( "b1", "pippo" )
"a1"->( "b2", "topolino" )
"a2"->( "b2", "topolino" )
"a3"->( "b3", "pluto" )
Perdendo pero' la possibilita' di ricercare direttamente sulla chiave
della mappa. Un'altra alternativa comporta la memorizzazione nella
multimappa di iteratori della mappa. Questo comporta pero' complessita'
di gestione se devi rimuovere elementi.
Altrimenti puoi provare a vedere se la libreria Boost.Multi-index
( 
http://boost.org/libs/multi_index/doc/index.html
 )
puo' fare al caso tuo.
Ciao,
Nicola

 std::multimap<char *, std::pair<char *, char *> >;
Non credo che questa soluzione sia applicabile, altrimenti il problema è 
più banale di quanto detto.
Kiuhnm


Probabilmente no, ma a volte i nostri connazionali amano soluzioni, per
cosi dire, rococo'.
Ciao,
Nicola Musatti

 "b3"->"pluto"
prova ad usare solo una multimap di questo tipo:
std::multimap< std::string, tr1::shared_ptr<std::string> >
praticamente come chiave hai una stringa e come valore un puntatore ad
una stringa.
shared_ptr e' un puntatore smart, ovvero ti aiuta nel memory management
degli oggetti di tipo stringa. shared_ptr e' reference counted quindi
non appena togli dalla mappa l'ultimo shared_ptr che punta ad un certo
oggetto tale oggetto viene distrutto (e la sua memoria deallocata) in
automatico.
shared_ptr lo trovi in tr1 o boost. 
Tommaso
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG