reverse(ForwardIterator, ForwardIterator)

 ( gabor2 | 2012. augusztus 15., szerda - 10:39 )

A Standard Library a reverse fuggvenyt csak BidirectionalIterator es RandomAccessIterator -ra tartalmazza. Van-e valakinek otlete, hogyan lehet megoldani a feladatot ForwardIterator-okra minnel gyorsabban.
En egy nem tul szep rekurziv megoldast talaltam ~2N muveletigennyel.


template<class ForwardIterator>
void reverse(ForwardIterator first,ForwardIterator last);

Tehat a feladat : helyben forditas, Forward bejarokkal. Nem hazi. :)

gabor

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ő.

Kódot nem tudok, de algoritmikusan a reverse iterátor létrehozásakor be kell járnod az egész forward iterátort, el kell tenni mindent egy listába, és onnan olvasni visszafele, ha lép a reverse iterátor.

--
joco voltam szevasz

Szerintem itt nem tudsz hasznalni reverse iterator-t.

STL-hez nem értek, C#-ból indultam ki. Ott az iterálás egy interfésszel megy (IEnumerable), vagyis az iterátor egy osztály példány. Ennek a konstruktorában lehet felépíteni a teljes listát, aztán a MoveNext metódusban visszafele lépegetni.

De nem is kell osztályt csinálni, elég egy segédfüggvény, ami beolvas egy iterátort egy listába, és visszaadja annak a reverse iterátorát.

--
joco voltam szevasz

Egy forward iteratornak nincs reverse iterator-ra. Hogyha csinalsz egy listat akkor mar nem helyben forditas. Persze ugy lehetne.

Na de hogy tudsz helyben megfordítani valamit, aminek nem is tudod, hol a vége? Így lehetetlent kérsz. Írhatok egy iterátort, ami random mennyiségű X betűt állít elő, muszáj végigolvasnod, hogy meg tudd fordítani. Ha egy iterátor csak egyirányú, akkor jó esetben okkal az.

--
joco voltam szevasz

Gondolj egy sima egyiranyu lancolt listara, de ugy hogy nem ismered a szerkezetet. Tehat altalanosan kell megoldanod azzal a felulettel amit az ForwardIterator-on keresztul elersz.

Csakhogy egy adatszerkezet lehet vegtelen is, es letezhet hozza ForwardIterator. (Mint az emlitett egyiranyu lancolt lista, ahol az utolso elem nem NULL-ra mutat, hanem a lista valamely masik elemere)

A helyes valasz, hogy altalanos esetben a ForwardIterator-t nem lehet megforditani. A "helyben" valo megforditashoz meg a vegessegen kivul kell egy random access mutator is (ami pl. read only adatszerkezeteknel nincsen).


Nem hazi. :)

Attól még elég hülye feladat :)

Szia,
Egy hülye kérdés: Mennyire kell helyben? Egy ideiglenes listát nem tudsz generálni, és oda felépíteni a fordított sorrendet? (lista alatt az Iteratorral bejárt objektumra gondolok....)
Mert akkor könnyít, ha elkezded az első elem _elé_ beszúrni a többi elemet, félig kártyarendezésként megoldva :)
Utána pedig visszapakolhatod természetesen az eredeti listába...
Ennél gyorsabb sajnos nincs, és per pill a végig járogatáson túl nem látok "gyorsabbat"...

Üdv,
LuiseX

Altalanos stl jellegu algoritmusrol van szo. Tehat low-level szinten. Nem hasznalhatsz tarolokat, iteratorokkal dolgozol es azok alapmuveleteivel, ++, *, =.

Szia,
Akkor sajnos nem tudok rá optimálisat, sajnos az iterátor műveletek eléggé szegényesek... Esetleg egy "kiherélt egyszerű cserés rendezés" szerűséget lehet, de az sem a legjobb...
Amire gondolok, az az, hogy végig lépkedsz az első, és utolsó elem között, második, és utolsó előttit tárolod, majd felcseréled az érintett két elemet, és kijelölöd elsőnek, illetve utolsónak a két korábban tárolt elemet...
Ugyanezt játszod végig, amíg "középre nem érsz"... Ebből ha jól gondolom elsőre két lehetőséged van: a két iterátor megegyezik --> páratlan számosságú elemhalmazod volt, illetve ha az első elem utáni pont az utolsó elem... Ekkor természetesen még cserélni kell, de fontos, hogy ezt a végpontot is figyeld (sajnos könnyen lehet reverse-elni az eddigi munkát, ha nem veszed számításba, és egy bájos exception fog megállítani legfeljebb :D :D )
Így kapásból erre tudok még gondolni, de itt is "alkalmazol tárolót"...
Am. ha perverziód a rekurzió, ez az algoritmus úgyis könnyen implementálható, de ciklusban is, amelyik szimpatikusabb :)
Üdv,
LuiseX

En 2 megoldast talaltam a feladatra.
Az egyik ami O(n*n) es alul a kollega is leirt, hogy mindig ellepkedunk az n, n-1 ... elemekre es kicsereljuk az 1, 2, ... elemekkel.

A masik 2n-es, de stack gyilkos :

template<class Iterator>
bool Reverse_helper_forward(Iterator &first,Iterator last,Iterator end)
    {
    if (++last==end) return true;

    if (Reverse_helper_forward(first,last,end))
       {
       if (first==last) return false;
       std::iter_swap(first,last);
       if (++first!=last) return true;
       }

    return false;
    }

template<class Iterator>
void Reverse(Iterator first,Iterator last)
    {
    if (first==last) return;

    Reverse_helper_forward(first,first,last);
    }

De akkor valsz a 2 kozott nincs atmenet. :)

Szia,
Végig gondoltam a második megoldásod, és, hogy őszinte legyek, nagyon szép... Legalábbis nekem tetszik :)
Bár tény, tényleg stack gyilkos :D
Üdv,
LuiseX

Köszönöm.
Egyébbként Prolog az egész világ. :)