Search
Tento úkol navazuje na předchozí domácí úkol, kde jste převedli trii jakožto strukturu na trii jakožto třídu a přidali další užitečné metody. V tomto úkolu rozšíříte svoji trii o další funkcionalitu, jmenovitě
trie::swap
|
&
==
!=
<
<=
>
>=
Potřebné hlavičkové soubory a testy jsou ke stažení zde.
Jeden nebo více .cpp souborů, které implementují funkce deklarované v souboru trie.hpp tak, aby testy procházely a neztrácela se paměť. Při práci na úkolu soubor trie.hpp neměňte a nemusíte ho ani odevzdávat.
.cpp
trie.hpp
word_cursor
Průnik a sjednocení nad trií se dají velmi snadno napsat rekurzivně a stále platí, že testovací vstupy jsou schválně nechané dostatečně malé, aby s tím nebyl problém.
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 trie::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
trie::iterator
class trie { class const_iterator { iterator& operator++(); }; };
trie::const_iterator& trie::const_iterator::operator++() { ... }
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]
trie3 [.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>.