Toto je starší verze dokumentu!


Domácí úkol č. 5: Vyvážený binární strom (bonus: mapa)

  • Úkol zadán: 30. 11. 2015
  • Deadline odevzdání: 15. 12. 2015
  • Odevzdávat lze od: 5. 12. 2015
  • Odevzdávané soubory: tree_impl.h, hw05_map.h (bonus)

Doplnění zadání (zobrazeno podtrženě):

  • 2.12.2015 Drobná doplnění zadání: doplněna poznámka o užití AVL/RBtree, struct→class (méně matoucí), „můžete předpokládat že komparátor je“ namísto „komparátor je“.
  • 4.12.2015 Opraven rozbitý odkaz v sekci literatura na materiál 3. strany.
  • 5.12.2015 Úloha otevřena k odevzdávání.
  • 7.12.2015 Doplněn explicitní zákaz vkládání stejných hodnot přímo k metodě insert.
  • Aktuální verze zveřejněných testů: 11.12.2015 09:18

Motivace

V dnešní době není problém nasbírat obrovské množstí dat. Jakékoliv lineární vyhledávání v takovém objemu dat je ale těžce neefektivní, proto se snažíme mít data nějakým způsobem organizovaná, uspořádaná. Takové informaci říkáme zpravidla index. Jedním z druhů indexů je vyvážený binární strom, který má řadu výhod.

Jako praktický příklad využití stromu můžete považovat našeptávač klienta příkazové řádky. Uživatel postupně píše do příkazové řádky slova, která mohou být buď příkazy celými, nebo jen jejich prefixem. Doplněným příkazem je pak uzel stromu příkazů, který hledanou frází začíná začíná.

Než se pustíte do samotné implementace, přečtěte si prosím pečlivě zadání (včetně poznámek), a zkuste si vytvořit diagramy tříd. Pamatujte, že řešení, které bude fungovat, ale nebude využívat vhodného vyváženého stromu nemusí dosáhnout plného počtu bodů (9+3 → 8.5+0). Na druhou stranu, každé řešení, které bude alespoň trochu fungovat, by nějaký ten bod dostat mělo (a tedy pomůže splnění podmínky 4 nenulových domácích úloh).

Popis

Samotný vyvážený strom budete implementovat pomocí dvou šablon tříd - šablony, reprezentující celý strom, a její dceřinné třídy, reprezentující uzel stromu. Kompilace šablon se nechová zcela tak jak jste zvyklí - při samotném načtení šablony kompilátorem je provedena pouze syntaktická kontrola. To, zda je kód v pořádku a nevolá neexistující metody či funkce se ověřuje až při užití konkrétních metod šablony. V sekci požadavky tedy najdete, co můžete u jednotlivých metod předpokládat.

Pokud jste z pouhého pomyšlení na strom na větvi, nezoufejte. Stromy si můžete připomenout pomocí odkazů v sekci literatura, sice simulátory chování dvou druhů balancovaných binárních stromů - AVL a Red-Black. Pokud byste chtěli použít jiný typ stromu, můžete, mějte však na paměti, že stromy vážené podle váhy prvku nemusí být akceptovány. Použitím AVL či Red-Black tree rozhodně o body nepříjdete.

V případě, že budete implementovat bonus (obdoba std::map), budete potřebovat další 3 třídy - mapu, dvojici klíče a hodnoty (obdoba std::pair) a iterátorem.

Slovníček

  • copy-constructable značí, že daný datový typ má kopírovací konstruktor.
  • default-constructable značí, že daný datový typ má bezparametrický konstruktor.

Šablona ''balanced_tree''

Tato šablona bude implementovat vyvážený strom. Šablona bude využívat pomocnou dceřinou třídu tree_node, která bude reprezentovat uzel stromu. Protože jsou veškeré binární vyhledávací stromy založené na porovnávání, které se může lišit dle okolností, bude šablona balanced_tree parametrizována i funktorem komparátoru. Posledním parametrem šablony pak budiž typ úložiště dat - zpravidla const Key.

