Search
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ě
list::swap
list::split
list::sort
==
!=
<
<=
>
>=
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.
.cpp
list.hpp
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
list::iterator
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
operator const_iterator() const
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.
BiDirectional
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]:
[.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.
-O3
Implementaci relačních operací si můžete zjednodušit chytrým využitím hlavičky <algorithm>.