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.

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

Jak by musiała wyglądać ta implementacja i w jakim czasie by się wykonywała?

Rozwiązanie

W STL przyjęto, że push_front() 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.

Ć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

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

Ć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

Patrz plik funktory.cpp.

Ć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

Patrz plik lista.h.

Ć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

Patrz plik test_koceptu.cpp. Aby go skompilować, musisz mieć zainstalowane biblioteki boost.