Šablona bude specializována následujícími argumenty:

  • Key značí argument šablony, zastupující datový typ ukládaných dat. Pokud budete do stromu ukládat typ int, bude Key značit právě typ int.
  • Compare značí komparátor, který bude strom používat. Komparátor je vybaven kopírovacím konstuktorem a má přetížený operátor funkčního volání (operátor () - jde tedy o funktor). Když nad tímto zapřemýšlíte, uvědomíte si, že uvedené vlastnosti vylučují použití funkce jako komparátoru (pro zvídavé studenty viz std::function z C++11). Pro komparátor dále platí:
    1. komparator(a, b) → true značí že v setřízené posloupnosti a předchází b (laicky a < b).
    2. komparator(a, b) → false && komparator(b, a) → false značí že a je ekvivalentní b (laicky a == b).
    3. Pro lepší představu si nastudujte třídu std::less (hlavička functional).
  • KeyStorage značí typ atributu, sloužícího k uložení klíče. Pokud chcete ukládat int z příkladu o dvě odrážky výše, bude vhodné jej uložit jako const int. Pokud by totiž klíč nebyl uložen jako const, mohlo by dojít k jeho změně a tedy porušení vlastností binárního stromu a jeho rozbití.

Dále bude šablona obnášet následující metody:

  • Konstruktor a destruktor
    • Kopírovací konstruktor (kopíruje jak strom, tak komparátor).
    • Bezparametrický konstruktor.
    • Parametrický konstruktor (argumentem existující komparátor).
    • Destruktor.
  • Vkládání a mazání prvků
    • Metoda erase - vymaže ze stromu existující klíč.
    • Metoda insert - vloží do stromu daný klíč.
  • Přístup k uloženým datům
    • Metoda find - vrátí uzel s daným klíčem.
    • Metoda root - vrátí kořen stromu.
    • Metoda get_comp() - zpřístupní interní komparátor stromu.

A nakonec dceřinná třída tree_node, obnášející:

  • Atribut KeyStorage key, nesoucí samotná data.
  • Metody get_left(), get_right() a get_parent(), vracející odpovídající potomky a rodiče uzlu ve stromu. Platí, že v levém podstromu uzlu jsou všechny hodnoty menší než key a v pravém podstromu hodnoty větší.
  • Libovolné pomocné metody a atributy samozřejmě jako privátní.

