reverse(ForwardIterator, ForwardIterator)

C/C++

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

  • 5788 megtekintés

( joco01 v | 2012. 08. 15., sze – 10:54 )

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

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

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

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

( Zsugabubus | 2012. 08. 15., sze – 12:35 )


Nem hazi. :)

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

( luisex v | 2012. 08. 15., sze – 12:53 )

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

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

( gabor2 | 2012. 08. 16., cs – 09:48 )

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