Tekst źródłowy strony Zaawansowane CPP/Ćwiczenia 2: Programowanie uogólnione

Dla większości programistów pierwszym poważnym kontaktem z technikami
programowania uogólnionego jest próba wykorzystania w swoim własnym
kodzie pojemników STL.
STL czyli Standard Template Library jest, jak sama nazwa wskazuje,
oficjalną częścią standardu języka C++ i jako taka jest zawsze dostępna.
Zawiera implementacje typowych struktur danych (listy, kolejki, tablice
haszujące, itd.).
Ciężko wyobrazić sobie jakikolwiek większy program, który nie posługiwałby
się przynajmniej jedną z tych klasycznych struktur.

Jak z powyższego wynika, STL warto poznać.
Oficjalna dokumentacja jest częścią standardu C++, natomiast w praktyce
zerka się zazwyczaj na witrynę [http://www.sgi.com/tech/stl/ http://www.sgi.com/tech/stl/].
Uwaga - ta witryna opisuje pewną konkretną wersję STL, zaimplementowaną
przez programistów z firmy SGI i zawierającą nieco więcej klas niż
przewiduje standard.

Podczas rozwiązywania poniższych zadań proszę zwrócić uwagę na sposób,
w jaki przekazywane są argumenty funkcji. Rzeczy, co do których mamy
pewność, że zajmują nie więcej niż kilka bajtów (iteratory, funktory) są
przekazywane przez wartość; rzeczy o nieznanym z góry rozmiarze (elementy
przechowywane w pojemnikach) są przekazywane przez referencję albo
referencję do stałej.

{{cwiczenie|1||

Zapoznaj się z dokumentacją pojemników vector oraz list, a następnie
spróbuj napisać jakiś prosty programik, wykorzystujący co najmniej 50% metod oferowanych przez te klasy.
Programik nie musi robić niczego specjalnie pożytecznego.
W przypadku niedostatku fantazji jako punkt startowy możesz wykorzystać
plik [[media:Zabawa_z_stl.cpp | zabawa_z_stl.cpp]].
}}
{{cwiczenie|2||
 
Zastanów się, dlaczego lista ma metodę <code><nowiki>push_front()</nowiki></code> ,
a wektor nie - przecież dałoby się ją dla niego zaimplementować.
}}
<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">
Jak by musiała wyglądać ta implementacja i w jakim czasie by się wykonywała?
</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">
W STL przyjęto, że <tt>push_front()</tt> ma obowiązek w amortyzowanym czasie O(1). Jeśli wewnętrzna struktura danych pojemnika tego nie umożliwia (np. wektor tego nie umożliwia), to metody się nie implementuje - lepiej aby jej w ogóle nie było, niż gdyby miała być nieoptymalna. W ten sposób żaden programista przez pomyłkę z niej nie skorzysta w swoim bardzo ważnym projekcie, od którego zależy cała jego dalsza kariera.
</div></div>

{{cwiczenie|3||
 
Metoda <code><nowiki>push_front()</nowiki></code>  wykonywana w czasie stałym jest częścią konceptu
FrontInsertionSequence.
Zajrzyj do wykładu, aby przypomnieć sobie hierarchię konceptów
opisujących pojemniki; następnie sprawdź jakie operacje z jaką złożonością
są zdefiniowane przez poszczególne koncepty.
Odpowiednie informacje możesz znaleźć m.in. na witrynie SGI.
}}
{{cwiczenie|4||
 
Oprócz uogólnionych pojemników STL dostarcza również uogólnionych funkcji
działających na ciągach elementów, tzw. algorytmy.
Ciąg przekazuje się do funkcji za pomocą dwóch iteratorów, wskazujących
na jego początek i za jego koniec.
Zaimplementuj algorytm <code><nowiki>wypisz_na_cout()</nowiki></code>,  robiący dokładnie to, na co
jego nazwa wskazuje; przetestuj go na którymś z pojemników STL oraz
na zwykłej tablicy.
Czy jesteś w stanie powiedzieć jakie typy będą użyte podczas konkretyzacji
tego szablonu?
}}
<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 4 </span><div class="mw-collapsible-content" style="display:none">
Patrz plik [[media:Wypisywanie.cpp | wypisywanie.cpp]].
Szablon konkretyzowany jest dwa razy, raz jako
<code><nowiki>wypisz_na_cout<std::vector<int>::iterator></nowiki></code> ,
drugi raz jako <code><nowiki>wypisz_na_cout<int *></nowiki></code> .
</div></div>

{{cwiczenie|5||
 
Wykład krótko wspomina o funktorach, czyli obiektach wyglądających
syntaktycznie tak jak funkcje.
Są one przydatne m.in. wtedy, gdy chcemy napisać uogólniony algorytm
coś robiący, ale nie wiemy z góry co to będzie.
Rozważmy szablon funkcji, która przechodzi przez ciąg elementów i dla
każdego elementu spełniającego pewien warunek wykonuje pewną czynność.
Jak widać, chcemy mieć możliwość przekazania z zewnątrz zarówno warunku,
jak i czynności.
Wyglądać to może na przykład tak:

 <nowiki>     template <typename Iter, typename Cond, typename Oper>
     void wykonaj_na_spełniających(Iter początek, Iter za_końcem,
             Cond warunek, Oper czynność)</nowiki>
Zaimplementuj algorytm o takiej sygnaturze.
}}
<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">
Patrz plik [[media:Funktory.cpp | funktory.cpp]].
</div></div>

{{cwiczenie|6||
 
Spróbuj zaimplementować swój własny pojemnik wyposażony w iterator.
Oprzyj go o dynamicznie tworzoną listę pojedynczo wiązaną.
Stosuj się do konwencji przyjętych w STL, ale nie musisz implementować
wszystkich metod znajdujących się w <code><nowiki> std::list</nowiki></code> , wystarczy jedna
operacja dodająca elementy do listy oraz <code><nowiki> begin()</nowiki></code>  i <code><nowiki> end()</nowiki></code> .
Skup się za to na implementacji iteratora i upewnij się, że udostępnia on
wszystkie operacje przewidziane w koncepcie ForwardIterator.
}}
<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">
Patrz plik [[media:Lista.h | lista.h]].
</div></div>

{{cwiczenie|7||
 
Zaimplementuj test, który sprawdza czy dany iterator rzeczywiście spełnia
wszystkie wymagania konceptu ForwardIterator.
Wykorzystaj metodę zaprezentowaną podczas wykładu (w podrozdziale
"Debugowanie").
Następnie użyj tego testu na iteratorach STL oraz na swoim własnym,
stworzonym w poprzednim zadaniu.
}}
<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">
Patrz plik [[media:Test_konceptu.cpp | test_koceptu.cpp]]. Aby go skompilować, musisz mieć zainstalowane biblioteki [http://www.boost.org/ <tt>boost</tt>].
</div></div>