Repository 32bit  Forum
Repository 64bit  Wiki

Classe Vector in C++

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

Classe Vector in C++

Messaggioda ccts2002 » lun nov 24, 2008 11:45

Salve a tutti!
avrei bisogno di un'informazione riguardo al classe "vector" del C++. mediante la funzione insert(...) posso inserire un elemento nel vettore in una determinata posizione. ma l'indirizzo di questo elemento quale sarà?
mi spiego. ho un vettore di 10 elementi. se ne inserisco uno tra il quarto e il quinto (per esempio) cosa succede agli indirizzi di memoria? l'indirizzo del nuovo elemento è uno nuovo (cioè dove il programma trova una parte di memoria non allocata) o è l'indirizzo dell'ex quinto che andrà quindi ad occupare l'indirizzo dell'ex-sesto, etc...
forse, se ho bisogno che nonostante l'inserimento l'indirizzo sia costante, devo usare le liste, giusto?

grazie!
Avatar utente
ccts2002
Linux 2.0
Linux 2.0
 
Messaggi: 155
Iscritto il: gio nov 09, 2006 23:20
Località: milano - trieste - catania

Re: Classe Vector in C++

Messaggioda lamarozzo » lun nov 24, 2008 12:01

la classe vector salva le informazioni in modo contiguo. Quindi ogni volta che fai un inserimento, la funzione insert deve traslare tutti gli elementi successivi a quello che vuoi inserire. Questa è un'operazione ordine N. Se hai bisogno di fare molti inserimenti, anzichè ricerche, ti conviene utilizzare una linked list.
Avatar utente
lamarozzo
Linux 2.6
Linux 2.6
 
Messaggi: 732
Iscritto il: mer lug 13, 2005 23:00
Località: Roma
Desktop: xfce
Distribuzione: archlinux

Re: Classe Vector in C++

Messaggioda m0rdr3d » lun nov 24, 2008 12:06

Secondo la documentazione che trovi qui i vector sono organizzati come aree contigue di memoria, in cui l'inserimento costante (ammortizzato) è dato solo all'inserimento in coda. L'inserimento in un punto qualsiasi è quindi più costoso, come spiegato nella sezione del metodo insert:
Because vectors keep an array format, insertions on positions other than the vector end are performed by moving all the elements between position and the end of the vector to their new positions, and then inserting the new element(s), which may not be a method as efficient as the insertion in other kinds of sequence containers (deque, list).

Se utilizzi spesso l'inserimento in una posizione interna al vector ti consiglio di usare una linked list, come tu stesso suggerivi.

Edit: uffa, preceduto... ;-)
Ultima modifica di m0rdr3d il lun nov 24, 2008 12:11, modificato 1 volta in totale.
Avatar utente
m0rdr3d
Linux 2.4
Linux 2.4
 
Messaggi: 404
Iscritto il: dom dic 24, 2006 13:40
Slackware: Slackware64-current
Kernel: 3.4.*
Desktop: KDE 4.8.2

Re: Classe Vector in C++

Messaggioda ccts2002 » lun nov 24, 2008 12:09

ho il problema di dover fare sia inserimenti che ricerche. avevo pensato di usare la classe vector proprio per il problema delle ricerche...fare tante ricerche in maniera sequenziale penso che vorrebbe troppo tempo...
non c'è una via di mezzo, vero???? :cry: :cry:
penso che opterò sui vettori, facendo però ogni volta ricercare l'indirizzo dell'elemento che mi interessa...
Avatar utente
ccts2002
Linux 2.0
Linux 2.0
 
Messaggi: 155
Iscritto il: gio nov 09, 2006 23:20
Località: milano - trieste - catania

Re: Classe Vector in C++

Messaggioda lamarozzo » lun nov 24, 2008 12:34

ccts2002 ha scritto:non c'è una via di mezzo, vero???? :cry: :cry:


Eccome se ci sono vie di mezzo, come ad esempio gli alberi. Questo è solo uno spunto ma se devi approfondire ti consiglio di chiedere a qualche informatico (esame di algoritmi e strutture dati?).

http://en.wikipedia.org/wiki/Self-balan ... earch_tree

D'altronde il tuo problema è alla base dei database. Dipende un po' dal problema che devi affrontare, ma se è così sensibile ai tempi di ricerca e inserimento ti consiglierei di interfacciarti direttamente ad un DBMS come MySQL.
Avatar utente
lamarozzo
Linux 2.6
Linux 2.6
 
Messaggi: 732
Iscritto il: mer lug 13, 2005 23:00
Località: Roma
Desktop: xfce
Distribuzione: archlinux

Re: Classe Vector in C++

Messaggioda elendil » lun nov 24, 2008 12:36

