stl vector | [es]

stl vector 02.12.2003. u 09:06 · pre 278 meseci #1

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

Re: stl vector 02.12.2003. u 09:13 · pre 278 meseci #2

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

Re: stl vector 02.12.2003. u 14:40 · pre 278 meseci #3

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?

Re: stl vector 02.12.2003. u 15:24 · pre 278 meseci #4

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 $O(n)$ umesto $O(1)$ . E sad, ako bi kompajlier svaki put racunao size, for petlja bi se pretvorila u dve i umesto $O(n)$ dobio bi $O(n^2)$ bez preke potrebe.

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

Re: stl vector 02.12.2003. u 15:45 · pre 278 meseci #5

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

Re: stl vector 02.12.2003. u 16:20 · pre 278 meseci #6

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().

Potpis

IOCC

Re: stl vector 02.12.2003. u 17:16 · pre 278 meseci #7

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.

Re: stl vector 02.12.2003. u 17:44 · pre 278 meseci #8

Mislio sam na vector::size(), naravno.

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

Izvinjavam se na nepreciznosti.

Potpis

IOCC

Re: stl vector 02.12.2003. u 17:55 · pre 278 meseci #9

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.

Re: stl vector 02.12.2003. u 19:03 · pre 278 meseci #10

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().

Potpis

IOCC

Re: stl vector 02.12.2003. u 19:31 · pre 278 meseci #11

I da ne bude opet zabune, ceo prethodni post se odnosi na std::list

Potpis

IOCC

Re: stl vector 02.12.2003. u 21:52 · pre 278 meseci #12

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;
}

Re: stl vector 02.12.2003. u 22:43 · pre 278 meseci #13

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;
}

Potpis

IOCC

Re: stl vector 02.12.2003. u 23:19 · pre 278 meseci #14

Mmmm, to je verovatno hteo i filmil da kaze ali nisam odma' razumeo.
Fala. A sta si ono pricao da ovaj samo priprema niz?

Re: stl vector 02.12.2003. u 23:26 · pre 278 meseci #15

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.

Potpis

IOCC

Re: stl vector 02.12.2003. u 23:33 · pre 278 meseci #16

Do yaya. Danke onoliko!
btw koliko "kosta" (vremena) ovakva opercija?

Re: stl vector 03.12.2003. u 16:52 · pre 278 meseci #17

remove_if() je linearna operacija, a isto tako i erase().

Potpis

IOCC

Re: stl vector 05.12.2003. u 10:35 · pre 278 meseci #18

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 :)

Re: stl vector 05.12.2003. u 10:39 · pre 278 meseci #19

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;
};

Re: stl vector 05.12.2003. u 13:57 · pre 278 meseci #20

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?

Srodne teme