Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

stl vector

[es] :: C/C++ programiranje :: stl vector

Strane: 1 2

[ Pregleda: 6815 | Odgovora: 25 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
*.ptt.yu



+64 Profil

icon stl vector02.12.2003. u 09:06 - pre 247 meseci
recimo da imamo
vector<klasa> v;

i u nekoj petlji moguce izbacivanje clanova niza (btw da li to moze ne neki drugi nacin?)
Code:

vector<klasa>::iterator it = v.begin();
for (int i=0; i<v.size(); ++i) {
if (v[i] zadovoljava neki uslov) {
v.erase(it);
continue;
}
++it;
}


da li je ovo ok? ovako nesto vec radi, ali me interesuje da li je sve ok?
brine me ovo oko indexiranja
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: stl vector02.12.2003. u 09:13 - pre 247 meseci
Citat:
darkosos:
i u nekoj petlji moguce izbacivanje clanova niza (btw da li to moze ne neki drugi nacin?)


Algoritam remove_if()?

Code:
 
 template<typename _ForwardIter, typename _Predicate>
    _ForwardIter
    remove_if(_ForwardIter __first, _ForwardIter __last,
              _Predicate __pred)


f
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
*.ptt.yu



+64 Profil

icon Re: stl vector02.12.2003. u 14:40 - pre 247 meseci
wow, ovo je suvise napredno za mene;
ali resio sam ono na drugi nacin i mislim da je sada sve ok.
ostaje ipak jedno pitanje : da li prevodilac uradi to tako da svaki put racuna v.size(), sto bi bilo suvisno u vecini slucajeva ili pri svakoj proveri i<v.size() racuna desnu stranu, sto bi ponekad bilo zgodno?
 
Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521


Profil

icon Re: stl vector02.12.2003. u 15:24 - pre 247 meseci
Ovo da li racuna svaki put zavisi od toga kako kompajler otimizuje kod. U idealnoj situaciji, ako je size() const, kompajler bi mogao da isprati const correctness i da vidi da nema potrebe da size racuna svaki put.

Iskreno, nisam proveravao da li i kada koji kompajler to radi - ja obicno uvedem privremenu promenljivu u koju upisem size - ako mi je to bitno, naravno.
Npr. kod std::list u SGI implementaciji, koja je najcesca, size ima slozenost umesto . E sad, ako bi kompajlier svaki put racunao size, for petlja bi se pretvorila u dve i umesto dobio bi bez preke potrebe.

Kod std::vector izadje (skoro) na isto, posto je size() vrlo kratak, ali opet zavisi od optimizacije.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: stl vector02.12.2003. u 15:45 - pre 247 meseci
Zgodan priručni tekst za sve koji ne mogu da izbegnu :) korišćenje STL-a: http://www.cs.utexas.edu/users/lavender/courses/stl/stl.pdf . Prema referentnoj implementaciji size() metoda je konstantne složenosti (pogledajte gornji dokument), dakle sme se koristiti kao da je O(1). Kako je to ista složenost kao kada je u pitanju eksplicitna memoizacija, optimizovanje je nepotrebno. Ako imaš problema sa lošijim implementacijama STL-a, kao što je, može biti ova o kojoj sspasic govori, onda promeniš STL. :)

f
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: stl vector02.12.2003. u 16:20 - pre 247 meseci
Po C++ standardu, size() mora da je O(1). Međutim, to što je svuda O(1) ne znači da je svuda podjednako brza - zavisi od konstante.

@filmil: Deluje čudno na prvi pogled, ali remove_if() uopšte ne briše elemente, već ih samo preuredi tako da ih lako obrišeš posle sa erase().
 
Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521


Profil

icon Re: stl vector02.12.2003. u 17:16 - pre 247 meseci
Citat:
Dragi Tata:
Po C++ standardu, size() mora da je O(1). Međutim, to što je svuda O(1) ne znači da je svuda podjednako brza - zavisi od konstante.


Nisam siguran da je ovo tacno za sve kontejnere. Ja sam naveo primer za std::list.
Za std::vector mislim da ste u pravu. Gde to standard kaze?

Kod SGI implementacije pise ovo:
Citat:

Returns the size of the list. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the list. If you wish to test whether a list is empty, you should write L.empty() rather than L.size() == 0.

na linku http://www.sgi.com/tech/stl/List.html, a koliko mi je poznato ovu implementaciju (uz razne modifikacije) koriste skoro svi kompajleri, kao i stlport koji vazi za veoma dobru implementaciju.

Upravo proverih u stlport 4.5.3 i tu je definitivno O(n).

Moguce je da imam stare informacije ili da je SGI STL, odnosno stlport neusaglasen sa standardom.
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: stl vector02.12.2003. u 17:44 - pre 247 meseci
Mislio sam na vector::size(), naravno.

list::size() je po prirodi stvari O(n).

