Zaawansowane CPP/Ćwiczenia 10: Inteligentne wskaźniki

Ćwiczenie 1

Napisz testy sprawdzające działanie szablonu inteligentnego wskaźnika opartego na zliczaniu referencji.

Ćwiczenie 2

Napisz klasę wytyczną do wskaźnika Ref_ptr opartą o listę referencji.

Rozwiązanie

Zobacz szablon Linked_reference_counter w pliku ref_ptr.h.

Ćwiczenie 3

Napisz klasę wytyczną do wskaźnika ref_ptr opartą o licznik we wskazywanym obiekcie. Załóż, że obiekty wskazywane dziedziczą z klasy:

class Handle {
private:
  size_t _count;
public:
  Handle():_count(0){};

  void add_ref()           { ++_count;}
  bool remove_ref()        {--_count; return _count == 0;}
  size_t count() const     {return _count;};
};

Rozwiązanie

Zobacz szablon Intrusive_counter_impl w pliku ref_ptr.h.

Ćwiczenie 4

Zaimplementuj iterator pozwalający wkładać wartości na koniec kontenera.

Rozwiązanie

Zobacz plik backinserter.h.

Ćwiczenie 5

Zaimplementuj iterator realizujący przechodzenie po drzewie binarnym. Drzewo oparte jest o strukturę:

template<typename T> class binary_tree {

  class node {
    T _val;
    node *_left;
    node *_right;
    }

    node* _root;

}

Iterator powinien realizować przechodzenie drzewa "wgłąb", zaczynając od lewej strony. Dodaj do drzewa odpowiednie instrukcje begin i end, zwracające iteratory na początek i za koniec drzewa.

Podpowiedź

Napisz nierekurencyjną wersję algorytmu przeszukiwania drzewa wgłąb.

Rozwiązanie

Nierekurencyjna funkcja przechodząca drzewo wgłąb może wyglądać następująco:

Patrz plik table.h.

Ćwiczenie 6

Dodaj do drzewa instrukcję pozwalające na jego budowanie:

iterator add_root(const T &val); iterator add_left(iterator it, const T &val); iterator add_right(iterator it, const T &val);

które tworzą nowy węzeł drzewa z wartościa {val} i wstawiają go odpowiednio jako wierzchołek drzewa lub jako lewe lub prawe dziecko wierzchołka wskazywanego przez {it}. Jeśli ktoryś z tych nowych elementów już istnieje to jest rzucany wyjątek. Funkcje {add} zwracają iterator do nowo wstawionego elementu.

Uwaga Największa trudność tego zadania leży w zwracanym iteratorze. Iterator ma dwie funkcje: wskazywać na dany wierzchołek drzewa oraz umożliwiać przechodzenie do następnego wierzchołka. W funkcjach {add_...} wykorzystywana jest pierwsza funkcja iteratora. Zapewnienie tego, aby zwracany iterator poprawnie implementował drugą funkcję tzn. prawidłowo określał swój następnik, jest dużo bardziej skomplikowane. Da się to zrobić dla rozpatrywanego iteratora, ale już np. dla iteratora realizującego przeszukiwanie drzewa "wszerz" nie jest możliwe w czasie $O(1)$. Proponowane rozwiązanie to rodzielenie tych dwu funkcji iteratora, i wprowadzenie klasy {trivial_iterator}.

Klasa {trivial iterator} jest modelem konceptu {TrivialIterator} i realizuje tylko dostęp do wierzchołka. Natomiast klasa {iterator} dziedziczy z {trival_iterator} i uzupełnia go o funkcję przechodzenia do następnego elementu. Definicje funkcji {add_...} zmienimy na:

trivial_iterator add_root(const T &val); trivial_iterator add_left(trivial_iterator it, const T &val); trivial_iterator add_right(trivial_iterator it, const T &val);