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

stl vector

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

Strane: 1 2

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

Postavi temu Odgovori

Autor
Pretraga teme: Traži
Markiranje Štampanje RSS

darkosos
Darko Šoš
Beograd

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



Profil

icon stl vector02.12.2003. u 09:06

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
02.12.2003. u 09:06 

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


Profil

icon Re: stl vector02.12.2003. u 09:13
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
02.12.2003. u 09:13 

darkosos
Darko Šoš
Beograd

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



Profil

icon Re: stl vector02.12.2003. u 14:40
Laptopovi

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?
02.12.2003. u 14:40 

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
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.
02.12.2003. u 15:24 

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


Profil

icon Re: stl vector02.12.2003. u 15:45
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
02.12.2003. u 15:45 

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



Profil

icon Re: stl vector02.12.2003. u 16:20
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().
IOCC
02.12.2003. u 16:20 

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
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.
02.12.2003. u 17:16 

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



Profil

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

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

Izvinjavam se na nepreciznosti.
IOCC
02.12.2003. u 17:44 

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
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.
02.12.2003. u 17:55 

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



Profil

icon Re: stl vector02.12.2003. u 19:03
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().
IOCC
02.12.2003. u 19:03 

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



Profil

icon Re: stl vector02.12.2003. u 19:31
I da ne bude opet zabune, ceo prethodni post se odnosi na std::list
IOCC
02.12.2003. u 19:31 

darkosos
Darko Šoš
Beograd

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



Profil

icon Re: stl vector02.12.2003. u 21:52
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;
}
02.12.2003. u 21:52 

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



Profil

icon Re: stl vector02.12.2003. u 22:43
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;
}
IOCC
02.12.2003. u 22:43 

darkosos
Darko Šoš
Beograd

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



Profil

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

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



Profil

icon Re: stl vector02.12.2003. u 23:26
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.
IOCC
02.12.2003. u 23:26 

darkosos
Darko Šoš
Beograd

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



Profil

icon Re: stl vector02.12.2003. u 23:33
Do yaya. Danke onoliko!
btw koliko "kosta" (vremena) ovakva opercija?
02.12.2003. u 23:33 

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



Profil

icon Re: stl vector03.12.2003. u 16:52
remove_if() je linearna operacija, a isto tako i erase().
IOCC
03.12.2003. u 16:52 

darkosos
Darko Šoš
Beograd

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



Profil

icon Re: stl vector05.12.2003. u 10:35
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 :)
05.12.2003. u 10:35 

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
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;
};
05.12.2003. u 10:39 

darkosos
Darko Šoš
Beograd

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



Profil

icon Re: stl vector05.12.2003. u 13:57
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?
05.12.2003. u 13:57 

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

Strane: 1 2

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

Postavi temu Odgovori

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