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