Pro volání všech uvedených metod platí, že metoda bude volána v konzistentním stavu a také její zavolání v konzistentní stav vyústí. Zejména tedy musí zůstat strom vyvážený a s platnými ukazateli. Pro porovnávání klíčů můžete používat jen a pouze komparátor (tj. namísto if (a < b) používejte if (komparator(a, b)). Bližší (a striktnější) popis pravidel konzistence najdete v sekci požadavky.

Požadavky

Šablona ''balanced_tree'' a dceřinná třída ''tree_node''

template <typename Key, typename Compare = std::less<Key>, typename KeyStorage = const Key > class balanced_tree;

Požadavky na šablonu ''balanced_tree''

  • Key datový typ klíče. Můžete předpokládat, že Key je copy-constructable.
  • Compare, platí:
    • Můžete předpokládat, že je copy-constructable.
    • Operátor () kompatibilní s prototypem bool operator(const Key & a, const Key & b) const:
      1. komparator(a, b) → true značí že v setřízené posloupnosti a předchází b (laicky a < b),
      2. komparator(a, b) → false && komparator(b, a) → false značí že a je ekvivalentní b (laicky a == b).
    • Výchozím komparátor budiž std::less<Key>
  • KeyStorage datový typ uloženého klíče.
    • Výchozí hodnotou budiž const Key
  • Konstruktory
    • Kopírovací konstruktor. Můžete předpokládat, že jak Key, tak Compare a KeyStorage nejsou default-constructable.
    • Bezparametrický konstruktor. Můžete předpokládat, že Compare je default-constructable.
    • Parametrický konstruktor (argumentem instance komparátoru), který zkopíruje komparátor a uloží jej jako atribut.
  • tree_node * find(const Key &)
    const tree_node * find(const Key &) const
     
    1. zjistí, zda je ve stromu uložena hodnota v argumentu funkce,
    2. pokud se ve stromu hodnota nevyskytuje, vrací nullptr, pokud vyskytuje, vrátí ukazatel na odpovídající uzel své interní struktury.
  • void insert(const Key &)
    1. vloží do stromu kopii hodnoty v argumentu, dodržuje pravidla pro konzistenci,
    2. hodnota, která již ve stromu vložena je není vkládána podruhé, ani nepřepisuje svou již uloženou instanci (důsledek vlastností komparátoru a pravidel konzistence).
  • void erase(const Key &)
    1. odstraní ze stromu hodnotu v argumentu, dodržuje pravidla pro konzistenci,
    2. pakliže se daný klíč ve stromu nevyskytuje, nic nemaže.
  • const Compare & get_comp() const
    1. vrací komparátor, použitý stromem.
  • tree_node * root()
    const tree_node * root() const
    1. vrátí ukazatel na kořen stromu,
    2. rodič kořene je nullptr,
    3. pokud je strom prázdný, vrací nullptr.

Dceřinná třída ''balanced_tree<Key, Compare, KeyStorage>::tree_node''

Veřejně přístupná dceřinná třída tree_node představuje uzel stromu. Nese:

  • KeyStorage key
    1. atribut nesoucí klíč; můžete předpokládat vlastnost copy-constructable.
  • tree_node * get_left()
    const tree_node * get_left() const
     
    tree_node * get_right()
    const tree_node * get_right() const
     
    tree_node * get_parent()
    const tree_node * get_parent() const
    1. metody vracející odpovídající potomky a rodiče uzlu ve stromu (pokud jsou, jinak nullptr).

PRAVIDLA PRO KONZISTENCI

  1. Před zavoláním libovolné veřejné metody je strom vyvážený, stejně tak po jejím ukončení.
  2. Pro veškeré porovnání hodnot je použit komparátor, nikoliv relační operátory nad Key.
  3. Pokud je získán nenulový ukazatel metodou find a následně zavolána metoda insert se stejným argumentem jako find, zůstává ukazatel získaný find platný a klíč není přepsán.
  4. Pokud je získán nenulový ukazatel metodou find a následně zavolání metoda erase se stejným argumentem jako find, pozbývá ukazatel získaný find platnosti (tj. ukazuje na neplatnou paměť – tj. nemusíte počítat s tím, že by ho kdy kdo použil). Ostatní ukazatele získané (předchozími) voláními find pro jiné hodnoty zůstávají platné.
  5. Libovolná posloupnost operací nezpůsobuje memory-leaky.
Zajisté jste si všimli, že se řada metod vyskytuje jak v const, tak v obyčejné variantě. V naivním pohledu toto znamená duplikaci kódu, vy už ale znáte const_cast. Zkuste jej využít.

Bystřejší mysli si uvědomí, že existují i šablony funkcí (např. hlavička algorithm) a statické metody - odtud už je jen krůček k tomu, abyste kód napsali jen jednou a nemuseli využívat služeb const_cast.

BONUS

Šablona ''hw05_map'' [2b]

Šablona hw05_map reprezentuje jednoduchou mapu, implementovanou pomocí výše zmíněného stromu. Obecně mapa ukládá dvojici (klíč, hodnota). Pokud bychom ale použili strom přímo, mohli bychom použít jen komparátory, které uvažují celou dvojici. Vašim úkolem tedy bude vytvořit třídy reprezentující mapu, uloženou dvojici a (v případě druhého bonusu) iterátor.

template <typename Key, typename Value, typename Compare = std::less<Key> > struct hw05_map;
  • Key značí typ klíče, který splňuje copy-constructable.
  • Value značí typ ukládané hodnoty. Pro jednodušší implementaci můžete předpokládat, že Value je jak default-constructable, tak má operátor přiřazení.
  • Compare značí komparátor, který bude mapa používat pro porovnání klíčů.
  • Konstruktory
    • Bezparametrický konstruktor. Můžete předpokládat, že Compare je default-constructable.
    • Parametrický konstruktor (argumentem instance komparátoru), který zkopíruje komparátor a uloží jej jako atribut (tj. copy-constructable).
  • void insert(const Key &, const Value &)
    1. vloží do mapy odpovídající záznam a hodnotu.
  • void erase(const Key &)
    1. odstraní odpovídající záznam,
    2. v případě, že daný záznam neexistuje, beze chyby ukončí metodu.
  • Value & operator[](const Key &)
    1. vrátí referenci na uloženou hodnotu odpovídající klíči,
    2. případ kdy taková hodnota uložena není se netestuje, vypořádejte se s ním vhodným assertem.
  • struct item {
    const Key key;
    Value value;
    item(const Key & key, const Value & value); // implementujte
    }
Bystrého čtenáře zajisté napadne, že si může vytvořit pomocné třídy, do kterých zabalí vše potřebné. Jak ale zajistit to, že operátor[] umožní změnit uloženou hodnotu? Jednoduše, strom vytvoříte s argumentem šablony stromu KeyStorage nastavenou na stejný datový typ, jako Key.

Iterátory pro ''hw05_map'' [2b]

Za obvyklých podmínek lze mapou iterovat - tedy procházet položky v pořadí dle klíče, bez jeho explicitní znalosti. K tomuto slouží iterátory. Pro jednoduchost budete implementovat pouze iterátory nabízející přístup pro čtení, sice typu forward_iterator (tedy iterátor, který nabízí ++, ale už ne ). Jako datový typ iterátoru poslouží dceřiná třída šablony hw05_map, pojmenovaná const_iterator.

  • const_iterator begin() const
    1. vrátí iterátor, odpovídající 1. položce mapy,
    2. pokud je mapa prázdná, vrátí výsledek end().
  • const_iterator end() const
    1. vrátí iterátor, který už neukazuje na platnou položku,
    2. v případě prázdné mapy platí begin() == end().
  • Požadavky na třídu const_iterator:
    • const_iterator & operator++()
      1. prefixový posun iterátoru,
      2. odpovídá chování „vracím sebe sama posunutého“,
      3. v případě že se již není kam posunout, stane se ekvivalentním end().
    • const_iterator operator++(int)
      1. postfixový posun iterátoru,
      2. odpovídá chování „zkopíruji se a posunu, vracím neposunutou kopii“,
      3. v případě že se již není kam posunout, vrací end().
    • const item * operator->() const
      1. vrátí ukazatel na odpovídající instanci třídy item,
      2. dereference end() vrací nullptr.
    • const item & operator*() const
      1. vrátí referenci na odpovídající instanci třídy item,
      2. dereference end() není testována, ošetřete ji ale vhodným assertem.
    • Relační operátory ==, !=,
    • Bezparametrický konstruktor (vytváří neplatný iterátor), kopírovací konstruktor (kopie platného iterátoru je platný iterátor, analogicky kopie neplatného iterátoru je neplatný iterátor) a operátor přiřazení =.
    • Iterátor musí obnášet několik definic datových typů. Pro jejich seznam se podívejte na šablonu std::iterator. Mějte však na paměti, že reference i ukazatel, které budete vracet, budou const.

Literatura

Referenční implementace

Stáhnout si můžete předkompilovanou hlavičku obsahující referenční implementaci. Narozdíl od objektových souborů ale nejsou multiplatformní a obsah samotného souboru je silně závislý na platformě. Tuto hlavičku tedy můžete použít pouze na serveru aisa.fi.muni.cz s g++ verze 4.8.2. # module load gcc-4.8.2

Samotná referenční implementace (zde) slouží k upřesnění nejasností v zadání a umožňuje vlastní testy poměřit s referenční implementací. V žádném případě nemáte za úkol okopírovat komplet její chování, zejména pak nesupluje testy ani ukázkový program!

Protože jsou předkompilované hlavičky ve své podstatě vysypanou pamětí kompilátoru, platí pro jejich užití striktní pravidla:

  • Tuto hlavičku lze použít pouze na stejné platformě se stejnou cílovou architekturou.
  • Přepínače g++ musí být shodné s přepínači se kterými byla hlavička generována.
  • Předkompilovaná hlavička je použita pouze pokud je načítána prvním makrem #include v překladové jednotce a jejímu nahrání nesmí předcházet žádná jiná konstrukce (jedná se tedy o řádek č. 1 celého souboru).
  • Ve vlastním zdrojovém kódu používáte i nadále #include „hlavicka.h“, nikoliv #include „hlavicka.h.gch“.
# g++ -H -Werror -pedantic -Wall -Wextra -O2 -std=c++11 vasetesty.cpp -o vasetesty

V případě že dojde ke korektnímu nahrání předkompilované hlavičky uvidíte na řádku s cestou k hlavicka.h.gch symbol “!“, v případě obtíží „x“ nebo se takový řádek vůbec nevyskytne.

Pozn.: Hlavička byla zcela záměrně generována s optimalizacemi a bez ladícího řežimu, v případě aplikace vašich testů tedy nebude ladící režim fungovat a budete si muset vystačit s výpisy!

Poznámky a testování

Testování

Psaní vlastních šablon může být poněkud stresující, nezřídkakdy jeden zapomene nějaké klíčové slovo nebo se nevyzná ve výpisu kompilátoru. Typickým problémem je pak situace, kdy si neuvědomíte že kód něco předpokládá.

struct A {
    A() = delete;
    A(const int i);
    ...
};
std::vector<A> data;
data.reserve(3); // platný kód
data.resize(3); // chyba při kompilaci - skrytě vyžaduje bezparametrický konstruktor

Protože jsou logy kompilátoru vítaným pomocníkem, mimo jiné i s těmito chybami, máte k dispozici část testů nanečisto (pochopitelně redakčně upravených).

Testy (nejen tyto) jsou organizovány následovně:

  • Kompilační testy - ověřují, že Váš kód jde zkompilovat v souladu s požadavky zadání, že nepředpokládáte o argumentech šablony nic, co by nebylo v zadání uvedeno. Některé z těchto testů mají uspět, u jiných má dojít k chybě kompilace. Některé nepřidělují žádné body, ale současně jejich neprojití bude znamenat, že nedostanete doplňkových 3-1 bodů za odevzdání plně funkční úlohy.
  • Testy, které ověřují základní vlastnosti binárního stromu; přičemž šablona je parametrizována:
    • pouze klíčem - typ int
    • typem klíče int a vlastním komparátorem
  • Komparátorem, který nevyhovuje specifikaci
  • Kopírování stromu
  • Testy, které používají datové typy bez bezparametrického konstruktoru, či vlastní implementaci std::less
  • Test, ktery ma podchytit extremne neefektivni implementace (kupříkladu takové, které budou simulovat strom propojeným seznamem - O(n^2) v každém přístupu). Drtivé většiny z Vás se nedotkne.
  • Testy bonusu

Poznámky

  • V úloze se vyskytují dvojice tříd, které potřebují vzájemně přistupovat ke svým privátním prvkům. Tedy jako kamarád do kamarádovy ledničky.
  • Testy Vám budou v tomto házet klacky pod nohy - budete dostávat komparátory a ukládané typy bez různých metod, jen s minimem potřebného. Naštěstí máte část těchto testů k dispozici.
  • Tato úloha je zaměřená na univerzalitu, nikoliv bezpečnost kódu - v testech se proto nesetkáte s operacemi na neplatných iterátorech (např. *map_instance.end()++, apod.). Můžete tedy předpokládat, že testy operují pouze s iterátory (dle zadání) platnými. Porovnání (platného) iterátoru s neplatným iterátorem je platnou operací!
Pokud Vás šablony matou, představte (a klidně pište kód) takto:
typedef int Key;
typedef std::less<Key> Compare;
typedef const Key KeyStorage;
struct balanced_tree {
...
};

Ve chvíli kdy budete mít kód odladěný a funkční stačí změnit první řádky na:

template <typename Key, typename Compare = std::less<Key>, typename KeyStorage = const Key>
struct balanced_tree {

Nasledně stačí vypořádat se s chybami při překladu (nějaké se jistě objeví).

Pokud se odkazujete na type deklarovaný uvnitř třídy, která je argumentem šablony a kompilátor v tomto místě hlásí chybu (např. 'expected primary expression before'…, nebo 'need typename before'…), zkuste využít dodatečné typename (typedef aa::bb cc → typedef typename aa::bb cc). Tuto chybu potkáte zpravidla ve chvíli, kdy využíváte dceřinný typ (jiné) šablony, který ještě není definitivně rozhodnut. Taková situace nastává kupříkladu u šablon, které uvnitř používají nějaký kontejner a jeho iterátory.

Autor: Úlohu připravil Lukáš Ručka, v případě nejasností kontaktujte na xrucka@fi.muni.cz nebo diskuzním fóru.

QR Code
QR Code public:pb161_fall15_hw05 (generated for current page)