Zaawansowane CPP/Ćwiczenia 3: Szablony II

From Studia Informatyczne

Ćwiczenie 1

Jednym z poprzednich ćwiczeń było zaimplementowanie szablonu funkcji wypisz_na_cout(), biorącej jako argumenty parę iteratorów. Przeciąż ten szablon, definiując również wersje biorące iterator plus ilość elementów do wypisania oraz pojemnik STL.

Rozwiązanie

Patrz plik wypisywanie.cpp.

Ćwiczenie 2

Zaimplementuj szablon kolejki, używając jako klasy bazowej szablonu std::list<> .

Rozwiązanie

Patrz pliki kolejka.h oraz test_kolejki.cpp.

Ćwiczenie 3

Zaimplementuj szablon klasy Tablica, biorący jako argumenty nazwę typu oraz rozmiar tablicy. Jedynymi metodami udostępnianymi przez klasę powinny być set() oraz get(), dające dostęp do wskazanych elementów:

     Tablica<int, 10> t;
     t.set(0, 77);
     cout << t.get(9) << '\n';
     cout << sizeof(t) << '\n';   // powinno zajmować 40 bajtów

Wyspecjalizuj ten szablon dla typu bool, tak aby elementy tego typu zajmowały w pamięci 1 bit, a nie 1 bajt.

Rozwiązanie

Patrz pliki tablica.h oraz test_tablicy.cpp.

Wykład zawiera dyskusję problemów związanych z porównywaniem elementów wewnątrz algorytmów uogólnionych. Porównywanie za pomocą operatora < nie zawsze jest tym, czego potrzebujemy - klasycznym przykładem są łańcuchy char *. Są również sytuacje gdy np. chcemy posortować ciąg liczb według ich odległości od pewnej wyznaczonej wartości.

Pojemniki i algorytmy STL zapewniają możliwość wyspecyfikowania pożądanego sposobu sortowania poprzez dodatkowy parametr szablonów. Tym parametrem jest funktor, biorący jako argumenty dwie wartości danego typu i zwracający odpowiedź na pytanie "czy pierwszy argument jest mniejszy od drugiego?" jako wartość boolowską. Jako domyślną wartość tego parametru przyjmuje się std::less<>, czyli zwykłe porównywanie poprzez < .

Ćwiczenie 4

Zapoznaj się z rodziną funktorów porównujących, do której należy std::less<>. Przypomnij sobie pojemnik std::set. Następnie napisz programik korzystający ze zbioru liczb posortowanego odwrotnie (czyli malejąco).

Rozwiązanie

Patrz plik zbior_malejacy.cpp.

Ćwiczenie 5

Zaimplementuj uogólniony algorytm sortujący przez prosty wybór ciąg elementów wyznaczony dwoma iteratorami. Do zamiany miejscami dwóch elementów użyj std::swap, a porównania wykonuj przy pomocy funktora przekazywanego jako parametr szablonu naszego algorytmu. Pamiętaj, że jako parametr dostaniesz klasę funktora; aby móc porównywać, musisz stworzyć obiekt tej klasy. Funktory zazwyczaj mają puste konstruktory i żadnych składowych, więc koszt stworzenia takiego obiektu jest pomijalny.

Uwaga

STL udostępnia uogólniony algorytm sortujący o nazwie std::sort. Zwróć uwagę na inny sposób przekazywania funktora porównującego elementy - nie przez nazwę klasy będącą parametrem szablonu, lecz przez instancję tej klasy przekazaną jako argument funkcji. Rozwiązanie przyjęte w STL jest lepsze, gdy mamy do czynienia z funktorami posiadającymi wewnętrzny stan; przed rozpoczęciem sortowania można ten stan zainicjować.

Rozwiązanie

Patrz plik sortowanie.cpp.