{{page>courses:b6b36pjc:styles#common&noheader&nofooter}} {{page>courses:b6b36pjc:styles#ukoly&noheader&nofooter}} ===== Domácí úkol: List ===== V tomto úkolu budete implementovat oboustranně spojený spojový seznam, viz [[https://en.wikipedia.org/wiki/Doubly_linked_list|Wikipedia]], ve stylu standardní knihovny. To znamená, že dostanete hlavičkový soubor definující třídu ''pjc::list'', včetně jejího rozhraní, a sadu testů, které ověří, zda vaše implementace funguje tak, jak má. Váš úkol pak bude naimplementovat jednotlivé metody třídy ''list'' tak, aby všechny testy prošly. Pro usnadnění implementace jsou testy rozděleny do 5 částí, které na sobě staví a z nichž každá testuje jinou část vaší implementace. Díky tomu můžete pracovat dle testů bez toho, aby se na vás vyvalily chyby, které zatím ani nemůžete opravit. ==== Zadání ==== Seznam metod, které musíte implementovat najdete v hlavičce ''list.hpp''. Co jednotlivé metody mají dělat pak najdete v téže hlavičce, ve formátu tzv. Doxygen komentářů((Speciálně formátované komentáře, ze kterých lze automaticky generatovat HTML dokumentaci)). Archiv s testy, hlavičkou ''list.hpp'' a ''CMakeLists.txt'' najdete {{:courses:b6b36pjc:ukoly:list.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. ==== Hodnocení ==== ^ **Sekce** ^ Body ^ | Basic functionality (stage1) | 2.5 | | Iterators (stage2) | 2.5 | | Copy, move, compare (stage3) | 2.5 | | Reverse | 1.0 | | Split | 1.5 | | Merge | 1.5 | | Sort | 1.0 | | Remove | 1.0 | | Split: algorithmic complexity | 0.5 | | Merge: algorithmic complexity | 0.5 | | Sort: algorithmic complexity | 0.5 | ==== Rady ==== Doporučujeme o listu přemýšlet a pohybovat se v něm podobně jako ve stromu, to jest rekurzivně. Prakticky to znamená, že by se člověk při průchodu listu neměl orientovat dle velikosti, ale dle struktury -- to že jsme v prvním uzlu se pozná tak, že platí ''prev == nullptr'' a naopak poslední uzel se pozná dle toho tak, že platí ''next == nullptr''. Ostatní uzly jsou prostě někde v listu a není důležité, kde přesně. Stejně tak vám doporučujeme vždy aktualizovat ukazatele prvků v listu, i v případě, že to není striktně potřeba. Například když smažete poslední uzel v listu, tak krom přesunutí ukazatele ''tail'' doporučujeme vynulovat i ukazatel ''next'' předposledního (nově posledního) uzlu listu. ==== Užitečné hlavičky ==== Implementaci si můžete zjednodušit vhodným použití funkcí z dvou hlaviček, [[https://en.cppreference.com/w/cpp/header/utility|]] a [[https://en.cppreference.com/w/cpp/header/algorithm|]]. ==== Implementační poznámky a rady ==== * Při operacích, které modifikují oba listy, silně doporučujeme pracovat přímo s uzly obou listů, ne pouze s prvky uloženými v nich. * Obvykle se očekává, že merge je [[https://cs.wikipedia.org/wiki/Stabiln%C3%AD_%C5%99azen%C3%AD|stabilní]], ale v tomto úkolu to není testováno. * V inicializačním seznamu (//initializer list//) lze zavolat jiný konstruktor třídy. * Funkcionalita v jednotlivých částech a jejich pořadí není náhodné. Pokud se vám některá funkcionalita zdá hrozně složitá, rozmyslete si, jestli si její implementaci nemůžete zjednodušit vhodným využitím již existující funkcionality((Některé případy jsou i na cvičení)). * Když je deklarace třídy v nějakém ''namespace'', musí v něm být i definice. * Pokud máte problém s komplexitou metody ''split'', zkontrolujte, zda nemáte stejný problém, jako je předveden na 6. cvičení v sekci [[courses:b6b36pjc:cviceni:cviceni-06#dalsi_priklady|další příklady]], konkrétně ''tracker_in_a_jar''. ==== 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. Vaše implementace by měla být tzv. [[https://cs.wikipedia.org/wiki/Stabiln%C3%AD_%C5%99azen%C3%AD|"stabilní"]], ale přímo v testech to nekontrolujeme, pouze testujeme, zda se asymptotická složitost vaší implementace jeví rozumná. ==== 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 deklaraci class list { class iterator { iterator& operator--(); }; }; tedy patří tato definice 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''. ==== Přístup ke smazané paměti ==== Dávejte si pozor na přístup ke smazané paměti, protože jakmile nějaký kus paměti uvolníte, už k němu nesmíte přistoupit. To znamená, že například při mazání listu je potřeba nejdříve přesunout hlavu, a až pak smazat první prvek. Malá ilustrace (node je celá struktura reprezentující uzel v listu a šipky jsou ukazatele): Začneme se správně zkonstruovaným listem, který má 4 prvky. head | | _____V__ ________ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <------------------------- Pokud smažeme uzel, na který ukazuje head, dostaneme se do tohoto stavu: head | | _____V__ ________ ________ ________ / nod/ | / node | / node | / node | |\--/-- | |------ | |------ | |------ | | \/lue | | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ |<-- | prev |<-- | prev |<-- | prev | | |-------- |-------- |-------- |-------- | nullptr <-------------------------- A z něho už nemůžeme pokračovat s mazáním, protože nemůžeme přistoupit k hodnotě ''head.next''. Správně musíme nejdříve posunout hlavu: head | | ________ ____V___ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <------------------------- A pak teprve můžeme smazat první uzel. head | | _______ ______V_ ________ ________ / nod/ | / node | / node | / node | |\--/--| |------ | |------ | |------ | | \/lue| | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ | |- | prev |<-- | prev |<-- | prev | | |------- | |-------- |-------- |-------- | --------> nullptr <------------------------- ==== Časově náročné testy (5. krok) ==== Testy v 5. kroku jsou časově náročné, a je potřeba je spouštět pouze pokud byly zkompilovány s optimalizacemi. Jsou proto schovány za tagem ''[.long]''. V případě, že používáte CMake+CTest, pak se vám automaticky dají do sady testů, pokud jste konfigurovali build buďto v ''Release'', nebo v ''RelWithDebInfo''. V ostatních případech si je musíte spustit manuálně, například takto: ./tests "[.long]" Silně doporučujeme ho spouštět pouze v optimalizované binárce, tj. konfigurovat v //Release// módu. TIP: Obzvlášť na linuxu (a asi i Macu) doporučujeme psát kolem tagů uvozovky, protože hranaté závorky jsou interpretované shellem jako pattern souboru (tedy např. ''vector.[ch]pp'' se rozvine na ''vector.cpp vector.hpp'', pokud oba soubory existují). Pokud žádný takový soubor neexistuje, některé shelly skončí s chybou (zsh), jiné to pak vezmou tak, jak to je, bez rozbalování (bash).