Zaawansowane CPP/Ćwiczenia 10: Inteligentne wskaźniki: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 23 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
''Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki''
+
{{cwiczenie|1||
  
{Inteligentne wskaźniki}
+
Napisz testy sprawdzające działanie szablonu
 
 
'''Zadanie 1 '''  Napisz testy sprawdzające działanie szablony
 
 
inteligentnego wskaźnika opartego na zliczaniu referencji.
 
inteligentnego wskaźnika opartego na zliczaniu referencji.
 +
}}
 +
{{cwiczenie|2||
  
'''Zadanie 2 '''  Napisz klasę wytyczna do wskaźnika <code><nowiki> Ref_ptr</nowiki></code> opartą o
+
Napisz klasę wytyczną do wskaźnika <code><nowiki>ref_ptr</nowiki></code> opartą o
 
listę referencji.  
 
listę referencji.  
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Zobacz szablon <tt>Linked_reference_counter</tt> w pliku [[media:Ref_ptr.h | ref_ptr.h]].
 +
</div></div>
 +
 +
{{cwiczenie|3||
  
'''Zadanie 3 '''  Napisz klasę wytyczną do wskaźnika <code><nowiki> ref_ptr</nowiki></code> opartą o licznik we wskazywanym obiekcie. Załóż, że obiekty wskazywane dziedziczą z klasy:
+
Napisz klasę wytyczną do wskaźnika <code><nowiki>ref_ptr</nowiki></code> opartą o licznik we wskazywanym obiekcie. Załóż, że obiekty wskazywane dziedziczą z klasy:
  
  <nowiki> class Handle {
+
  <nowiki>class Handle {
 
private:
 
private:
 
   size_t _count;
 
   size_t _count;
Linia 20: Linia 26:
 
   bool remove_ref()        {--_count; return _count == 0;}
 
   bool remove_ref()        {--_count; return _count == 0;}
 
   size_t count() const    {return _count;};
 
   size_t count() const    {return _count;};
};
+
};</nowiki>
</nowiki>
+
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Zobacz szablon <tt>Intrusive_counter_impl</tt> w pliku [[media:Ref_ptr.h | ref_ptr.h]].
 +
</div></div>
  
'''Zadanie 4 '''
+
{{cwiczenie|4||
 +
 
Zaimplementuj iterator pozwalający wkładać wartości na koniec
 
Zaimplementuj iterator pozwalający wkładać wartości na koniec
 
kontenera.  
 
kontenera.  
+
}}
'''Zadanie 5 '''  Zaimplementuj iterator realizujący przechodzenie po drzewie binarnym. Drzwo opearte jest o strukturę:
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Zobacz plik [[media:Ref_ptr.h | backinserter.h]].
 +
</div></div>
 +
 
 +
{{cwiczenie|5||
 +
 
 +
Zaimplementuj iterator realizujący przechodzenie po drzewie binarnym. Drzewo oparte jest o strukturę:
  
  <nowiki> template<typename T> class binary_tree {
+
  <nowiki>template<typename T> class binary_tree {
  
 
   class node {
 
   class node {
Linia 36: Linia 52:
 
     node *_right;
 
     node *_right;
 
     }
 
     }
 +
    node* _root;
 +
}</nowiki>
 +
 +
Iterator powinien realizować przechodzenie drzewa "wgłąb", zaczynając od lewej strony. Dodaj do drzewa odpowiednie instrukcje <tt>begin</tt> i <tt>end</tt>, zwracające iteratory na początek i za koniec drzewa.
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź</span><div class="mw-collapsible-content" style="display:none">
 +
Napisz nierekurencyjną wersję algorytmu przeszukiwania drzewa wgłąb.
 +
</div></div>
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Nierekurencyjna funkcja przechodząca drzewo wgłąb może wyglądać następująco:
 +
 +
std::deque<node *> nodes;
 +
nodes.push_back(_root);<br>
 +
while(!nodes.empty()) {
 +
  node *nd <nowiki> =</nowiki>    nodes.back();
 +
  nodes.pop_back();<br>
 +
  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ł <tt>nd</tt> 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 <tt>binary_tree</tt>:
 +
 +
class iterator {
 +
std::deque<node *> _nodes;
 +
node *_current;<br>
 +
iterator(node *ptr <nowiki> =</nowiki>    0):_current(ptr) {
 +
  if(_current) {
 +
    if(_current->right)
 +
        _nodes.push_back(_current->right);
 +
    if(_current->left)
 +
        _nodes.push_back(_current->left);
 +
}<br>
 +
iterator &operator++() {
 +
  _current<nowiki> =</nowiki>  _nodes.back();
 +
  _nodes.pop_back();<br>
 +
  if(_current) {
 +
    if(_current->right)
 +
        _nodes.push_back(_current->right);
 +
    if(_current->left)
 +
        _nodes.push_back(_current->left);
 +
    }
 +
    else
 +
    _current<nowiki> =</nowiki>  0;
 +
}
 +
 +
Żeby ta klasa zachowywała się jak wskaźnik dodajemy operatory:
 +
 
 +
public:
 +
    T &operator*()  {return _ptr->_val;};
 +
    T *operator->() {return &(_ptr->_val);};
  
     node* _root;
+
Potrzebny jest też operator porównania:
 +
 +
  bool operator<nowiki> =</nowiki>  <nowiki> =</nowiki>  (const trivial_iterator&lhs) const {
 +
     return this->_ptr<nowiki> =</nowiki>  <nowiki> =</nowiki>  lhs._ptr;
 +
  }
 +
  bool operator!<nowiki> =</nowiki>  (const trivial_iterator&lhs) const {
 +
    return !operator<nowiki> =</nowiki>  <nowiki> =</nowiki>  (lhs);
 +
  }
 +
 
 +
Potrzebna jest jeszcze deklaracja:
 +
 +
friend class binary_tree;   
 +
 
 +
żeby klasa <tt>binary_tree</tt> mogła korzystać z konstruktora
 +
<tt>iterator(node *ptr)</tt>.
 +
 
 +
W klasie <tt>binary_tree</tt> definiujemy funkcje:
 +
 
 +
  iterator begin() {return iterator(_root);}
 +
  iterator end(){return iterator(0);}
 +
</div></div>
 +
 
 +
{{cwiczenie|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ą <tt>val</tt> i wstawiają go
 +
odpowiednio jako wierzchołek drzewa lub jako lewe lub prawe dziecko
 +
wierzchołka wskazywanego przez <tt>it</tt>. Jeśli ktoryś z tych nowych
 +
elementów już istnieje to jest rzucany wyjątek.
 +
Funkcje <tt>add</tt> 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 <tt>add_...</tt>
 +
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 <math>\displaystyle O(1)</math>. Proponowane rozwiązanie to rodzielenie tych
 +
dwu funkcji iteratora i wprowadzenie klasy <tt>trivial_iterator</tt>.
 +
 
 +
Klasa <tt>trivial iterator</tt> jest modelem konceptu <tt>TrivialIterator</tt> i
 +
realizuje tylko dostęp do wierzchołka. Natomiast klasa <tt>iterator</tt>
 +
dziedziczy z <tt>trivial_iterator</tt> i uzupełnia go o funkcję
 +
przechodzenia do następnego elementu. Definicje funkcji <tt>add_...</tt> 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);
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Wyżej opisaną klasę iteratora dzielimy na dwie klasy. Pierwsza to <tt>trivial_iterator</tt>, zawierająca pole <tt>_ptr</tt>,
 +
operator  dostępu <tt>*</tt> i <tt>-></tt> oraz operatory porównania.
 +
 
 +
Druga to
 +
 
 +
class iterator: public trivial_iterator ;
 +
 
 +
zawierająca pole <tt>_nodes</tt> i operatory <tt>++</tt>.
 +
 
 +
Funkcje <tt>insert_</tt> są już łatwe do zaimplementowania, np.:
 +
 
 +
  trivial_iterator insert_right(trivial_iterator it,const T &val) {
 +
    if(!it._ptr->_right)
 +
      it._ptr->_right <nowiki> =</nowiki>    new node(val);
 +
    return trivial_iterator(it._ptr->_right);
 +
  }
  
}
+
Całość  kodu jest zamieszczona w pliku [[media:Binary_tree.h | binary_tree.h]].
</nowiki>
+
</div></div>

Aktualna wersja na dzień 10:41, 2 paź 2006

Ć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