Warning
This page is located in archive.

Trie 3

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ě

  • iterátory
  • kopírující konstruktor a přiřazení
  • přesouvající konstruktor a přiřazení
  • trie::swap – Prohodí obsah obou listů
  • operátor | – Sjednocení dvou trií
  • operátor & – Průnik dvou trií
  • porovnávací operátory: ==, !=, <, <=, >, >=

Potřebné hlavičkové soubory a testy jsou ke stažení zde.

Co odevzdat?

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.

Rady

  • V inicializačním seznamu lze zavolat jiný konstruktor třídy.
  • Logika iterátoru je stejná, jako u třídy word_cursor v minulém úkolu

Průnik a sjednocení

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.

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

class trie {
    class const_iterator {
        iterator& operator++();
    };
};
tedy patří tato definice
trie::const_iterator& trie::const_iterator::operator++() {
    ...
}

Č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]:

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.

Užitečné hlavičky

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

courses/b6b36pjc/ukoly/trie_3.txt · Last modified: 2017/10/24 09:38 by horenmar