STL - Vector i realokacija

[ ljube @ 02.03.2007. 20:46 ] @

Imam par nedoumica o vector klasi. Potrebno mi je za projekat da koristim strukuture tipa array koje mogu lako da koriste dodavanje i brisanje članova.
Na prvi pogled upotreba vector-a bi mi odgovarala ali nisam siguran sta se desava sa memorijom kada program pređe inicijalno rezervisani prostor.

Primjer:
vector<HWND> selectedObjects;
selectedObjects.reserve(10);

Šta će se desiti ako imam potrebu da ubacim 20 članova sa push_back a prethodno sam rezervisao 10.
Da li će realokacija invalidirati postojeće članove u vektoru?
Meni je potrebno da vektor automatski raste (u ovom primjeru 10 članova) ali da pri tome ne invalidira postojeće članove u nizu.
Ukoliko realokacija briše(invalidira) postojeće članove, da li možete da mi preporučite neko drugo rješenje koje može slobodno da se proširuje bez birsanja postojeće strukture.

Pozdrav,
Ljubiša

[ cynique @ 02.03.2007. 21:04 ] @

Dodavanje novog člana vektoru može realocirati sav (čak i ako dodaješ samo jedan član na kraj) storage koji je prethodno zauzimao (vektor je optimiziran za brz slučajan pristup pa je memorija kontinuirano alocirana), te tako invalidirati sve iteratore koji pokazuju na neki od njegovih elemenata.

Mislim da tražiš listu (std::list).

[ Dragi Tata @ 02.03.2007. 21:18 ] @

Ako sam razumeo tvoje zahteve, vector je upravo ono što tražiš.

Ukratko, neće ništa da im fali. Realokacija vektora je uprošćeno rečeno:

1) rezerviše se novi memorijski prostor za vektor
2) iskopiraju se elementi iz starog u novi
3) dealocira se stari memorijski prostor.

Znači, sve dok članovi niza imaju normalnu semantiku kopiranja, sve je OK.

Ono što cynique priča se tiče iteratora. Tj, ako imaš iterator na neki član niza pa uradiš push_back, taj iterator postaje invalidan.

Ako razumeš kako radi realloc u C-u, ovo je veoma slično.

[ ljube @ 02.03.2007. 21:39 ] @

Mnogo hvala na brzim odgovorima!

Pristup vektoru nije preko itratora tako da bi ovo trebalo da bude u redu.
Ipak ću pročitati i o std::list, možda mi je prikladnija za ovaj projekat.

Pozdrav,
Ljubiša

[ tosa @ 03.03.2007. 05:01 ] @

Ukoliko ti nije potrebno da ubacuješ članove na određeno mesto, vektor je mnogo bolje
rešenje. Dodavanje u listu zahteva alokaciju svaki put, kod vektora to nije slučaj.
Doduše, možeš uvek da napišeš i svoj alokator, mada verovatno nemaš potrebe za tim...

[ ljube @ 03.03.2007. 07:51 ] @

U ovom slucaju, članovi se dodaju na kraj sa push_back ali imam potrebu da ih brišem sa određenih lokacija.

petlja...
if (selectedObjects.at(x) = hWndParam) {
selectedObjects.erase(selectedObjects.begin()+x);
break;
}
...

Obzirom na logiku programa, mislim da ce vector biti dobar. Jedino me je brinula realokacija a ako sam dobro razumio poruku od "Dragi Tata", realokacija ne bi trebala da me brine jer su članovi sačuvani tokom proširivanja vektora.

Pozdrav,
Ljube

[ cynique @ 03.03.2007. 18:02 ] @

Citat:

ljube: U ovom slucaju, članovi se dodaju na kraj sa push_back ali imam potrebu da ih brišem sa određenih lokacija.

Što će u slučaju vektora, potencijalno opet realocirati CIJELI kontejner, dok se u slučaju liste tako nešto ne bi dogodilo :)

Nijedan standardni kontejner neće "invalidirati" same podatke - bilo bi idiotski kad bi se dodavanjem novog elementa stari jednostavno izgubili :) Kad pitaš "hoće li invalidirati elemente", prirodno je pretpostaviti da misliš na njihovu lokaciju u memoriji...

BTW, u svom kodu mjesto dva znaka == imaš samo jedan. Također se nadam da u iterirajućoj petlji nemaš fiksno spremljenu selectedObjects::size, jer se nakon brisanja veličina mijenja, pa buš dobio indeksiranje izvan granica... :) Ako budeš prepisivao preko iteratora, pazi da izostaviš iter++ nakon brisanja :)

[ ljube @ 03.03.2007. 20:55 ] @

Uh, sada sam potpuno zbunjen.

Očekivao sam da se selectedObjects.size() automatski ažurira poslje brisanja i da ima vrijednost manje jedan.

