Tento úkol navazuje na 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í zde.

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.

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.

Jako sort doporučujeme 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 stabilní řazení, ale v této úloze to netestujeme. Testujeme pouze zda máte rozumnou asymptotickou složitost.

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

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--();
    };
};

list::iterator& list::iterator::operator--() {
    ...
}

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 {
   ...
}

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.

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.

Implementaci relačních operací si můžete zjednodušit chytrým využitím hlavičky <algorithm>.