Purtroppo non conosco bene la STL, ma se ti serve fare molte operazioni di ricerca forse dovresti orientarti verso un tipo di struttura dati diverso basato su albero binario, tipo una map o un set, che se non ricordo male hanno il costo dell'operazione find logaritmico.

edit: magari per una piccola applicazione usare un DBMS è come ammazzare le mosche con un cannone :)
"In wars boy, fools kill other fools for foolish causes." (R. Jordan, The Wheel of Time book 1)
elendil
Linux 2.0
Linux 2.0
 
Messaggi: 103
Iscritto il: sab ago 09, 2008 11:39
Località: Carpineto Romano (RM)
Nome Cognome: Valerio
Slackware: 14
Kernel: 3.2.29
Desktop: xfce
Distribuzione: SalixOS

Re: Classe Vector in C++

Messaggioda m0rdr3d » lun nov 24, 2008 13:26

Se puoi darci qualche dettaglio in più possiamo vedere di cercare una soluzione soddisfacente. Non sono molto fresco di strutture dati, ma potrebbe essere l'occasione giusta per rinfrescarsi un po'.

P.S.: a proposito di rinfrescarsi, qui in veneto oggi abbiamo la neve...
Avatar utente
m0rdr3d
Linux 2.4
Linux 2.4
 
Messaggi: 404
Iscritto il: dom dic 24, 2006 13:40
Slackware: Slackware64-current
Kernel: 3.4.*
Desktop: KDE 4.8.2

Re: Classe Vector in C++

Messaggioda ccts2002 » lun nov 24, 2008 13:50

per l'applicazione che sto creando l'interfacciarsi con un database non è proponibile, dato che deve essere distribuibile su qualsiasi computer, che abbia o no un database...e fornirli insieme non mi sembra il caso... :D
penso che mi orienterò verso i map, utilizzando le liste come contenitori e un map che memorizzi gli indirizzi degli elementi delle liste...in questo modo, almeno teoricamente, dovrei mantenere l'inserimento delle liste e l'accesso agli elementi nella maniera migliore...
ma è una cosa che devo progettare bene per non fare casini...già questo mi costringe ad una riscrittura di buona parte del codice... :(
grazie mille a tutti!!!!!!!!!!!!!!
Avatar utente
ccts2002
Linux 2.0
Linux 2.0
 
Messaggi: 155
Iscritto il: gio nov 09, 2006 23:20
Località: milano - trieste - catania

Re: Classe Vector in C++

Messaggioda ksniffer » mar nov 25, 2008 11:57

Potresti provare sqlite. Un database leggerissimo scritto in C che adopera il file system. Sul sito puoi scaricare anche la versione composta da un unico file che puoi includere direttamente nel tuo applicativo. Poi potresti creartri una classe C++ per interfacciarti allo stesso usando le API di sqlite.
Avatar utente
ksniffer
Linux 2.6
Linux 2.6
 
Messaggi: 540
Iscritto il: lun lug 30, 2007 12:18
Kernel: 2.6.34
Desktop: KDE 4.4.4
Distribuzione: ArchLinux

Re: Classe Vector in C++

Messaggioda Blizzard » mar nov 25, 2008 16:24

ksniffer ha scritto:Potresti provare sqlite. Un database leggerissimo scritto in C che adopera il file system. Sul sito puoi scaricare anche la versione composta da un unico file che puoi includere direttamente nel tuo applicativo. Poi potresti creartri una classe C++ per interfacciarti allo stesso usando le API di sqlite.

lo sto utilizzando per un mio software(ino) e confermo quanto sia spettacolare. Hai un comune file e buona parte delle funzionalità del linguaggio sql.

Una vera manna dal cielo.

Gio

P.S.
Se vuoi continuare senza db mi unisco al coro che suggerisce gli alberi (IMHO bst o red-black [2,3,4] )
Avatar utente
Blizzard
Master
Master
 
Messaggi: 1509
Iscritto il: mar gen 02, 2007 22:53
Nome Cognome: Giovanni Santostefano
Slackware: 12.2
Kernel: 2.6.27.7-smp
Desktop: Fluxbox

Re: Classe Vector in C++

Messaggioda ccts2002 » mar nov 25, 2008 16:46

ksniffer ha scritto:Potresti provare sqlite. Un database leggerissimo scritto in C che adopera il file system. Sul sito puoi scaricare anche la versione composta da un unico file che puoi includere direttamente nel tuo applicativo. Poi potresti creartri una classe C++ per interfacciarti allo stesso usando le API di sqlite.


darò un occhiata...la possibilità di includere un database può sempre tornare utile... :D
Avatar utente
ccts2002
Linux 2.0
Linux 2.0
 
Messaggi: 155
Iscritto il: gio nov 09, 2006 23:20
Località: milano - trieste - catania


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Google [Bot] e 3 ospiti