Ovo je kompletan kod funkcije koja uklanja članove koji mi više nisu potrebni:

BOOL RemoveFncElement (HWND valeEl)
{
if(!IsWindow(valeEl))
{
return FALSE;
}
int x = 0;
for(x=0; x<=selectedObjects.size()-1; x+=1)
{
if(selectedObjects.at(x)==valeEl)
{
selectedObjects.erase(selectedObjects.begin()+x);
return TRUE;
}
}
return FALSE;
}

Poslje, opet u kodu koristim provjeru selectedObjects.size() ali sam očekivao da ona nako brisanja vraća tačno onoliko koliko ih i ima nakon brisanja.

To: cynique
Šta si mislio pod: "Također se nadam da u iterirajućoj petlji nemaš fiksno spremljenu selectedObjects::size, jer se nakon brisanja veličina mijenja, pa buš dobio indeksiranje izvan granica... :)"?

Pozdrav,
Ljubiša

[ kiklop74 @ 04.03.2007. 00:25 ] @

Ne radi se brisanje tako. Ovo je kod u duhu standardne biblioteke koji provereno radi:

Code:
BOOL RemoveFncElement (std::vector<HWND> &selectedObjects, HWND valeEl)
{
  BOOL result = IsWindow(valeEl);
  if(result) {
    std::vector<HWND>::iterator itEnd = selectedObjects.end();
    std::vector<HWND>::iterator iter = std::find( selectedObjects.begin(),
                                                 itEnd,
                                                 valeEl );

    result = (iter != itEnd);
    if (result) {
     selectedObjects.erase(iter);
    }
  }
  return result;
}

Ovako je bolje jer je vektor nad kojim se vrši operacija sada ulazni parametar funkcije te tako ne zavisi od nikakve globalne magične promenjive. Pozivaš ga sa:

Code:
RemoveFncElement(mojvector,<hwnd>)

[ DjoleReject @ 04.03.2007. 01:03 ] @

Citat:

ljube: Mnogo hvala na brzim odgovorima!

Pristup vektoru nije preko itratora tako da bi ovo trebalo da bude u redu.
Ipak ću pročitati i o std::list, možda mi je prikladnija za ovaj projekat.

Pozdrav,
Ljubiša

Pristup vektoru itekako jeste preko iteratora. Ne znam kako si dosao do ovoga?

[ Dragi Tata @ 04.03.2007. 01:44 ] @

Citat:

ljube: U ovom slucaju, članovi se dodaju na kraj sa push_back ali imam potrebu da ih brišem sa određenih lokacija.

Onda std::list. :)

[ tosa @ 04.03.2007. 04:55 ] @

Std::list ti garantuje skupe alokacije pri svakom ubacivanju/izbacivanju člana,
kod vektora to nije slučaj, posebno ako koristiš reserve metod.

@ljube
Nisam siguran da je tebi brzina presudan faktor, tako da slobodno koristi šta god ti se dopada :)

[ Dragi Tata @ 04.03.2007. 14:26 ] @

vector je efikasan samo ako se dodavanje i brisanje vrši na kraju. Ako namerava da briše elemente iz sredine ili početka, list je daleko efikasniji nego vector.

Inače što se tiče garantovano skupih alokacija, CRT je danas dovoljno pametan da "ukine" takve garancije.

[ ljube @ 04.03.2007. 14:39 ] @

Hvala svima na odgovorima. Izgleda da mi je pametnije da koristim list a i da malo više pročitam o STL.

Pozdrav,
Ljubiša

[ tosa @ 05.03.2007. 13:55 ] @

Citat:

Dragi Tata: vector je efikasan samo ako se dodavanje i brisanje vrši na kraju. Ako namerava da briše elemente iz sredine ili početka, list je daleko efikasniji nego vector.

Inače što se tiče garantovano skupih alokacija, CRT je danas dovoljno pametan da "ukine" takve garancije.

Može uvek da koristi std::swap pre brisanja elementa, da bi ga stavio na kraj vektora.
Nažalost, crt nije dovoljno pametan da pomogne u slučaju liste - bar ne na svim platformama.
Sve zavisi od potreba, situacije i pre svega kombinacije platforma/kompajler.

[ Dragi Tata @ 05.03.2007. 15:25 ] @

Citat:

tosa: Može uvek da koristi std::swap pre brisanja elementa, da bi ga stavio na kraj vektora.

Može ako mu semantika programa to dozvoljava.

Citat:

tosa:
Nažalost, crt nije dovoljno pametan da pomogne u slučaju liste - bar ne na svim platformama.
Sve zavisi od potreba, situacije i pre svega kombinacije platforma/kompajler.

Naravno, samo sam rekao da alokacija nije "garantovano" skupa.