stl vector

[ darkosos @ 02.12.2003. 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

[ filmil @ 02.12.2003. 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)

[ darkosos @ 02.12.2003. 14:40 ] @

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?

[ sspasic @ 02.12.2003. 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.

[ filmil @ 02.12.2003. 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

[ Dragi Tata @ 02.12.2003. 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().

[ sspasic @ 02.12.2003. 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.

[ Dragi Tata @ 02.12.2003. 17:44 ] @

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

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

Izvinjavam se na nepreciznosti.

[ sspasic @ 02.12.2003. 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.

[ Dragi Tata @ 02.12.2003. 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().

[ Dragi Tata @ 02.12.2003. 19:31 ] @

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

[ darkosos @ 02.12.2003. 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;
}

[ Dragi Tata @ 02.12.2003. 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;
}

[ darkosos @ 02.12.2003. 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?

[ Dragi Tata @ 02.12.2003. 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.

[ darkosos @ 02.12.2003. 23:33 ] @

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

[ Dragi Tata @ 03.12.2003. 16:52 ] @

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

[ darkosos @ 05.12.2003. 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 :)

[ sspasic @ 05.12.2003. 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;
};

[ darkosos @ 05.12.2003. 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?

[ sspasic @ 05.12.2003. 14:15 ] @

Ponekad moze.
Poenta je u tome da remove_if trazi predikat (http://www.sgi.com/tech/stl/Predicate.html) kome nekako mora da prosledi (referencu na) objekat za koji se proverava da li ga treba brisati ili ne i kao odgovor ocekuje bool vrednost.
Nacin na koji se zove predikat je:

Code:

if (predikat(objekat)) ...

pa operator() sluzi da bi predikat tako mogao da bude pozivan.

U odredjenim situacijama i klasicne C funkcije, staticki i ne-staticki metodi klasa mogu biti pozivani kao predikati, ali to zahteva da se funkcijama iz functional hedera, ili slicnim (npr. iz boost biblioteke) prilagode da postanu predikti. Pogledaj bind(1st, 2nd), mem_fn (odnosno mem_fun) i slicne funkcije.

[ darkosos @ 05.12.2003. 16:33 ] @

upravo pokusavajuci

Citat:

Pogledaj bind(1st, 2nd), mem_fn (odnosno mem_fun) i slicne funkcije.

sam i dobio onu gresku; dakle mogu samo da nabadam kako to treba da se uradi, ali ako neko zna odmak da kaze kako, ustedeo bik se nabadanja :)

Dakle, kako od bool funkcije, clanice neke strukture/klase da dobijem "predikat" koji mogu da prosledim u remove_if? Kako se koristi mem_fun?

[ sspasic @ 05.12.2003. 18:45 ] @

Evo jednog primera sa boost::bind i boost::mem_fn, na VC++ 6.0

Code:

#include <iostream>
#include <algorithm>
#include <vector>
#include <boost/bind.hpp>
#include <boost/mem_fn.hpp>

class klasa {
public:
    klasa(int val) : Val_(val) {}

    bool manje_od(int max) const { return Val_ < max; }

    int value() const { return Val_; }

private:
    int Val_;
};

void
napravi(std::vector<klasa> &v, int broj)
{
    for (int i = 0; i < broj; ++i) {
        v.push_back(i);
    }
}

void
ispisi(const std::vector<klasa> &v)
{
    for (std::vector<klasa>::const_iterator i = v.begin(); i != v.end(); ++i) {
        std::cout << i->value() << " ";
    }
    std::cout << std::endl;
}

int
main(int argc, char* argv[])
{
    std::vector<klasa> v;
    napravi(v, 10);

    // Obrisi elemente manje od 3
    std::vector<klasa>::iterator kraj = std::remove_if(v.begin(), v.end(),
                       boost::bind<bool>(boost::mem_fn(&klasa::manje_od), _1, 3));
    v.erase(kraj, v.end());

    ispisi(v);

    return 0;
}

[ darkosos @ 05.12.2003. 22:47 ] @

Veoma mi je žao, ali tako nešto kao boost nemam ni izdaleka!
U svakom slučaju hvala puno na trudu :)
Moraću to nekako drukčije da rešim...
Osim ako... da, mogao bi da mi mail-uješ (ili slično) te .h i .cpp fajlove!
Ili ako može nešto bez boost-a.

Evo, na primer, šta kompajler ne prihvata (prijavljuje grešku u algorithm fajlu) :

Code:

struct A {...; bool F();};
vector<A> v;
vector<A>::iterator last = remove_if(v.begin(), v.end(), mem_fun(&A::F));

[ sspasic @ 05.12.2003. 23:17 ] @

Boost mozes naci na www.boost.org.

Inace, evo listinga dopunjenog sa par primera koji ne koriste boost:

Code:

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <boost/bind.hpp>
#include <boost/mem_fn.hpp>

class klasa {
public:
    klasa(int val) : Val_(val) {}

    bool manje_od(int max) const { return Val_ < max; }

    int value() const { return Val_; }

    bool za_brisanje() { return Val_ < 4; }
    bool operator<(const klasa &o) const { return Val_ < o.Val_; }

private:
    int Val_;
};

void
napravi(std::vector<klasa> &v, int broj)
{
    for (int i = 0; i < broj; ++i) {
      v.push_back(i);
    }
}

void
ispisi(const std::vector<klasa> &v)
{
    for (std::vector<klasa>::const_iterator i = v.begin(); i != v.end(); ++i) {
      std::cout << i->value() << " ";
    }
    std::cout << std::endl;
}

class kriterijum {
public:
    kriterijum(int val) : Val_(val) {}

    bool operator()(const klasa &o) { return o.value() < Val_; }

private:
    int Val_;
};

int
main(int argc, char* argv[])
{
    std::vector<klasa> v;
    napravi(v, 10);

    // Obrisi elemente manje od 3
    std::vector<klasa>::iterator kraj = std::remove_if(v.begin(), v.end(),
      boost::bind<bool>(boost::mem_fn(&klasa::manje_od), _1, 3));
    v.erase(kraj, v.end());
    ispisi(v);

    kraj = std::remove_if(v.begin(), v.end(),
      std::mem_fun_ref(&klasa::za_brisanje));
    v.erase(kraj, v.end());
    ispisi(v);

    kraj = std::remove_if(v.begin(), v.end(), kriterijum(5));
    v.erase(kraj, v.end());
    ispisi(v);

    kraj = std::remove_if(v.begin(), v.end(),
         std::bind2nd(std::less<klasa>(), klasa(6)));
    v.erase(kraj, v.end());
    ispisi(v);

    return 0;
}

Iskreno, pomocu funkcija standardne biblioteke ne umem da napisem primer ekvivalentan onom koji koristi boost sa VC++ 6.0.

[ darkosos @ 05.12.2003. 23:21 ] @

Upravo mi je iskompajlirao verziju sa mem_fun_ref umesto mem_fun !
Jos da vidimo da li radi!