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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
(Nie pokazano 25 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
 +
{{cwiczenie|1||
  
''Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki''
+
Napisz testy sprawdzające działanie szablonu
 +
inteligentnego wskaźnika opartego na zliczaniu referencji.
 +
}}
 +
{{cwiczenie|2||
  
{Inteligentne wskaźniki}
+
Napisz klasę wytyczną do wskaźnika <code><nowiki>ref_ptr</nowiki></code> opartą o
 +
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>
  
==Wstęp==
+
{{cwiczenie|3||
  
Wskaźniki to jeden z bardziej pożytecznych elementów języka C/C++, ale
+
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:
napewno najbardziej niebezpieczny. Zabawa z gołymi wskaźnikami
 
przypomina żonglerkę odbezpieczonymi granatami. To nie jest już
 
kwestia, czy nastąpi wybuch, ale tego, kiedy on nastąpi.  Możliwości
 
wywołania wybuchu i jego konsekwencje są wielorakie:
 
* Możemy usunąć wskaźnik, nie zwalniając pamięci, na którą on
 
  wskazuje.  Jeśli żaden inny wskaźnik nie wskazuje na ten obszar, to
 
  jest on bezpowrotnie stracony dla naszej aplikacji i mamy do
 
  czynienia z wyciekiem pamięci.
 
* Możemy zwolnić ten sam obszar pamięci kilkakrotnie.
 
Powoduje to zwykle krach całej aplikacji.
 
* Podobnie, jeśli spróbujemy zdereferencjonować wskaźniki
 
  zerowe (<code><nowiki> null</nowiki></code>).
 
* No i oczywiście mamy całe spektrum możliwości sięgnięcia za
 
  pomocą wskaźnika tam, gdzie nie powinniśmy, odczytując lub co gorsza,
 
  zmieniając, nie te zmienne co trzeba.
 
 
Jeśli więc nie czujemy się jak Rambo albo  sam Chuck
 
Norris, to powinniśmy poszukać jakiś zabezpieczeń. W C++
 
zabezpieczenia są dostarczane poprzez możliwość definicji własnych
 
typów. Dzięki klasom możemy nie korzystać z dynamicznej alokacji
 
pamięci bezpośrednio, ale za pośrednictwem klas, które dbają o alokację
 
w konstruktorach, dealokację w destruktorach, zwiększają i
 
zmmniejszają pamięć na żądanie, itp. Przykładem takiego podejścia są
 
np. kontenery STL, których jedną z zalet,  jest właśnie zarządzanie
 
własną pamięcią. Jeśli jednak ciągle potrzebujemy wskaźników, to możemy
 
rozważyć opakowanie ich w klasy.  Jest to możliwe dzięki możliwościom,
 
jakie w C++ daje przeładowywanie operatorów. W szczególności możemy
 
przeładowywać operatory dereferencjonowania <code><nowiki> operator*()</nowiki></code> i
 
<code><nowiki> operator->()</nowiki></code>. W ten sposób możemy upodobnić zachowanie
 
definiowanych przez nas typów, do zachowania  wskaźników.
 
Takie typy nazywamy inteligentnymi wskaźnikami, ponieważ dostarczają
 
nam dodatkowej funkcjonalności ponad zwykłe zachowanie wskaźnika.
 
  
Tak jak i u ludzi rodzaje inteligencji wskaźników bywają różne;
+
<nowiki>class Handle {
inteligente wskaźniki występują w najróżniejszych wariacjach. Podział
+
private:
tych wariantów można przeprowadzić na wiele sposobów, ja skoncentruję
+
  size_t _count;
się na dwóch grupach:
+
public:
* Zachowanie wskaźników podczas kopiowania, przypisywania
+
  Handle():_count(0){};
i niszczenia. Nazwiemy to prawami własności.
 
* Zachowanie się operatorów  <code><nowiki> operator*()</nowiki></code> i <code><nowiki> operator->()</nowiki></code>.
 
Nazwiemy to kontrolą dostępu.
 
 
Poniżej krótko przedstawię przegląd głównych możliwości w każdej z
 
powyższych grup.
 
  
==Prawa własności==
+
  void add_ref()          { ++_count;}
 +
  bool remove_ref()        {--_count; return _count == 0;}
 +
  size_t count() const    {return _count;};
 +
};</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>
  
Głównym powodem używania inteligentnych wskaźników jest uzyskanie
+
{{cwiczenie|4||
kontroli nad operacjami kopiowania, przypisywania i niszczenia
 
wskaźnika. W tym kontekście mówimy często, że wskaźnik jest albo nie
 
jest właścicielem obiektu, na który wskazuje.  Poniżej przedstawiam cztery
 
typowe schematy wskaźników.
 
 
 
====Głupie wskaźniki====
 
 
 
Zwykłe (nieinteligentne) wskaźniki nie są właścicielami obiektów, na
 
którę wskazują. Kopiowanie czy przypisanie, prowadzi do współdzielenia
 
referencji (oba wskaźniki wskazują na ten sam obiekt), często
 
niezamierzonej. Zniszczenie wskaźnika  nie powoduje
 
zniszczenia (dealokacji pamięci) obiektu na który on wskazuje.
 
Przedstawia to rysunek&nbsp;[[##fig:ptr_vulgaris|Uzupelnic fig:ptr_vulgaris|]] na którym zilustrowano
 
przebieg wykonania kodu:
 
 
 
<nowiki> void f() {
 
X *px( new X);
 
X  py(px);
 
X  pz(new X);
 
pz  =    py;
 
}
 
 
 
f();
 
</nowiki>
 
 
 
[width<nowiki> =</nowiki>  ]{mod11/graphics/vulgaris.eps}
 
 
   
 
   
{Zwykłe wskaźniki.}
+
Zaimplementuj iterator pozwalający wkładać wartości na koniec
+
kontenera.  
====Zliczanie 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 plik [[media:Ref_ptr.h | backinserter.h]].
 +
</div></div>
  
Wskaźniki zliczające referencje są niejako właścicielami grupowymi
+
{{cwiczenie|5||
obiektu, na który wskazują. Kopiowanie i przypisanie powoduje
 
współdzielnie referencji, ale kontrolowane, w tym sensie, że
 
monitorowana jest liczba wskaźników do danego obiektu.  Na zasadzie
 
"ostatni gasi światło" zniszczenie wskaźnika powoduje zniszczenie
 
obiektu wtedy, gdy był to jedyny (ostatni) wskaźnik na ten obiekt.
 
Liczenie referencji reprezentuje więc prostą wersję "odśmieczacza"
 
(garbage-collector). Zachowanie się tego typu wskaźników prezentuje
 
rysunek&nbsp;[[##fig:ptr_reference|Uzupelnic fig:ptr_reference|]] w oparciu o analogiczny kod:
 
  
<nowiki> void f() {
+
Zaimplementuj iterator realizujący przechodzenie po drzewie binarnym. Drzewo oparte jest o strukturę:
ref_ptr<X>  px(new X);
 
ref_ptr<X>  py(px);
 
ref_ptr<X>  pz(new X);
 
pz  =    py;
 
}
 
  
f();
+
<nowiki>template<typename T> class binary_tree {
</nowiki>
 
  
[width<nowiki> =</nowiki>   ]{mod11/graphics/reference.eps}
+
   class node {
+
    T _val;
{Wskaźniki zliczające referencje.}
+
    node *_left;
+
    node *_right;
====Głęboka/fizyczna kopia====
+
    }
 +
    node* _root;
 +
}</nowiki>
  
Takie wskaźniki są pojedynczymi właścicielami obiektów na które
+
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.
wskazują i zachowują się jak wartości, a nie, wskaźniki. Kopiowanie bądź
+
}}
przypisanie powoduje fizyczne kopiowanie obiektu wskazywanego.
+
<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">
Zniszczenie wskaźnika powoduje zniczenie wskazywanego obiektu. Od
+
Napisz nierekurencyjną wersję algorytmu przeszukiwania drzewa wgłąb.
zwykłych wartości obiektów różnią się tym, że mają zachowanie
+
</div></div>
polimorficzne i używane są tam, gdzie polimorfizm jest nam potrzebny, a
 
więc nie możemy użyć bezpośrednio samych obiektów. Zachowanie kodu:
 
  
<nowiki> void f() {
+
<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">
clone_ptr<X> px(new X);
+
Nierekurencyjna funkcja przechodząca drzewo wgłąb może wyglądać następująco:
clone_ptr<X> py(px);
 
cloen_ptr<X> pz(new X);
 
pz  =    py;
 
}
 
  
f();
+
std::deque<node *> nodes;
</nowiki>
+
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);
 +
}
  
ilustruje rysunek&nbsp;[[##fig:deep_copy|Uzupelnic fig:deep_copy|]].
+
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.  
[width<nowiki> =</nowiki>   ]{mod11/graphics/deep_copy.eps}
+
Jako oznaczenie końca iteracji wykorzystamy iterator wskazujący na węzeł pusty.
 
{Wskaźniki wykonujące kopie fizyczne.}
 
 
Zastosowanie wskaźników z głębokim kopiowaniem zilustruję na
 
przykładzie podanego już wcześniej przykładu z kształtami
 
geometrycznymi.  W programie wykorzystującym takie kształty na pewno
 
zachodzi konieczność kopiowania kształtów. Załóżmy, że wybraliśmy
 
(myszką) jakiś kształt i wskaźnik do niego jest przechowywany w
 
zmiennej <code><nowiki> Shape *selected</nowiki></code>.  Załóżmy, że jest to obiekt typy
 
<code><nowiki> Circle</nowiki></code>.  Teraz chcemy uzyskać kopię tego kształtu. Przypisanie
 
  
<nowiki> Shape *copy  =    selected;
+
Definujemy klasę zagnieżdżoną wewnątrz <tt>binary_tree</tt>:
</nowiki>
 
  
oczywiście nie jest poprawne, bo uzyskamy dwa wskaźniki na jeden obiektA
+
  class iterator {
my potrzebujemy drugiego obiektu. Bez koniecznośći polimorfizmu
+
std::deque<node *> _nodes;
wystarczyłoby użyć konstruktora kopiującego:
+
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;
 +
}
  
  <nowiki> Shape *copy  =    new Shape(*selected);
+
Żeby ta klasa zachowywała się jak wskaźnik dodajemy operatory:
</nowiki>
+
 
 +
  public:
 +
    T &operator*() {return _ptr->_val;};
 +
    T *operator->() {return &(_ptr->_val);};
  
Niestety w naszym przypadku ten kod się nawet nie skompiluje, bo klasa
+
Potrzebny jest też operator porównania:
<code><nowiki> Shape</nowiki></code> jest klasą abstrakcyjną. Nawet gdyby nie była, to i tak
 
zostałby utworzony obiekt typu <code><nowiki> Shape</nowiki></code> a nie <code><nowiki> Circle</nowiki></code>.  W celu
 
zaimplementowania kopiowania polimorficznego możemy wyposażyć naszą
 
klasę <code><nowiki> Shape</nowiki></code> w funkcje
 
 
 
<nowiki> virtual Shape *clone() const  =    0
 
</nowiki>
 
 
 
i następnie zdefiniować ją w każdej podklasie:
 
 
 
<nowiki> class Circle :public Shape {
 
...
 
Circle *clone() {return new Circle(*this);};
 
}
 
</nowiki>
 
 
 
Możemy wtedy skopiować (sklonować) nasz obiekt za pomocą:
 
 
 
<nowiki> Shape *copy  =    selected->clone();
 
</nowiki>
 
 
 
Możemy teraz tę technikę, nazywaną również wzorcem prototypu, lub
 
fabryką klonów (zob. {gamma}), zastosować w implementacji inteligentnego
 
wskaźnika <code><nowiki> clone_ptr</nowiki></code>:
 
 
 
<nowiki> clone_ptr<Shape> selected;
 
...
 
clone_ptr<Shape> copy(selected);
 
</nowiki>
 
 
 
====autoptr====
 
 
 
Wskaźniki <code><nowiki> auto_ptr</nowiki></code> (jedyne inteligentne wskaźniki dostępne w
 
standardzie C++) są pojedynczymi, bardzo zaborczymi, właścicielami obiektu,
 
na który wskazują.  Tak zaborczymi, że nie dopuszczają możliwości
 
współdzielenia obiektu ani jego kopiowania.  Próba skopiowania, albo
 
przypisania prowadzi do przekazania własności: obiekt
 
kopiowany(przypisywany) oddaje/przekazuje prawo własności do
 
posiadanego obiektu drugiemu obiektowi.  Oznacza to, że obiekt
 
kopiowany lub przypisywany jest zmieniany w trakcie tych operacji.
 
Ilustruje to rysunek&nbsp;[[##fig:auto_ptr|Uzupelnic fig:auto_ptr|]] na podstawie kodu:
 
 
 
<nowiki> void f() {
 
auto_ptr<X>  px(new X);
 
auto_ptr<X>  py(px);
 
auto_ptr<X>  pz(new X);
 
pz  =    py;
 
}
 
 
 
f();
 
</nowiki>
 
 
 
[width<nowiki> =</nowiki>  ]{mod11/graphics/auto_ptr.eps}
 
 
   
 
   
{Wskaźniki <tt>autoptr</tt>.}
+
  bool operator<nowiki> =</nowiki>   <nowiki> =</nowiki>   (const trivial_iterator&lhs) const {
+
     return this->_ptr<nowiki> =</nowiki>   <nowiki> =</nowiki>   lhs._ptr;
To bardzo nieintuicyjne zachowanie:
+
   }  
obiekty <code><nowiki> auto_ptr</nowiki></code> nie są modelami konceptu <code><nowiki> Assignable</nowiki></code>.
+
  bool operator!<nowiki> =</nowiki>  (const trivial_iterator&lhs) const {
Wskaźniki te zostały wprowadzone, aby wspomagać bezpieczną alokację
+
     return !operator<nowiki> =</nowiki>   <nowiki> =</nowiki>   (lhs);
zasobów (głównie pamięci), według wzorca "alokacja zasobów jest
+
  }
inicjalizacją" {Stroustrup}. Rozważmy następujący przykład:
 
 
 
<nowiki> int  f() {
 
  BigX *p  =     new BigX;
 
/*... tu coś się dzieje */
 
  delete  p;
 
  return wynik;
 
}
 
</nowiki>
 
 
 
To typowe zastosowanie dynamicznej alokacji pamięci.
 
Problem polega na tym, że jeżeli pomiędzy przydziałem pamięci a  jej
 
zwolnieniem coś się stanie, to będziemy mieli wyciek pamięci.  To coś,
 
to może być np. dodatkowe wyrażenie <code><nowiki> return</nowiki></code> lub rzucony wyjątek.
 
W obu przypadkach zniszczone zostaną wszystkie statycznie zaalokowane
 
obiekty w tym i wskaźnik <code><nowiki> p</nowiki></code>. Ale ponieważ jest to zwykły wskaźnik
 
jego zniszczenie nie spowoduje zwolnienia wskazywanej przez niego
 
pamięci. Rozwiązaniem jest właśnie uczynienie go obiektem będącym właścicielem
 
wskazywanej pamięci:
 
 
 
<nowiki> int  f() {
 
  auto_ptr<BigX> p(new BigX);
 
 
 
/*... tu coś się dzieje */
 
 
 
   return wynik;
 
}
 
</nowiki>
 
 
 
Teraz przy wyjściu z funkcji  zostanie wywołany destruktor <code><nowiki> p</nowiki></code>, a on
 
zwolni przydzieloną pamięć.
 
 
 
Wzkaźniki <code><nowiki> auto_ptr</nowiki></code> mogą być przekazywane i zwracane z funkcji.
 
Jeśli przekażemy <code><nowiki> auto_ptr</nowiki></code> do funkcji przez wartość, to
 
spowodowane tym kopiowanie spowoduje, że własność zostanie przekazana
 
na argument funkcji i pamięć zostanie zwolniona, kiedy funkcja
 
zakończy swoje działanie.
 
 
 
<nowiki> template<typename T> void val(T p) {
 
};
 
 
 
auto_ptr<X> px(new X);
 
val(px);
 
/* px zawiera wskaźnik null. pamięć jest zwolniona */
 
cout<<px.get()<<endl;
 
/* zwraca opakowany wskaźnik na X, powinnien być zero*/
 
</nowiki>
 
 
 
Jeśli przekażemy <code><nowiki> auto_ptr</nowiki></code> przez referencje, to kopiowania nie
 
będzie, przekazanie własności będzie zależeć od tego, czy wkaźnik
 
zostanie skopiowany lub przypisany wewnątrz funkcji.
 
 
 
<nowiki> template<typename T> void ref_1(T &p) {
 
   T x  =    p;
 
};
 
template<typename T> void ref_2(T &p) {
 
};
 
 
 
auto_ptr<X> px(new X);
 
ref_2(px);
 
/* nic sie nie zmieniło*/
 
cout<<px.get()<<endl; /* wypisuje jakiś adres*/
 
ref_1(px)
 
/* px zawiera wskaźnik null. pamięć jest zwolniona */
 
cout<<px.get()<<endl;
 
/* zwraca opakowany wskaźnik na X, powinnien być zero*/
 
</nowiki>
 
 
 
W przypadku przekazania <code><nowiki> auto_ptr</nowiki></code> jako referencji do stałej sprawa
 
jest bardziej skomplikowana. Obecny standard stanowi, że wskaźnik
 
<code><nowiki> auto_ptr</nowiki></code> przekazany jako referencja do stałej nie przekazuje
 
własności, tzn. operacje, które by to tego prowadziły nie powinny się
 
skompilować.  Z tych samych powodów nie powinien skompilować się kod
 
używający kontenerów STL zawierających wskaźniki <code><nowiki> auto_ptr</nowiki></code>.
 
 
 
<nowiki> template<typename T> void cref_1(const T &p) {
 
  T x  =     p;
 
};
 
template<typename T> void cref_2(const T &p) {
 
};
 
 
 
auto_ptr<X> px(new X);
 
cref_2(px);
 
/* OK, nic się nie stanie*/
 
cout<<px.get()<<endl; /* wypisuje jakiś adres*/
 
cref_1(px) /* nie skompiluje się */
 
 
 
std::vector<auto_ptr<X> > v(10); /* nie skompiluje się*/
 
/* {mod11/code/auto_ptr.cpp}{autoptr.cpp}*/
 
</nowiki>
 
 
 
Różne implementacje różnie sobie z tym radzą i w praktyce wynik
 
kompilowania powyższych fragmentów kodu może być różny na różnych
 
platformach.  Jest to dość techniczne zagadnienie, zainteresowane
 
osoby odsyłam do {szablony} i  {josuttis}.
 
 
 
==Kontrola dostępu==
 
 
 
Poza kontrolą rodzaju praw własności, inteligentny wskaźnik daje nam
 
możliwość kontroli nad operacjami dostępu do wskazywanego obiektu
 
poprzez operatory <code><nowiki> operator->()</nowiki></code> i <code><nowiki> operator*()</nowiki></code>.  Wpływać na
 
zachowanie tych operatorów możemy dwojako: po pierwsze, w oczywisty
 
sposób możemy wykonać dodatkowy kod, zanim zwrócimy z nich odpowiednią
 
wartość:
 
 
 
<nowiki> T &operator*() {
 
/* zrob coś */
 
return *_p;  
 
}
 
</nowiki>
 
 
 
Ten dodatkowy kod może np. sprawdzać, czy wskaźnik <code><nowiki> _p</nowiki></code> nie jest
 
zerowy, może zliczać wywołania, itp.
 
 
 
Po drugie, możemy zmienić zwracany typ. Wbudowane operatory <code><nowiki> *</nowiki></code> i
 
<code><nowiki> -></nowiki></code> zwracają odpowiednio <code><nowiki> T&</nowiki></code> i <code><nowiki> T*</nowiki></code>. Oczywiście my możemy
 
zwrócić cokolwiek, ale żeby to miało jakiś sens, powinny to być obiekty
 
zachowujące się jak <code><nowiki> T&</nowiki></code> i <code><nowiki> T*</nowiki></code>. Takie obiekty, które "zachowują
 
się jak coś", ale  tym  nie są (kwacze jak kaczka, ale to nie jest
 
kaczka) nazywamy obiektami zastępczymi (proxy).
 
 
 
===Proxy===
 
 
 
Dlaczego moglibyśmy chcieć używać obiektów zastępczych?
 
 
 
Typowe zastosowanie to implemenatacja operacji przypisania do obiektów,
 
które tak naprawdę obiektami nie są. Weźmy jako przykład
 
<code><nowiki> ostream_iterator</nowiki></code> dostarczany przez STL, który zezwala traktować
 
plik wyjściowy jak kontener z iteratorem typu <code><nowiki> OutputIterator</nowiki></code>:
 
 
 
<nowiki> vector<int> V(10,7);
 
copy(V.begin(), V.end(), ostream_iterator<int>(cout, ""));
 
</nowiki>
 
  
Przypatrzny się temu przykładowi bliżej. Jeśli zdefiniujemy
+
Potrzebna jest jeszcze deklaracja:
 
 
<nowiki> ostream_iterator<int>(cout, "") iout;
 
</nowiki>
 
 
 
to w zasadzie jedyną dozwoloną operacją jest przypisanie i zwiększenie
 
następujące po sobie:
 
 
 
<nowiki> (*iout)  =    666; ++iout;
 
</nowiki>
 
 
 
Ewidentnie nie istnieje żaden obiekt, do którego referencje moglibyśmy
 
zwrócić. Możemy jednak zwrócić obiekt zastępczy, który będzie
 
definiował operator przypisania:
 
 
 
<nowiki> class writing_proxy {
 
    std::ostream &_out;
 
  public:
 
    writing_proxy(std::ostream &out) :_out(out) {};
 
   
 
    void operator  =    (const T &val) {
 
      _out<<val;
 
    }
 
  };
 
/* {mod11/code/out.cpp}{out.cpp} */
 
</nowiki>
 
 
 
Tę klasę zamkniemy wewnątrz klasy <code><nowiki> ostream_iterator</nowiki></code>
 
 
 
<nowiki> template<typename T> class ostream_iterator:
 
public std::iterator <std::output_iterator_tag, T >  {
 
 
 
  class writing_proxy {
 
  /*...*/
 
  };
 
 
   
 
   
  std::string _sep;
+
  friend class binary_tree;     
  std::ostream &_out;
 
  writing_proxy _proxy;
 
public:
 
  ostream_iterator(std::ostream &out,std::string sep):
 
    _out(out),_sep(sep),_proxy(_out){};
 
  void operator++()   {_out<<_sep;}
 
  void operator++(int) {_out<<_sep;}
 
  writing_proxy &operator*() {return _proxy;};
 
};
 
/* {mod11/code/out.cpp}{out.cpp} */
 
</nowiki>
 
 
 
Dziedziczenie z klasy <code><nowiki> iterator</nowiki></code> zapewni nam, że nasz
 
<code><nowiki> ostream_iterator</nowiki></code> posiada wszystkie typy stowarzyszone wymagane
 
przez iteratory STL. To z kolei pociąga za sobą możliwość użycia
 
<code><nowiki> iterator_traits</nowiki></code>(zobacz [[##lbl:iterator-traits|Uzupelnic lbl:iterator-traits|]]). Bez tego nie
 
moglibyśmy używać <code><nowiki> ostream_iterator</nowiki></code> w niektórych algorytmach STL. 
 
 
 
Teraz możemy juz używać wyrażeń typu:
 
  
<nowiki> ostream_iterator<int> io(std::cout,"");
+
żeby klasa <tt>binary_tree</tt> mogła korzystać z konstruktora
(*io) =    44;
+
<tt>iterator(node *ptr)</tt>.
/* {mod11/code/out.cpp}{out.cpp} */
 
</nowiki>
 
  
Wywołanie <code><nowiki> *io</nowiki></code> zwraca <code><nowiki> writing_proxy</nowiki></code>. Następnie wywoływany
+
W klasie <tt>binary_tree</tt> definiujemy funkcje:
jest
 
  
<nowiki> writing_proxy::operator  =    (44)}
+
  iterator begin() {return iterator(_root);}
</nowiki>
+
  iterator end(){return iterator(0);}
 +
</div></div>
  
który wykonuje operację
+
{{cwiczenie|6||
 
+
Dodaj do drzewa instrukcje pozwalające na jego budowanie:
<nowiki> std::cout<<44;
 
</nowiki>
 
 
 
Widać też, że operacja
 
 
 
<nowiki> i  =    (*io)
 
</nowiki>
 
 
 
nie powiedzie się (nie skompiluje). W tym przypadku jest to pożądane
 
zachowanie, bo taka operacja nie ma sensu.  Jeślibyśmy jednak
 
chcieli umożliwić działanie operacji przypisania w drugą stronę możemy
 
w obiekcie proxy zdefiniować operator konwersji na typ <code><nowiki> T</nowiki></code>.
 
 
 
<nowiki> operator T() {return T();}; /* uwaga bzdurny przykład !!! */
 
</nowiki>
 
 
 
Wtedy wykonanie
 
 
 
<nowiki> i  =    (*io)
 
</nowiki>
 
 
 
przypisze zero do zmiennej <code><nowiki> i</nowiki></code>. W ten sposób obiekty proxy
 
pozwalają nam rozróżniać użycie operatora <code><nowiki> *</nowiki></code> do odczytu i do
 
zapisu.
 
 
 
Obiekty zastępcze stanowią zresztą często spotykany wzorzec projektowy
 
(zobacz {gamma}). Poniżej przedstawię jeszcze jedną "sztuczkę"
 
opisaną w {alexandrescu}.
 
 
 
===Opakowywanie wywołań funkcji===
 
 
 
Załóżmy, że mamy obiekt typu:
 
 
 
<nowiki> struct Widget {
 
  void pre() {cout<<"pre"<<endl;};
 
  void post() {cout<<"post"<<endl;};
 
 
 
  void f1() {cout<<"f1"<<endl;}
 
  void f2() {cout<<"f2"<<endl;}
 
/*{mode11/code/pre_post.cpp}{prepost.cpp} */
 
}
 
</nowiki>
 
 
 
Niech
 
 
 
<nowiki> Smart_prt<Widget> pw(new Widget);
 
</nowiki>
 
 
 
będzię  inteligentnym wskaźnikiem do <code><nowiki> Widget</nowiki></code>.
 
Chcemy, aby każde wywołanie funkcji z <code><nowiki> Widget</nowiki></code> np.
 
 
 
<nowiki> pw->f1()
 
</nowiki>
 
 
 
zostało poprzedzone poprzez wywołanie funkcji <code><nowiki> pre()</nowiki></code>, a po nim
 
nastąpiło wywołanie funkcji <code><nowiki> post()</nowiki></code>.  Jedną z możliwości jest
 
oczywiście zmiana kodu funkcji <code><nowiki> f1</nowiki></code> i <code><nowiki> f2</nowiki></code>,
 
tak aby wywoływały na początku
 
<code><nowiki> pre()</nowiki></code> i <code><nowiki> post()</nowiki></code> na końcu. Można też dodać zestaw funkcji
 
opakowywujących:
 
 
 
<nowiki> f1_wrapper() {pre();f1();post();}
 
</nowiki>
 
 
 
Jest to jednak niepotrzebne duplikowanie kodu i możliwe do
 
zastosowania tylko jeśli mamy możliwość zmiany kodu klasy <code><nowiki> Widget</nowiki></code>.
 
 
 
Można jednak zrobić inaczej. Zdefiniujemy pomocniczą klasę:
 
 
 
<nowiki> template<typename T> struct Wrapper {
 
  T* _p;
 
  Wrapper(T* p):_p(p) {_p->pre();}
 
  &nbsp;Wrapper()          {_p->post();}
 
 
 
  T*  operator->() {return _p;}
 
};
 
/*{mode11/code/pre_post.cpp}{prepost.cpp} */
 
</nowiki>
 
 
 
W klasie inteligentnego wskaźnika przedefiniujemy <code><nowiki> operator->()</nowiki></code>
 
tak, aby zwracał <code><nowiki> Wrapper<T>(T *)</nowiki></code> zamiast<code><nowiki> T*</nowiki></code>.
 
 
 
<nowiki> template<typename T> struct Smart_ptr {
 
  T *_p;
 
  Smart_ptr(T *p):_p(p) {};
 
  &nbsp;Smart_ptr(){delete _p;};
 
 
 
  Wrapper<T> operator->()  {return Wrapper<T>(_p);};
 
  T &operator*() {return *_p};
 
  /*{mode11/code/pre_post.cpp}{prepost.cpp} */
 
};
 
</nowiki>
 
 
 
Jeśli teraz wywołamy
 
 
 
<nowiki> pw->f1();
 
</nowiki>
 
 
 
to będą się dziać następujace rzeczy:
 
* zostanie wywołany
 
 
 
<nowiki> pw.operator->();
 
</nowiki>
 
 
 
operator ten zwraca obiekt <code><nowiki> tmp</nowiki></code> typu <code><nowiki> Wrapper<Widget></nowiki></code>, ale
 
najpier musi go skonstruować, a więc
 
* zostanie wywołany konstruktor
 
 
 
<nowiki> tmp  =    Wrapper<Widget>(p);
 
</nowiki>
 
 
 
który wywoła
 
 
 
<nowiki> p->pre();
 
</nowiki>
 
* Jeśli <code><nowiki> operator->()</nowiki></code>, zwróca obiekt który posiada
 
  <code><nowiki> operator->()</nowiki></code>, to jest on wywoływany rekurencyjnie, aż zostanie
 
  zwrócony typ wskaźnikowy. Tak więc zostanie wywołany
 
<code><nowiki> tmp.operator->()</nowiki></code> który zwróci <code><nowiki> p</nowiki></code>.
 
* Poprzez ten wskaźnik zostanie wywołana funkcja
 
 
 
<nowiki> p->f1();
 
</nowiki>
 
* Zakończy się wywołanie <code><nowiki> pw.operator->()</nowiki></code>, a więc zostanie
 
  wywołany destruktor obiektu tymczasowego <code><nowiki> tmp</nowiki></code> który wywoła
 
 
 
<nowiki> p->post();
 
</nowiki>
 
 
 
Widać więc, że w końcu zostanie wykonana sekwencja wywołań:
 
 
 
<nowiki> p->pre();
 
p->f1();
 
p->post();
 
</nowiki>
 
 
 
i tak będzie dla dowolnej wywoływanej metody.
 
Jesli jednak wywołamy funkcję <code><nowiki> f1()</nowiki></code> za pomocą wyrażenia:
 
 
 
<nowiki> (*pw).f1();
 
</nowiki>
 
 
 
to ten mechanizm nie zadziała i nie ma możliwości, aby go w tej sytuacji
 
zaimplementować. Może to być traktowane jako wada, bo nie jesteśmy w
 
stanie zapewnić, że każde wywołanie funkcji zostanie opakowane, ale z
 
drugiej strony mamy, do dyspozycji możliwość wyboru pomiędzy opakowanym
 
i nieopakowanym wywołaniem funkcji.
 
 
 
==Współdzielenie reprezentacji==
 
 
 
Opisując inteligentne skaźniki, nie można nie wspomnieć o technice
 
implementacyjnej, która jest ściśle z nimi związana, a mianowicie o
 
współdzieleniu reprezentacji. Technika ta polega na oddelegowaniu
 
całego (lub prawie całego) zachowania klasy do innego obiektu,
 
nazywanego reprezentacją, a  w obiekcie klasy przechowywanie tylko uchwytu
 
do reprezentacji (zob rysunek&nbsp;[[##fig:cow|Uzupelnic fig:cow|]]).
 
[p]
 
 
   
 
   
{}
+
  iterator add_root(const T &val);
   
+
  iterator add_left(iterator  it, const T &val);
  <nowiki> class Wichajster {
+
iterator add_right(iterator it, const T &val);
public:
 
void do_something() {_rep->do_something();}
 
private:
 
  WichajsterRep _rep; 
 
}
 
</nowiki>
 
  
Techniki tej używamy np.  kiedy chcemy oszczędzić czas i miejsce
+
które tworzą nowy węzeł drzewa z wartością <tt>val</tt> i wstawiają go
potrzebne na kopiowanie obiektów. Kilka kopi obiektów klasy
+
odpowiednio jako wierzchołek drzewa lub jako lewe lub prawe dziecko
<code><nowiki> Wichajster</nowiki></code> może współdzielić jedną reprezentację, korzystając np.
+
wierzchołka wskazywanego przez <tt>it</tt>. Jeśli ktoryś z tych nowych
ze zliczania referencji. Istotną różnicą w stosunku do inteligentnych
+
elementów już istnieje to jest rzucany wyjątek.
wskaźników jest zachowanie w przypadku zmiany jednego z obiektówW
+
Funkcje <tt>add</tt> zwracają iterator do nowo wstawionego elementu.
przypadku wskaźników, współdzielenie referencji jest planowaną cechą
+
}}
podejścia: kiedy zmieniamy obiekt poprzez jeden ze  wskaźników,  
+
{{uwaga| ||
wszystkie inne wskaźniki wskazują na zmieniony obiekt.  
+
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 iteratoraZapewnienie 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>.
  
W przypadku współdzielenia reprezentacji chcemy cały czas rozróżniać
+
Klasa <tt>trivial iterator</tt> jest modelem konceptu <tt>TrivialIterator</tt> i
obiekty, współdzielenie jest tylko technicznym środkiem optymalizacji.
+
realizuje tylko dostęp do wierzchołka. Natomiast klasa <tt>iterator</tt>  
Wymaga to zastosowania techniki "copy on write", tzn. w momencie, w
+
dziedziczy z <tt>trivial_iterator</tt> i uzupełnia go o funkcję
którym dokonujemy na obiekcie operacji mogącej go zmienić i jeśli
+
przechodzenia do następnego elementu. Definicje funkcji <tt>add_...</tt> zmienimy na:
posiada on współdzieloną reprezentację, to tworzymy nową fizyczna
 
kopię tej reprezentacji i dopiero ją zmieniamy. Przedstawione to jest
 
na rysunku&nbsp;[[##fig:cow|Uzupelnic fig:cow|]].
 
 
 
W przypadku metod łatwo stwierdzić, które zmieniaja obiekt, a które nie;
 
problem występuje tylko z metodami które zwracaja referencje do wnętrza
 
obiektu. Takie metody mogą służyć zarówno do zapisu jak i do odczytu.
 
Cześciowym rozwiązaniem może być użycie obiektów proxy, tak jak to
 
opisano w poprzednim podrozdziale. Szczegółowy opis tej techniki
 
znajduje się w {MeyersMECPP}.
 
 
 
==Iteratory==
 
 
 
Iteratory to kolejny rodzaj inteligentnych wskaźników. Jeżli chodzi o
 
prawa własności czy kontrolę dostępu, to w większości zachowują się jak
 
zwykłe wskaźniki. Wyjątkiem są specjalne iteratory takie, jak
 
<code><nowiki> ostream_iterator</nowiki></code>, czy <code><nowiki> back_inserter</nowiki></code>, wspomniane powyżej.
 
Ale zasadniczo inteligencja iteratorów umiejscowiona jest w operacjach
 
arytmetycznych. Chodzi głównie o operator <code><nowiki> operator++()</nowiki></code>, ponieważ
 
wyposażone są w niego wszystkie iteratory kontenerów z STL.  To
 
właśnie jest zresztą podstawowa rola iteratora: przechodzenie do
 
kolejnych elementów, semantyka wskaźnika to już wybór twórców STL.
 
 
 
==Implementacje==
 
 
 
Widać, że różnorodność inteligentnych wskaźników może przyprawić o
 
zawrót głowy. A nie rozważyliśmy jeszcze wszystkich kwestii
 
dotyczących ich zachowania. Wyczerpująca dyskusja na ten
 
temat znajduje się w {alexandrescu}. Tam też podana jest
 
implemenatcja uniwersalnego szablonu klasy inteligentnego wskaźnika
 
parametryzowanego kilkoma klasami wytycznymi. Alternatywą jest użycie
 
szeregu klas (szablonów) implementujacych jeden typ wskaźnika każda.
 
Zbiór takich klas można znaleźć w bibliotece <code><nowiki> boost</nowiki></code>  
 
({<math>\displaystyle BOOST_LIBS/smart_ptr/smart_ptr.htm}{smart\_ptr}).
 
Bardzo dobre opisy implementacji inteligentnych wskaźników znajdują
 
się również w \cite{szablony} i \cite{MeyersMECPP}. 
 
 
 
Tutaj dla przykładu zaprezentuję implementację wskaźnika zliczającego
 
referencję, parametryzowanego jedną klasą wytyczną. Jest to podejście
 
zbliżone do \cite{szablony}.
 
 
 
==Zliczanie  referencji==
 
 
 
Implementacje zliczanie referencji różnią się przede wszystkim
 
miejscem, w którym umieszczony zostanie licznik. Dwie główne możliwości
 
to wewnątrz lub na zewnątrz obiektu, na który wskazujemy. Pierwszy
 
wariant jest ewidentnie możliwy tylko wtedy, jeśli mamy dostęp do
 
kodu tej klasy. W każdej z tych dwu grup  mamy dalsze możliwości np:
 
\beginfigure
 
\begincenter
 
\includegraphics[width=\floatwidth]{mod11/graphics/counter.eps}
 
\endcenter
 
\caption{Wkaźniki ze współdzielniem referencji.}
 
\endfigure
 
# Obiekt wskazywany udostępnia miejsce na licznik, zarządzaniem licznikiem
 
zajmuje się wskaźnik
 
# Obiekt wskazywany udostępnia nie tylko licznik, ale i interfejs do
 
zarządzania nim.
 
# Licznik jest osobnym obiektem. Każdy wskaźnik posiada wskaźnik
 
  na obiekt wskazywany i wskaźnik na licznik (zobacz
 
  rysunek~[[##fig:counter|Uzupelnic fig:counter|]]).
 
# Licznik jest osobnym obiektem który zawiera również wskaźnik do
 
  obiektu wskazywanego. Każdy wskaźnik zawiera tylko wskaźnik do
 
  licznika (zobacz rysunek~[[##fig:counter|Uzupelnic fig:counter|]]).
 
# Nie ma licznika, wskaźniki do tego samego obiektu połączone są w
 
  listę (zobacz rysunek~[[##fig:counter|Uzupelnic fig:counter|]]).
 
 
   
 
   
Pokażę teraz przykładową implementację szablonu wskaźnika
+
trivial_iterator add_root(const T &val);
parametryzowanego jedną klasą wytyczną określającą którąś z powyższych
+
trivial_iterator add_left(trivial_iterator it, const T &val);
strategii, aczkolwiek przy jednej wytycznej jest to wysiłek który
+
trivial_iterator add_right(trivial_iterator it, const T &val);
pewnie się nie opłaca, jako że kod wspólny jest dość mały. Ale
+
}}
implementacja ta może stanowić podstawę do rozszerzenia o kolejne
+
<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">
wytyczne.
+
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.
Najpierw musimy się zastanowić na interfejsem lub raczej konceptem
 
klasy wytycznej. W sumie najłatwiej to zrobić, implemetując konkretną
 
wytyczną. Zaczniemy od osobnego zewnętrznego licznika
 
(strategia~[[##lbl:external|Uzupelnic lbl:external|]]). 
 
Klasa wytyczna musi zawierać wsaźnik do wspólnego licznika:
 
 
 
<nowiki> template<typename T> struct Extra_counter_impl {
 
/*...*/
 
private:
 
  size_t *_c;
 
};
 
</nowiki>
 
  
i funkcje zwiększające i zmniejszające licznik:
+
Druga to
 
 
<nowiki> public:
 
  bool remove_ref()    {--(*_c);return *_c==0;};
 
  void add_ref()      {++(*_c);};
 
  size_t count() {return *_c;};
 
};
 
</nowiki>
 
 
 
Funkcja zmniejszająca licznik zwraca prawdę, jeśli usunięta została
 
ostatnia referencja do wskazywanego obiektu. Potrzebna też będzie
 
funkcja niszcząca licznik:
 
 
 
<nowiki> void cleanup() {
 
    delete _c;
 
    _c=0;
 
  }
 
</nowiki>
 
 
 
Potrzebne będą dwa konstruktory: defaultowy, który nic nie robi:
 
 
 
<nowiki> Extra_counter_impl():_c(0)                    {};
 
</nowiki>
 
 
 
i  konstruktor inicjalizujący licznik obiektu powstającego po raz pierwszy:
 
 
 
<nowiki> Extra_counter_impl(T* p):_c(new size_t) {*_c=0;};
 
</nowiki>
 
 
 
który przydziela pamięć dla licznika. Argument <code><nowiki> T* p</nowiki></code> służy tylko
 
do rozróżnienia tych konstruktorów.
 
 
 
Korzystając z tej klasy nietrudno jest, napisać szablon inteligentnego
 
wskaźnika. Obiekt klasy <code><nowiki> Extra_counter_impl</nowiki></code>  może być składową
 
tego szablonu lub możemy z tej klasy wytycznej
 
dziedziczyć (zob~[[##lbl:wytyczne|Uzupelnic lbl:wytyczne|]]).
 
 
 
Niestety, przy tak zdefiniowanym interfejsie do klasy wytycznej,
 
bedziemy mieli problem próbując zaimplementować inne strategie, w
 
szczególności strategię w której licznik i wskaźnik na obiekt
 
wskazywany znajdują się w tym samym obiekcie
 
(strategia~[[##lbl:indirect|Uzupelnic lbl:indirect|]]). Dlatego zmienimy trochę naszą
 
implementację wytycznej i założymy, że obiekty tej klasy będą
 
zawierać również wskaźnik na obiekt wskazywany.
 
 
 
<nowiki> T *_p;
 
</nowiki>
 
 
 
i dodamy funkcję
 
 
 
<nowiki> T* pointee() {return _p;}
 
</nowiki>
 
 
 
Musimy jeszcze poprawić funkcję czyszczącą:
 
 
 
<nowiki> void cleanup() {
 
    delete _c;
 
    delete _p;
 
    _p=0;
 
  }
 
/* \href{mod11/code/ref_ptr.h}{ref\_ptr.h} */
 
</nowiki>
 
 
 
I jeden z konstruktorów:
 
 
 
<nowiki> Extra_counter_impl(T* p):_c(new size_t),_p(p) {*_c=0;};
 
</nowiki>
 
 
 
Szablon wskaźnika korzystający z tak zdefiniowanej klasy wytycznej może
 
wyglądać następująco:
 
 
 
<nowiki> template<typename T,
 
        typename counter_impl = Extra_counter_impl<T>  >
 
class Ref_ptr {
 
public:
 
  Ref_ptr() {};
 
  Ref_ptr(T *p):_c(p) {
 
    _c.add_ref();
 
  };
 
 
 
  ~Ref_ptr() {detach();}
 
 
 
  Ref_ptr(const Ref_ptr &p):_c(p._c) {
 
    _c.add_ref();
 
  }
 
 
 
  Ref_ptr &operator=(const Ref_ptr &rhs) {
 
    if(this!=&rhs) {
 
      detach();
 
      _c=rhs._c;
 
      _c.add_ref();
 
    }
 
    return *this;
 
  }
 
 
    
 
    
  T* operator->() {return _c.pointee();}
+
  class iterator: public trivial_iterator ;
  T &operator*() {return *(_c.pointee());}
 
  
  size_t count() {return _c.count();};
+
zawierająca pole <tt>_nodes</tt> i operatory <tt>++</tt>.
private:
 
  mutable counter_impl _c;
 
  void detach() {     
 
    if (_c.remove_ref() ) _c.cleanup();
 
  };
 
};
 
/* \href{mod11/code/ref_ptr.h}{ref\_ptr.h} */
 
</nowiki>
 
  
==auto\_ptr==
+
Funkcje <tt>insert_</tt> są już łatwe do zaimplementowania, np.:
  
Implementacja wskaźnika <code><nowiki> auto_ptr</nowiki></code> oparta jest o dwie funkcje.
+
  trivial_iterator insert_right(trivial_iterator it,const T &val) {
Jedna zwalnia przechowywany wskaźnik zwracając go na zewnątrz i
+
    if(!it._ptr->_right)
oddając własność:
+
      it._ptr->_right <nowiki> =</nowiki>   new node(val);
 
+
     return trivial_iterator(it._ptr->_right);
<nowiki> T* release() {
 
    T *oldPointee = pointee;
 
    pointee = 0;
 
     return oldPointee;
 
 
   }
 
   }
/* \href{mod11/code/auto_ptr.h}{auto\_ptr.h} */
 
</nowiki>
 
 
<code><nowiki> pointee</nowiki></code> jest przechowywanym (zwykłym) wskaźnikiem.
 
 
<nowiki> private:
 
  T *pointee;
 
</nowiki>
 
 
Druga funkcja zamienia przechowywany wskaźnik na inny, zwalnianiając
 
wskazywaną przez niego pamięć:
 
 
<nowiki> void reset(T *p = 0)  {
 
    if (pointee != p) {
 
      delete pointee;
 
      pointee = p;
 
    }
 
  }
 
/* \href{mod11/code/auto_ptr.h}{auto\_ptr.h} */
 
</nowiki>
 
 
Za pomocą tych funkcji można już łatwo zimplementować resztę szablonu np.:
 
 
<nowiki> template<class T> class auto_ptr {
 
public:
 
  explicit auto_ptr(T *p = 0): pointee(p) {}
 
 
  template<class U>
 
  auto_ptr(auto_ptr<U>& rhs): pointee(rhs.release()) {}
 
 
  ~auto_ptr() { delete pointee; }
 
 
 
  template<class U>
 
  auto_ptr<T>& operator=(auto_ptr<U>& rhs)
 
  {
 
    if (this != &rhs) reset(rhs.release());
 
    return *this;
 
  }
 
 
  T& operator*() const { return *pointee; }
 
  T* operator->() const { return pointee; }
 
  T* get() const { return pointee; }
 
}
 
/* \href{mod11/code/auto_ptr.h}{auto\_ptr.h} */
 
</nowiki>
 
 
Konstruktor kopiujacy i operator przypisania są szablonami. W ten
 
sposób można kopiować również wskaźniki <code><nowiki> auto_ptr</nowiki></code> opakowywujące
 
typy,  które mogą być na siebie rzutowane np. można przypisać
 
<code><nowiki> auto_ptr<Derived></nowiki></code> do <code><nowiki> auto_ptr<Base></nowiki></code>, jeśli <code><nowiki> Derived</nowiki></code>
 
dziedziczy publicznie z <code><nowiki> Base</nowiki></code>.  Konstruktor <code><nowiki> auto_ptr(T *p =
 
  0)</nowiki></code> został zadeklarowany jako <code><nowiki> explicit</nowiki></code>, wobec czego nie
 
spowoduje niejawnej konwersji z typu <code><nowiki> T*</nowiki></code> na <code><nowiki> auto_ptr<T></nowiki></code>.
 
  
Różne impelentacje <code><nowiki> auto_ptr</nowiki></code> różnią się szczegułami dotyczącymi
+
Całość kodu jest zamieszczona w pliku [[media:Binary_tree.h | binary_tree.h]].
obsługi <code><nowiki> const auto_ptr</nowiki></code> i przekazywania <code><nowiki> auto_ptr</nowiki></code> przez stałą
+
</div></div>
referencję. Powyższa implentacja wzięta, z \cite{MeyersMECPP}, nie
 
posiada pod tym względem żadnych zabezpieczeń. Szczegółowa dyskusja
 
tego zagadnienia i bardziej zaawansowana implementacja znajduje się w
 
\cite{josuttis}. Temat ten jest też poruszony w \cite{szablony}.
 
Warto też zaglądnąć do implementacji <code><nowiki> auto_ptr</nowiki></code> dostarczonej z
 
wraz z kompilatorem <code><nowiki> g++</nowiki></code>.</math>
 

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