Zaawansowane CPP/Ćwiczenia 2: Programowanie uogólnione: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 11: Linia 11:
 
Jak z powyższego wynika, STL warto poznać.
 
Jak z powyższego wynika, STL warto poznać.
 
Oficjalna dokumentacja jest częścią standardu C++, natomiast w praktyce
 
Oficjalna dokumentacja jest częścią standardu C++, natomiast w praktyce
zerka się zazwyczaj na witrynę <code><nowiki> http://www.sgi.com/tech/stl/</nowiki></code> .
+
zerka się zazwyczaj na witrynę <code><nowiki>http://www.sgi.com/tech/stl/</nowiki></code> .
Uwaga -- ta witryna opisuje pewną konkretną wersję STL, zaimplementowaną
+
Uwaga - ta witryna opisuje pewną konkretną wersję STL, zaimplementowaną
 
przez programistów z firmy SGI, i zawierającą nieco więcej klas niż
 
przez programistów z firmy SGI, i zawierającą nieco więcej klas niż
 
przewiduje standard.
 
przewiduje standard.
Linia 28: Linia 28:
 
Programik nie musi robić niczego specjalnie pożytecznego.
 
Programik nie musi robić niczego specjalnie pożytecznego.
 
W przypadku niedostatku fantazji jako punkt startowy możesz wykorzystać
 
W przypadku niedostatku fantazji jako punkt startowy możesz wykorzystać
plik <code><nowiki> zabawa_z_stl.cpp</nowiki></code> .
+
plik <code><nowiki>zabawa_z_stl.cpp</nowiki></code> .
  
 
'''Zadanie 2 '''  
 
'''Zadanie 2 '''  
Zastanów się, dlaczego lista ma metodę <code><nowiki> push_front()</nowiki></code> ,
+
Zastanów się, dlaczego lista ma metodę <code><nowiki>push_front()</nowiki></code> ,
a wektor nie -- przecież dałoby się ją dla niego zaimplementować.
+
a wektor nie - przecież dałoby się ją dla niego zaimplementować.
  
 
'''Podpowiedź do zadania 2 '''  
 
'''Podpowiedź do zadania 2 '''  
Linia 38: Linia 38:
  
 
'''Zadanie 3 '''  
 
'''Zadanie 3 '''  
Metoda <code><nowiki> push_front()</nowiki></code>  wykonywana w czasie stałym jest częścią konceptu
+
Metoda <code><nowiki>push_front()</nowiki></code>  wykonywana w czasie stałym jest częścią konceptu
 
FrontInsertionSequence.
 
FrontInsertionSequence.
 
Zajrzyj do wykładu, aby przypomnieć sobie hierarchię konceptów
 
Zajrzyj do wykładu, aby przypomnieć sobie hierarchię konceptów
Linia 50: Linia 50:
 
Ciąg przekazuje się do funkcji za pomocą dwóch iteratorów, wskazujących
 
Ciąg przekazuje się do funkcji za pomocą dwóch iteratorów, wskazujących
 
na jego początek i za jego koniec.
 
na jego początek i za jego koniec.
Zaimplementuj algorytm <code><nowiki> wypisz_na_cout()</nowiki></code>  robiący dokładnie to, na co
+
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
 
jego nazwa wskazuje; przetestuj go na którymś z pojemników STL oraz
 
na zwykłej tablicy.
 
na zwykłej tablicy.
Linia 57: Linia 57:
  
 
'''Rozwiązanie 4 '''  
 
'''Rozwiązanie 4 '''  
Patrz plik <code><nowiki> wypisywanie.cpp</nowiki></code> .
+
Patrz plik <code><nowiki>wypisywanie.cpp</nowiki></code> .
 
Szablon konkretyzowany jest dwa razy, raz jako
 
Szablon konkretyzowany jest dwa razy, raz jako
<code><nowiki> wypisz_na_cout<std::vector<int>::iterator></nowiki></code> ,
+
<code><nowiki>wypisz_na_cout<std::vector<int>::iterator></nowiki></code> ,
drugi raz jako <code><nowiki> wypisz_na_cout<int *></nowiki></code> .
+
drugi raz jako <code><nowiki>wypisz_na_cout<int *></nowiki></code> .
  
 
'''Zadanie 5 '''  
 
'''Zadanie 5 '''  
Linia 71: Linia 71:
 
Jak widać, chcemy mieć możliwość przekazania z zewnątrz zarówno warunku,
 
Jak widać, chcemy mieć możliwość przekazania z zewnątrz zarówno warunku,
 
jak i czynności.
 
jak i czynności.
Wyglądać to może na przykład tak: <br>
+
Wyglądać to może na przykład tak:
<code><nowiki>    template <typename Iter, typename Cond, typename Oper></nowiki></code>  <br>
+
 
<code><nowiki>    void wykonaj_na_spełniających(Iter początek, Iter za_końcem,</nowiki></code>  <br>
+
<nowiki>    template <typename Iter, typename Cond, typename Oper>
<code><nowiki>            Cond warunek, Oper czynność)</nowiki></code>  <br>
+
    void wykonaj_na_spełniających(Iter początek, Iter za_końcem,
 +
            Cond warunek, Oper czynność)</nowiki>
 
Zaimplementuj algorytm o takiej sygnaturze.
 
Zaimplementuj algorytm o takiej sygnaturze.
  

Wersja z 09:21, 3 wrz 2006

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/ . 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.

Zadanie 1 Zapoznaj się z dokumentacją pojemników vector oraz list, a następnie spróbuj napisać jakiś prosty programik wykorzystujący co najmniej 50metod oferowanych przez te klasy. Programik nie musi robić niczego specjalnie pożytecznego. W przypadku niedostatku fantazji jako punkt startowy możesz wykorzystać plik zabawa_z_stl.cpp .

Zadanie 2 Zastanów się, dlaczego lista ma metodę push_front() , a wektor nie - przecież dałoby się ją dla niego zaimplementować.

Podpowiedź do zadania 2 Jak by musiała wyglądać ta implementacja, i w jakim czasie by się wykonywała?

Zadanie 3 Metoda push_front() 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.

Zadanie 4 Oprócz uogólnionych pojemników STL dostarcza również uogólnione funkcje działające 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 wypisz_na_cout() 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?

Rozwiązanie 4 Patrz plik wypisywanie.cpp . Szablon konkretyzowany jest dwa razy, raz jako wypisz_na_cout<std::vector<int>::iterator> , drugi raz jako wypisz_na_cout<int *> .

Zadanie 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:

     template <typename Iter, typename Cond, typename Oper>
     void wykonaj_na_spełniających(Iter początek, Iter za_końcem,
             Cond warunek, Oper czynność)

Zaimplementuj algorytm o takiej sygnaturze.

Zadanie 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 std::list , wystarczy jedna operacja dodająca elementy do listy oraz begin() i end() . Skup się za to na implementacji iteratora, i upewnij się że udostępnia on wszystkie operacje przewidziane w koncepcie ForwardIterator.

Zadanie 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.