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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 1: Linia 1:
 
'''Zadanie 1 '''  
 
'''Zadanie 1 '''  
 
Jednym z poprzednich ćwiczeń było zaimplementowanie szablonu funkcji
 
Jednym z poprzednich ćwiczeń było zaimplementowanie szablonu funkcji
<code><nowiki> wypisz_na_cout()</nowiki></code> , biorącej jako argumenty parę iteratorów.
+
<code><nowiki>wypisz_na_cout()</nowiki></code> , biorącej jako argumenty parę iteratorów.
 
Przeciąż ten szablon, definiując również wersje biorące iterator
 
Przeciąż ten szablon, definiując również wersje biorące iterator
 
plus ilość elementów do wypisania, oraz pojemnik STL.
 
plus ilość elementów do wypisania, oraz pojemnik STL.
Linia 7: Linia 7:
 
'''Zadanie 2 '''  
 
'''Zadanie 2 '''  
 
Zaimplementuj szablon kolejki, używając jako klasy bazowej szablonu
 
Zaimplementuj szablon kolejki, używając jako klasy bazowej szablonu
<code><nowiki> std::list<></nowiki></code> .
+
<code><nowiki>std::list<></nowiki></code> .
  
 
'''Zadanie 3 '''  
 
'''Zadanie 3 '''  
Zaimplementuj szablon klasy <code><nowiki> Tablica</nowiki></code> , biorący jako argumenty
+
Zaimplementuj szablon klasy <code><nowiki>Tablica</nowiki></code> , biorący jako argumenty
 
nazwę typu oraz rozmiar tablicy.
 
nazwę typu oraz rozmiar tablicy.
Jedynymi metodami udostępnianymi przez klasę powinny być <code><nowiki> set()</nowiki></code>  
+
Jedynymi metodami udostępnianymi przez klasę powinny być <code><nowiki>set()</nowiki></code>  
oraz <code><nowiki> get()</nowiki></code> , dające dostęp do wskazanych elementów: <br>
+
oraz <code><nowiki>get()</nowiki></code> , dające dostęp do wskazanych elementów:
<code><nowiki>    Tablica<int, 10> t;</nowiki></code>  <br>
+
<nowiki>    Tablica<int, 10> t;
<code><nowiki>    t.set(0, 77);</nowiki></code>  <br>
+
    t.set(0, 77);
<code><nowiki>    cout << t.get(9) << '';</nowiki></code>  <br>
+
    cout << t.get(9) << '';
<code><nowiki>    cout << sizeof(t) << '';  // powinno zajmować 40 bajtów</nowiki></code>  <br>
+
    cout << sizeof(t) << '';  // powinno zajmować 40 bajtów</nowiki>
Wyspecjalizuj ten szablon dla typu <code><nowiki> bool</nowiki></code> , tak aby elementy tego
+
Wyspecjalizuj ten szablon dla typu <code><nowiki>bool</nowiki></code> , tak aby elementy tego
 
typu zajmowały w pamięci 1 bit, a nie 1 bajt.
 
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
 
Wykład zawiera dyskusję problemów związanych z porównywaniem elementów
 
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.
Linia 33: Linia 33:
 
danego typu, i zwracający odpowiedź na pytanie "czy pierwszy argument
 
danego typu, i zwracający odpowiedź na pytanie "czy pierwszy argument
 
jest mniejszy od drugiego?" jako wartość boolowską.
 
jest mniejszy od drugiego?" jako wartość boolowską.
Jako domyślną wartość tego parametru przyjmuje się <code><nowiki> std::less<></nowiki></code> ,
+
Jako domyślną wartość tego parametru przyjmuje się <code><nowiki>std::less<></nowiki></code> ,
czyli zwykłe porównywanie poprzez <code><nowiki> <</nowiki></code> .
+
czyli zwykłe porównywanie poprzez <code><nowiki><</nowiki></code> .
  
 
'''Zadanie 4 '''  
 
'''Zadanie 4 '''  
 
Zapoznaj się z rodziną funktorów porównujących, do której należy
 
Zapoznaj się z rodziną funktorów porównujących, do której należy
<code><nowiki> std::less<></nowiki></code> . Przypomnij sobie pojemnik <code><nowiki> std::set</nowiki></code> .
+
<code><nowiki>std::less<></nowiki></code> . Przypomnij sobie pojemnik <code><nowiki>std::set</nowiki></code> .
 
Następnie napisz programik korzystający ze zbioru liczb posortowanego
 
Następnie napisz programik korzystający ze zbioru liczb posortowanego
 
odwrotnie (czyli malejąco).
 
odwrotnie (czyli malejąco).
Linia 45: Linia 45:
 
Zaimplementuj uogólniony algorytm sortujący przez prosty wybór ciąg
 
Zaimplementuj uogólniony algorytm sortujący przez prosty wybór ciąg
 
elementów wyznaczony dwoma iteratorami.
 
elementów wyznaczony dwoma iteratorami.
Do zamiany miejscami dwóch elementów użyj <code><nowiki> std::swap</nowiki></code> ,
+
Do zamiany miejscami dwóch elementów użyj <code><nowiki>std::swap</nowiki></code> ,
 
a porównania wykonuj przy pomocy funktora przekazywanego jako
 
a porównania wykonuj przy pomocy funktora przekazywanego jako
 
parametr szablonu naszego algorytmu.
 
parametr szablonu naszego algorytmu.
Linia 54: Linia 54:
  
 
'''Uwaga do zadania 5 '''  
 
'''Uwaga do zadania 5 '''  
STL udostępnia uogólniony algorytm sortujący o nazwie <code><nowiki> std::sort</nowiki></code> .
+
STL udostępnia uogólniony algorytm sortujący o nazwie <code><nowiki>std::sort</nowiki></code> .
 
Zwróć uwagę na inny sposób przekazywania funktora porównującego elementy
 
Zwróć uwagę na inny sposób przekazywania funktora porównującego elementy
-- nie przez nazwę klasy będącą parametrem szablonu, lecz przez
+
- nie przez nazwę klasy będącą parametrem szablonu, lecz przez
 
instancję tej klasy przekazaną jako argument funkcji.
 
instancję tej klasy przekazaną jako argument funkcji.
 
Rozwiązanie przyjęte w STL jest lepsze, gdy mamy do czynienia z funktorami
 
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
 
posiadającymi wewnętrzny stan; przed rozpoczęciem sortowania można ten
 
stan zainicjować.
 
stan zainicjować.

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