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:

std::deque<node *> nodes;
nodes.push_back(_root);

while(!nodes.empty()) {
  node *nd  =    nodes.back();
  nodes.pop_back();

  if(node->right) nodes.push_back(node->right);
  if(node->left)  nodes.push_back(node->left);
}

Iterator będzie wykonywał ten algorytm krok po kroku. W każdym kroku węzeł nd będzie wezłem wskazywanym przez ten iterator. Jako oznaczenie końca iteracji wykorzystamy iterator wskazujący na węzeł pusty.

Definujemy klasę zagnieżdżoną wewnątrz binary_tree:

class iterator {
std::deque<node *> _nodes;
node *_current;

iterator(node *ptr  =    0):_current(ptr) {
  if(_current) {
    if(_current->right) 
       _nodes.push_back(_current->right);
    if(_current->left) 
       _nodes.push_back(_current->left);
}

iterator &operator++() {
  _current =   _nodes.back();
  _nodes.pop_back();

  if(_current) {
    if(_current->right) 
       _nodes.push_back(_current->right);
    if(_current->left) 
       _nodes.push_back(_current->left);
   }
   else
   _current =   0;
}

Żeby ta klasa zachowywała się jak wskaźnik dodajemy operatory:

public:
   T &operator*()  {return _ptr->_val;};
   T *operator->() {return &(_ptr->_val);};

Potrzebny jest też operator porównania:

 bool operator =    =   (const trivial_iterator&lhs) const {
   return this->_ptr =    =   lhs._ptr;
 } 
 bool operator! =   (const trivial_iterator&lhs) const {
   return !operator =    =   (lhs);
 }

Potrzebna jest jeszcze deklaracja:

friend class binary_tree;    

Żeby klasa binary_tree mogła korzystać z konstruktora iterator(node *ptr).

W klasie binary_tree definiujemy funkcje:

 iterator begin() {return iterator(_root);}
 iterator end(){return iterator(0);}

Ć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 $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);

Rozwiązanie

Zobacz plik backinserter.h.

Rozwiązanie 6

Wyżej opisaną klasę iteratora dzielimy na dwie klasy. Pierwsza to {trivial_iterator} zawierająca pole {_ptr}, operator dostępu {*} i {->} oraz operatory porównia.

Drugoa to

class iterator: public trivial_iterator ;

zawierająca pole {_nodes} i operatory {++}.

Funkcje {insert_} są już łatwe do zaimplementowania, np.:

 trivial_iterator insert_right(trivial_iterator it,const T &val) {
   if(!it._ptr->_right) 
     it._ptr->_right  =    new node(val);
   return trivial_iterator(it._ptr->_right);
 }

Całość kodu jest zamieszczona w pliku {mod11/exercises/binary_tree.h}binarytree.h.