Newsgroup: it.comp.lang.c++
Titolo: Containers e Vettori

Volevo sapere se esiste gia' qualche libreria che consenta di gestire un 
semplice vettore venendo in contro alle esigenze che si hanno quando si 
vogliono effettuare operazioni di eliminazione inserimento elementi ed 
operazioni di accesso diretto agli elementi .
Per spiegarmi meglio si puo' prendere come riferimento il vector delle STL 
in cui e' garantita una complessita' O(1) per l' accesso con indice agli 
elementi del vettore ma una complessita' O(N) per l' inserimento ed 
eliminazione elementi .
Storicamente quando si volgiono effettuare operazioni di inseirmento ed 
eliminazione elementi si deve passare ad una gestione  a liste avendo quindi 
un O(1) per queste operazioni ma un O(N) per l' accesso agli elementi.
Quello che sto' cercando e' una struttura che mi dia capra e cavoli, una 
struttura che mi permetta magari un accesso O(log)  agli elementi ed un 
~O(1) per le operazioni di inserimento ed eliminazione.
L' alternativa e' farmela utilizzando un albero che viene riempito in modo 
ordinato tentando di bilanciarlo durante il riempimento ed un sacco di 
problemi relativi da affrontare .
Esiste gia' qualcosa del genere?
Ciao, Denis. 

Ad esempio std::map e std::set.
Ciao,
Nicola


La map utilizza gli alberi per gestire gli elementi ma da quanto ho capito 
non fa niente per mantenerli bilanciati il che significa che l' accesso ad 
un elemento si ha con un O(n) , ed il problema e' che questo non accade 
raramente ma molto frequentemente basti pensare che creando una vettore 
semplicemente aggiungendo sempre alla fine si ottiene un albero totalmente 
sbilanciato con un accesso di O(n) pari ad una lista .
Oltre a questo svantaggio ( almeno l' implementazione che utilizzo io delle 
stl ) l' aggiunta di elementi richiede un costant_time o meglio finito il 
buffer preallocato viene effettuato uno swap su un' altra area di memoria 
portando quindi una complessita O(n) .
Ricapitolando si ha O(n) per inserimento elementi O(n) per accesso elementi 
O(1) per l' eliminazione , direi che non va proprio bene.
Puoi confermare ?
Ciao, Denis 

 un elemento si ha con un O(n)
No. Per i container associativi (map, set, multimap, multiset) lo Standard
richiede che le operazioni di inserimento e ricerca abbiano complessità
logaritmica (v. 32.1.2 [lib.associative.reqmts]). Credo che di solito
vengano usati alberi RB.
Max

  Credo che di solito vengano usati alberi RB.
La libreria di GNU usa appunto una versione modificata di alberi RB (se
ricordo anche io bene)
-- 
[ RiK0                                ]
[ Go away! The internet is full!      ]
[ Non credo negli schemi non vincenti ]

Si, vengono utilizzati alberi RB
Ciao, Denis 

Dato che la Map utilizza alberi rb garantisce un inserimento con O(logn) 
rimane il problema di come utilizzarla per risolvere il problema che ho 
proposto infatti se utilizzo come chiave l' indice dell' elemento del 
vettore ad ogni inserimento in mezzo al mio vettore dovre aggiornare tutte 
le chiavi per avere gli indici corretti. Sicuramente un implementazione 
particolare che utilizzi gli alberi rb risolverebbe il problema . Esiste 


Secondo me dovresti usare solo la map e lasciar stare il vector. La
chiave e' quella che utilizzeresti per cercare gli elementi ne tuo
vettore, che dai tuoi discorsi sembrerebbero essere naturalmente
ordinati. Se non lo sono, che senso ha parlare di accesso in tempo
logaritmico?
Ciao,
Nicola

 ha scritto nel messaggio 
news:1113828871....@l41g2000cwc.googlegroups.com...


 Inserimento/Eliminazione elementi  O(LogN)
Intanto la terminologia: se l'accesso non e' O(1) non e' un vettore.
In secondo luogo, per avere un accesso migliore di O(n) deve esistere
un criterio di ordinamento utilizzabile sia in inserimento che in
estrazione. Questo puo' essere legato all'ordine di inserimento, ma in
questo caso l'unica speranza di accedere in modo migliore di O(n) e'
usare una pila o una coda o una combinazione delle due, ovvero devi
accedere nell'ordne di arrivo o in quello inverso.
Altrimenti deve esistere un criterio di ordinamento calcolabile
confrontando due elementi. Se e' un "ordinamento stretto debole"
(strict weak ordering) come chiesto dallo standard per i contenitori
associativi puoi usare set, map e derivati, oppure un vector ordinato.
In alternativa puoi adottare un approccio tipo hash_table, oppure
contenitori piu' adatti a criteri di ordinamento complessi, come gli
alberi ternari.
Resta il fatto che se devi verificare ogni elemento per capire se e'
quello che ti serve avrai sempre accesso O(n), indipendentemente dal
contenitore che usi.
Ciao,
Nicola
