Zaawansowane CPP/Ćwiczenia 3: Szablony II: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 24: Linia 24:
 
wewnątrz algorytmów uogólnionych.
 
wewnątrz algorytmów uogólnionych.
 
Porównywanie za pomocą operatora <code><nowiki><</nowiki></code>  nie zawsze jest tym, czego
 
Porównywanie za pomocą operatora <code><nowiki><</nowiki></code>  nie zawsze jest tym, czego
potrzebujemy -- klasycznym przykładem są łańcuchy <code><nowiki>char *</nowiki></code> ,
+
potrzebujemy - klasycznym przykładem są łańcuchy <code><nowiki>char *</nowiki></code> ,
 
są również sytuacje gdy np. chcemy posortować ciąg liczb według ich
 
są również sytuacje gdy np. chcemy posortować ciąg liczb według ich
 
odległości od pewnej wyznaczonej wartości.
 
odległości od pewnej wyznaczonej wartości.

Wersja z 09:23, 3 wrz 2006

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

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

Zadanie 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) << '';
     cout << sizeof(t) << '';   // 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.

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

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

Zadanie 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 do zadania 5 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ć.