Izvinjavam se na nepreciznosti.
 
Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521


Profil

icon Re: stl vector02.12.2003. u 17:55 - pre 247 meseci
Inace, proverih jos malo std::list. Dakle:
Visual C++ 6.0 - O(1)
Visual C++ 7.0 - O(1)
GCC 3.2 - O(n)

U standardu (doduse kopiji s buvljaka ;) pise 'should', dakle trebalo bi da je O(1) ali nije obavezno. Zavisno od kontejnera i implementacije.


 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: stl vector02.12.2003. u 19:03 - pre 247 meseci
Tja, opet pričam napamet. Uglavnom, sad sam pogledao po knjigama i evo šta kaže "STL Pocket Reference" (taze knjiga, izašla u oktobru):

Citat:

The size function can have constant or linear complexity. The standard encourages library vendors to implement tha list class template so that size has constant complexity, but it permits worse performance (namely, linear in the size of the list).


Uglavnom, sve zavisi da li konkretna implementacija liste čuva podatak o broju članova u posebnoj promenljivoj ili ga broji pri svakom pozivu size().
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: stl vector02.12.2003. u 19:31 - pre 247 meseci
I da ne bude opet zabune, ceo prethodni post se odnosi na std::list
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
*.ptt.yu



+64 Profil

icon Re: stl vector02.12.2003. u 21:52 - pre 247 meseci
Ovo je malo otislo u drugu stranu, ali mislim da je interesantno ono pitanje u vezi for petlje i uslova koji moze biti promenljiv.
A evo i kako sam resio ono, ako nekom zatreba. Mislim da je dobro, ali nek' i drugi potvrde... :
Code:

vector<klasa> v;
vector<klasa>::iterator it = v.begin();

while(it<v.end()) {
if ((*it) zadovoljava neki uslov) {
it = v.erase(it); // nasao sam da erase(...) vraca prvi sledeci iterator posle izbrisanog
continue;
}
++it;
}
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: stl vector02.12.2003. u 22:43 - pre 247 meseci
Ipak je lakše ovako (pišem napamet, pa možda ima grešaka u sintaksi):

Code:


vector<klasa>::iterator kraj = remove_if(v.begin(), v.end(), Uslov);
v.erase(kraj, v.end());



Uslov je npr:

Code:

bool Uslov(const klasa& obj)
{
if (obj.nesto())
  return true;
return false;
}

 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
*.ptt.yu



+64 Profil

icon Re: stl vector02.12.2003. u 23:19 - pre 247 meseci
Mmmm, to je verovatno hteo i filmil da kaze ali nisam odma' razumeo.
Fala. A sta si ono pricao da ovaj samo priprema niz?
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: stl vector02.12.2003. u 23:26 - pre 247 meseci
Citat:
darkosos:
A sta si ono pricao da ovaj samo priprema niz?


remove_if() samo prepakuje niz tako da se svi elementi za brisanje nalaze posle iteratora koji vrati ova funkcija. Zato sam u gornjem primeru odmah posle remove_if() pozvao erase() koja je stvarno makla te "suvišne" elemente.
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
*.ptt.yu



+64 Profil

icon Re: stl vector02.12.2003. u 23:33 - pre 247 meseci
Do yaya. Danke onoliko!
btw koliko "kosta" (vremena) ovakva opercija?
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: stl vector03.12.2003. u 16:52 - pre 247 meseci
remove_if() je linearna operacija, a isto tako i erase().
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
*.ptt.yu



+64 Profil

icon Re: stl vector05.12.2003. u 10:35 - pre 247 meseci
e ovaj, opet ja :)
nikako da neteram taj remove_if da radi;
hocu reci, ne znam kako se pravi predikat...
situacija je sledeca :
Code:

struct A
{
...
bool F();
};

vector<A> v;

e sad zelim da mi ta funkcija F bude uslov za remove!
probao sam da napravim predikat pomocu mem_fun_t i slicno, ali ne ide...
najbolje sto sam uspeo da uradim je
fatal error C1001: INTERNAL COMPILER ERROR :)
 
Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521


Profil

icon Re: stl vector05.12.2003. u 10:39 - pre 247 meseci
Citat:
darkosos:
Code:

struct A
{
...
bool F();
};

e sad zelim da mi ta funkcija F bude uslov za remove!


Code:

struct A
{
...
bool operator()(const klasa &) const;
};

 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
*.ptt.yu



+64 Profil

icon Re: stl vector05.12.2003. u 13:57 - pre 247 meseci
Hm, da, veoma sažeto :)
Ali nisam savatao poruku?
Mada jeste on tamo pominjao neki operator() ali zar ne može da se koristi remove_if a da ne moram da "prilagođavam" ili "pripremam" strukturu?
 
Odgovor na temu

[es] :: C/C++ programiranje :: stl vector

Strane: 1 2

[ Pregleda: 6815 | Odgovora: 25 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.