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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 17 wersji utworzonych przez 2 użytkowników)
Linia 2: Linia 2:
 
programowania uogólnionego jest próba wykorzystania w swoim własnym
 
programowania uogólnionego jest próba wykorzystania w swoim własnym
 
kodzie pojemników STL.
 
kodzie pojemników STL.
STL, czyli Standard Template Library, jest, jak sama nazwa wskazuje,
+
STL czyli Standard Template Library jest, jak sama nazwa wskazuje,
oficjalną częścią standardu języka C++, i jako taka jest zawsze dostępna.
+
oficjalną częścią standardu języka C++ i jako taka jest zawsze dostępna.
 
Zawiera implementacje typowych struktur danych (listy, kolejki, tablice
 
Zawiera implementacje typowych struktur danych (listy, kolejki, tablice
 
haszujące, itd.).
 
haszujące, itd.).
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ę [http://www.sgi.com/tech/stl/ http://www.sgi.com/tech/stl/].
 
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.
  
 
Podczas rozwiązywania poniższych zadań proszę zwrócić uwagę na sposób,
 
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
 
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ą
+
pewność, że zajmują nie więcej niż kilka bajtów (iteratory, funktory) są
 
przekazywane przez wartość; rzeczy o nieznanym z góry rozmiarze (elementy
 
przekazywane przez wartość; rzeczy o nieznanym z góry rozmiarze (elementy
 
przechowywane w pojemnikach) są przekazywane przez referencję albo
 
przechowywane w pojemnikach) są przekazywane przez referencję albo
 
referencję do stałej.
 
referencję do stałej.
  
'''Zadanie 1 '''
+
{{cwiczenie|1||
 +
 
 
Zapoznaj się z dokumentacją pojemników vector oraz list, a następnie
 
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.
+
spróbuj napisać jakiś prosty programik, wykorzystujący co najmniej 50% metod oferowanych przez te klasy.
 
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 [[media:Zabawa_z_stl.cpp | zabawa_z_stl.cpp]].
 
+
}}
'''Zadanie 2 '''
+
{{cwiczenie|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ć.
 +
}}
 +
<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>
  
'''Podpowiedź do zadania 2 '''
+
{{cwiczenie|3||
Jak by musiała wyglądać ta implementacja, i w jakim czasie by się wykonywała?
+
 
 
'''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
opisujących pojemniki; następnie sprawdź, jakie operacje z jaką złożonością
+
opisujących pojemniki; następnie sprawdź jakie operacje z jaką złożonością
 
są zdefiniowane przez poszczególne koncepty.
 
są zdefiniowane przez poszczególne koncepty.
 
Odpowiednie informacje możesz znaleźć m.in. na witrynie SGI.
 
Odpowiednie informacje możesz znaleźć m.in. na witrynie SGI.
 
+
}}
'''Zadanie 4 '''
+
{{cwiczenie|4||
Oprócz uogólnionych pojemników STL dostarcza również uogólnione funkcje
+
działające na ciągach elementów, tzw. algorytmy.
+
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
 
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.
Czy jesteś w stanie powiedzieć, jakie typy będą użyte podczas konkretyzacji
+
Czy jesteś w stanie powiedzieć jakie typy będą użyte podczas konkretyzacji
 
tego szablonu?
 
tego szablonu?
 
+
}}
'''Rozwiązanie 4 '''
+
<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 <code><nowiki>wypisywanie.cpp</nowiki></code> .
+
Patrz plik [[media:Wypisywanie.cpp | wypisywanie.cpp]].
 
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> .
 +
</div></div>
  
'''Zadanie 5 '''
+
{{cwiczenie|5||
 +
 
Wykład krótko wspomina o funktorach, czyli obiektach wyglądających
 
Wykład krótko wspomina o funktorach, czyli obiektach wyglądających
 
syntaktycznie tak jak funkcje.
 
syntaktycznie tak jak funkcje.
 
Są one przydatne m.in. wtedy, gdy chcemy napisać uogólniony algorytm
 
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.
 
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
+
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ść.
 
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 widać, chcemy mieć możliwość przekazania z zewnątrz zarówno warunku,
Linia 77: Linia 87:
 
             Cond warunek, Oper czynność)</nowiki>
 
             Cond warunek, Oper czynność)</nowiki>
 
Zaimplementuj algorytm o takiej sygnaturze.
 
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>
  
'''Zadanie 6 '''
+
{{cwiczenie|6||
 +
 
Spróbuj zaimplementować swój własny pojemnik wyposażony w iterator.
 
Spróbuj zaimplementować swój własny pojemnik wyposażony w iterator.
 
Oprzyj go o dynamicznie tworzoną listę pojedynczo wiązaną.
 
Oprzyj go o dynamicznie tworzoną listę pojedynczo wiązaną.
Linia 84: Linia 99:
 
wszystkich metod znajdujących się w <code><nowiki> std::list</nowiki></code> , wystarczy jedna
 
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> .
 
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
+
Skup się za to na implementacji iteratora i upewnij się, że udostępnia on
 
wszystkie operacje przewidziane w koncepcie ForwardIterator.
 
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>
  
'''Zadanie 7 '''
+
{{cwiczenie|7||
 +
 
Zaimplementuj test, który sprawdza czy dany iterator rzeczywiście spełnia
 
Zaimplementuj test, który sprawdza czy dany iterator rzeczywiście spełnia
 
wszystkie wymagania konceptu ForwardIterator.
 
wszystkie wymagania konceptu ForwardIterator.
Linia 94: Linia 114:
 
Następnie użyj tego testu na iteratorach STL oraz na swoim własnym,
 
Następnie użyj tego testu na iteratorach STL oraz na swoim własnym,
 
stworzonym w poprzednim zadaniu.
 
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>

Aktualna wersja na dzień 10:19, 2 paź 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.

Ćwiczenie 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 zabawa_z_stl.cpp.

Ćwiczenie 2

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

Podpowiedź
Rozwiązanie

Ćwiczenie 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.

Ćwiczenie 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 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

Ćwiczenie 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.

Rozwiązanie

Ćwiczenie 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.

Rozwiązanie

Ćwiczenie 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.

Rozwiązanie