Tömb minden n. elemének kiíratása iterátorral, SZÉPEN

 ( parrot | 2010. január 14., csütörtök - 19:59 )

Sziasztok!

Ha van egy k elemű tömböm, és minden n. elemét szeretném kiíratni iterátorral, akkor hogyan lehet azt szépen megoldani?

Az alábbi megoldás nem jó, mert amikor az it a 12. elemre mutat akkor a 3-mal való megnövelése hibát okoz:

#include < vector>
#include < iostream>

int main(int argc, char * argv[])
{

std::vector < int > v;
for (int i = 0; i < 14; ++i)
{
v.push_back(i);
}

const int step = 3;

for (std::vector < int > ::iterator it = v.begin();
v.end() != it;
it += step)

{
std::cerr << *it << std::endl;
}

return 0;
}

Az alábbi megoldás működik ugyan, de (szerintem) nem túlságosan elegáns:

#include < vector>
#include < iostream>

int main(int argc, char * argv[])
{

std::vector < int > v;
for (int i = 0; i < 14; ++i)
{
v.push_back(i);
}

const int step = 3;

for (std::vector < int > ::iterator it = v.begin();
v.end() != it;
it = ((v.end() - step >= it) ? (it + step) : (v.end())))

{
std::cerr < < *it < < std::endl;
}

return 0;
}

Van erre bevett szép megoldás, vagy az iterátorok egyszerűen nem támogatják az ilyen használatot?

Szerk.: sorry, úgy látom a code elemek valamiért nem működnek, de azért remélem így is érthető a kódrészlet.

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

A random access iteratorokkal például meg lehet ezt csinálni:


for (std::vector<int>::iterator it = v.begin(); it < v.end(); it+=3) {
    std::cerr << *it << std::endl;
}

Ha már vektorod van, mért nem az operator[]-t használod?
Amúgy +1, it != v.end() helyett it < v.end() működik.

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Úgy tudom, hogy az iterator-ok használata ajánlott az indexek helyett..

Egyébként a programban, amit éppen fejlesztek (ez nem a fenti példa) ráadásul kényelmesebb is, mert az iterátor értéke egy másik tömböt címez, így szerintem áttekinthetőbb az hogy:

tömb1[*it]

mint az, hogy:

tömb1[tömb2[i]]

"iterator-ok használata ajánlott az indexek helyett"

per def a vektor elemei memóriafolytonosan helyezkednek el, és közvetlenül O(1) alatt elérhetőek. Vagyis a vektor nyugodtan használható [] operátorral. Ez a feladat pedig pont ilyenért kiált.

Felejtsétek el a it < v.end()-et mivel az csak RandomAccessIteratorral működik (azaz vectorral igen, de listtel nem).

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Természetesen, ez csak vektorra jó megoldás.

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Köszi, de sajna így is elszáll a program: 12-nél azt látja, hogy az iterátor még "kisebb", mint a tömb vége, végrehajtja a ciklus törzsét, majd amikor megpróbál 3-at hozzáadni ismét érvénytelen iterátorhoz jut.

Akkor it < v.end()-step

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Ha már RandomAccess:

for (int i=0;i<distance(v.begin(),v.end());i+=3)
   cout << v.begin()[i] << endl;

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

s/distance(v.begin(),v.end())/v.size()/

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Csak az úgy nem iterátor.
Amit én írtam az ez, csak nem akartam ennyit írni...

vector<int>::const_iterator b=v.begin();
vector<int>::const_iterator e=v.end();

for (int i=0;i<distance(b,e);i+=3)
   cout << b[i] << endl;

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Nem értem a különbséget, amire utalni próbálsz. Azon kívül, hogy a distance visszatérési értéke difference_type, ami egy előjeles egész, a size visszatérési értéke meg size_type, ami előjel nélküli egész, mindkettő a vektor elemeinek számát adja vissza.

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Az a különbség, hogy a ciklusban nem használom a vektort, csak a két random access iterátort.
Azaz a ciklus maga bármilyen két random access iterátorral működik, nem csak vektorral. Pl két mutatóval is ami egy tömb két végére mutat.
Vagy egy string két végére. Ettől lesz generikus.

(Ha felteszed, hogy vektort kapsz, akkor felesleges bohóckodni az iterátorokkal, indexeled a vektort és kész.)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

> Ha felteszed, hogy vektort kapsz, akkor felesleges bohóckodni az iterátorokkal, indexeled a vektort és kész.

Ez volt az első javaslatom. :))
Amúgy most már értem, hova akarsz kilyukadni.

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Azért ha az esetek másik 99%-ában a kapcsolt lista a jobb megoldás (sok beszúrás elejére és végére), akkor én ezt is azzal implementálnám le, egyszerűen azért, mert a memória áthelyezése költségesebb, mint ebben a kódban az a 8 plusz művelet.

Nyilván a fenti kódból a tároló egyéb használata most nem derül ki.
--
http://www.naszta.hu

Ha csak az elejére meg a végére akkor már mér nem dequeue?
----
Hülye pelikán

Azért szoktam láncolt listát használni, mert 5 perc múlva mindig kiderül, hogy azért néha középre is be kell szúrni és akkor a dequeue sem elég hatékony.

De még egyszer: ebben az esetben (is) elsősorban az a kérdés, hogy mi van az éles kódban. Ha ezt a függvény sokat kell hívogatni, akkor dequeue a jó megoldás, mert ez hatékony. Ha 1.000 futásból viszont csak egyszer van ez meghívva, akkor viszont láncolt lista a jobb, mert gyorsabb a végekre beillesztésnél és a végekről való törlésnél. Ha sokszor kell létrehozni és letörölni a tárolót, akkor már lehet, hogy dequeue gyorsabb (ha előre állítod a tároló méretet), mert az konstans idő alatt töröl vagy hoz létre tömböt, viszont ha egyesével növeled, akkor n*log(n) a növekedési sebessége (szemben a láncolt lista n-jével ) (n beszúrás esetén).

Ha sok adatot kell kezelni és sokat kell beszúrnod véletlen szerűen, akkor a dequeue-nél a beszúrás nem konstans idejű, míg a láncolt listánál az. Ha jól emlékszem valamivel több, mint log(n), mert mindig duplájára növeli az elemszámot a rövid oldalon és úgy másolja a teljes tartalmat a dequeue, ha kifut a tároló tömbből. Középre való beillesztésre meg kifejezetten lassú (talán n*log(n)).
--
http://www.naszta.hu

Alapvetően nem vitatkozok, mert nincs miről, nyílván a feladat választja az eszközt. De a lista alapból lassabb az indirekció miatt, és ha csak néha kell középre szúrni, akkor még simán lehet, hogy valamelyik nem-láncolt tároló jobban jön ki.

Ezt a mondatodat viszont nem értem: "... akkor viszont láncolt lista a jobb, mert gyorsabb a végekre beillesztésnél és a végekről való törlésnél."

Hogy is van ez? Jó eséllyel nem kerül sor allokációra, csak másolásra, míg listánál ugye.

Amúgy a dequeue implementációja nincs megkötve, nem kell duplájára növelnie (bár elhiszem, hogy minden általad és általam ismert implementáció így tesz).
----
Hülye pelikán

Ezt a mondatodat viszont nem értem: "... akkor viszont láncolt lista a jobb, mert gyorsabb a végekre beillesztésnél és a végekről való törlésnél."

Hogy is van ez? Jó eséllyel nem kerül sor allokációra, csak másolásra, míg listánál ugye.

Valóban allokációnál gyorsabb a dequeue, mert ott csak egy mutató változik.
--
http://www.naszta.hu