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

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.