Functii librarie: Vectori

[•moon]

Care este cea mai eficienta metoda de stergere a unei valori dintr-un vector ?
Exemplu: Pentru vectorul cu valori v[5] = {1,2,3,4,5}, sa se stearga valoarea lui v[3], aceasta fiind in schimb inlocuita de cea a lui v[4] (analog pentru v[4] si v[5] daca vectorul ar fi fost mai mare)

[•R.A.R]

Poti avea elementele intr-o lista simplu inlantuita.Operatia de stergere se va face in O(1).

[•Mishu91]

Ştergerea elementului se face în O(1), dar accesarea lui se face in O(N), deci nu ai rezolvat nimic. Dacă nu ai nevoie de ordinea elementelor în vector, poţi ţine un set (şi poţi face ştergerea, inserarea, accesarea în O(logN) ) sau mai bine un unordered_set(unde operaţiile se fac în O(1) amortizat).

[•moon]

Tocmai asta e...elementele trebuie sa fie asezate in ordine.
Mie mi se da un vector, iar eu trebuie sa sterg si sa mut anumite elemente din vector in capat, pe baza unor anumite conditii.
Singura solutie relativ eficienta la care m-am gandit ar fi sa maresc permanent numarul de elemente din cadrul vectorului, sa copiez elementele , dupa caz, in pozitiile superioare nou create, iar cele initiale sa primeasca valoare 0 sau NULL, ajungand apoi sa fie ignorate total de catre program.
Daca lucrez insa asa, voi ajuge sa am extrem de multa memorie risipita...

[•crushack]

 Salut , problema e cumva : "Danduse un vector sa se ordoneze crescator facand mutari de genu : muta elementul de pe pozitia x in spatele vectorului " ? ca atunci n-ai nevoie de insert si delete in vector

[•scipianus]

Care este cea mai eficienta metoda de stergere a unei valori dintr-un vector ?
Exemplu: Pentru vectorul cu valori v[5] = {1,2,3,4,5}, sa se stearga valoarea lui v[3], aceasta fiind in schimb inlocuita de cea a lui v[4] (analog pentru v[4] si v[5] daca vectorul ar fi fost mai mare)

Daca doresti sa ai elementele in vector inca in ordine si doar sa elimini din vector toate valorile x ,intr-o singura parcurgere a vectorului,atunci faci urmatorul algoritm:
1.ai initial k=0
2.parcurgi vectorul
3.daca v[ i ]==x atunci k++
4.daca v[ i ]!=x atunci v[ i - k ]=v[ i ]
5.la final dupa parcurgere,inainte de a face afisarea sau altceva,faci n=n-k

adica in cod ar fi asa:

Cod:

k=0;
for(i=1;i<=n;i++)
{
	if(v[i]==x)
		k++;
	else
		v[i-k]=v[i];
}
n=n-k;

[•PlayLikeNeverB4]

a[] sau v[] ? Hotaraste-te  

Edit: Normal ca mi-am dat seama, doar voiam sa clarific
Acum ai editat si voi cadea de fraier 

[•scipianus]

a[] sau v[] ? Hotaraste-te  

Vectorul v[],ca am scris mai in graba si am mai si dat copy-paste din codul meu,oricum iti dadeai si singur seama de asta   Am modificat acum postul cu v[]