===== Úkol 5 ===== Tento úkol navazuje na [[courses:a7b36pjc:ukoly:ukol_4|předchozí domácí úkol]], kde jste převedli spojový seznam jakožto strukturu, na spojový seznam jakožto třídu a přidali další užitečné metody. V tomto úkolu rozšíříte svůj list o další funkcionalitu, jmenovitě * iterátory * kopírující a přesouvající operace * ''list::swap'' -- Prohodí obsah obou listů * ''list::split'' -- Destruktivně rozdělí list kolem specifikovaného prvku * ''list::sort'' -- Seřadí list * porovnávací operátory: ''=='', ''!='', ''<'', ''%%<=%%'', ''>'', ''>='' Potřebné hlavičkové soubory a testy jsou ke stažení {{:courses:a7b36pjc:ukoly:small5.zip|zde}}. ==== Co odevzdat? ==== Jeden nebo více ''.cpp'' souborů, které implementují funkce deklarované v souboru ''list.hpp'' tak, aby testy procházely a neztrácela se paměť. Při práci na úkolu soubor ''list.hpp'' neměňte a nemusíte ho ani odevzdávat. ===== Rady ===== Pozor, tento úkol má deadline až v 8. týdnu a zatím jsme na cvičení neprocvičili všechny znalosti, které budete potřebovat. Nic vám ale nebrání začít napřed, ať už přímo s implementací, nebo jenom s promýšlením funkcionality. ==== Sort ==== Jako sort doporučujeme [[https://cs.wikipedia.org/wiki/Merge_sort|Merge sort]]. Pro spojové seznamy je velmi vhodný, protože umožňuje seřadit celý list bez přesouvání prvků samotných, a nepotřebuje mnoho extra paměti. Preferujeme pokud naimplementujete [[https://cs.wikipedia.org/wiki/Stabiln%C3%AD_%C5%99azen%C3%AD|stabilní řazení]], ale v této úloze to netestujeme. Testujeme pouze zda máte rozumnou asymptotickou složitost. ==== Pořadí implementace ==== Pokud chytře zvolíte pořadí implementace nové funkcionality, značně si zjednodušíte práci. Nějakou představu o vhodném pořadí byste měli mít ze 7. cvičení, doplníme pouze, že si můžete v některých případech zjednodušit práci i za pomoci iterátorů. ==== Definice metod vnořených tříd ==== Metody vnořených tříd (například ''list::iterator'') se definují stejně jako metody tříd, ale je potřeba si uvědomit, že k jejich plné identifikaci je potřeba zmínit i (všechny) vnější třídy. K této definici class list { class iterator { iterator& operator--(); }; }; tedy patří tato deklarace list::iterator& list::iterator::operator--() { ... } ==== Operátor přetypování ==== Specifikace ''list::iterator'' obsahuje i operátor přetypování, tj ''operator const_iterator() const''. V definici je potřeba plně specifikovat všechny typy, takže ve výsledku k němu patří tato definice list::iterator::operator list::const_iterator() const { ... } ==== Obousměrné iterátory ==== Nezapomeňte, že iterátory listu jsou tzv. ''BiDirectional'' a tudíž musí být možné iterátor přesunout zpátky k předchozímu prvku. Toto platí i pro iterátor vzniklý voláním funkce ''list::end''. ==== Časově náročné testy ==== Mezi testy je i jeden časově náročný test, který je při normálním spuštění vypnutý. Pokud ho chcete spustit, musíte zavolat výslednou binárku s argumentem ''[.long]'': ''small5 [.long]'' Silně doporučujeme ho spouštět pouze v optimalizované binárce, tj. stavět v //Release// módu nebo na příkazové řádce s parametrem ''-O3''. ==== Užitečné hlavičky ==== Implementaci relačních operací si můžete zjednodušit chytrým využitím hlavičky [[http://en.cppreference.com/w/cpp/header/algorithm|]].