Zaawansowane CPP/Ćwiczenia 10: Inteligentne wskaźniki

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ć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

Ć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

Ćwiczenie 4

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

Rozwiązanie

Ć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ź
Rozwiązanie

Ćwiczenie 6

Dodaj do drzewa instrukcje 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ścią 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 . 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 trivial_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);
Rozwiązanie