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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 16 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
'''Zadanie 1 '''
+
{{cwiczenie|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.
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Patrz plik [[media:Wypisywanie.cpp | wypisywanie.cpp]].
 +
</div></div>
  
'''Zadanie 2 '''
+
{{cwiczenie|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> .
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Patrz pliki [[media:Kolejka.h | kolejka.h]] oraz [[media:Test_kolejki.cpp | test_kolejki.cpp]].
 +
</div></div>
  
'''Zadanie 3 '''
+
{{cwiczenie|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:
+
oraz <code><nowiki>get()</nowiki></code>, dające dostęp do wskazanych elementów:
 
  <nowiki>    Tablica<int, 10> t;
 
  <nowiki>    Tablica<int, 10> t;
 
     t.set(0, 77);
 
     t.set(0, 77);
     cout << t.get(9) << '';
+
     cout << t.get(9) << '\n';
     cout << sizeof(t) << '';  // powinno zajmować 40 bajtów</nowiki>
+
     cout << sizeof(t) << '\n';  // 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.
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Patrz pliki [[media:Tablica.h | tablica.h]] oraz [[media:Test_tablicy.cpp | test_tablicy.cpp]].
 +
</div></div>
  
 
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
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 31: Linia 45:
 
pożądanego sposobu sortowania poprzez dodatkowy parametr szablonów.
 
pożądanego sposobu sortowania poprzez dodatkowy parametr szablonów.
 
Tym parametrem jest funktor, biorący jako argumenty dwie wartości
 
Tym parametrem jest funktor, biorący jako argumenty dwie wartości
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 '''
+
{{cwiczenie|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).
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Patrz plik [[media:Zbior_malejacy.cpp | zbior_malejacy.cpp]].
 +
</div></div>
  
'''Zadanie 5 '''
+
{{cwiczenie|5||
 +
 
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 52: Linia 72:
 
Funktory zazwyczaj mają puste konstruktory i żadnych składowych,
 
Funktory zazwyczaj mają puste konstruktory i żadnych składowych,
 
więc koszt stworzenia takiego obiektu jest pomijalny.
 
więc koszt stworzenia takiego obiektu jest pomijalny.
 
+
}}
'''Uwaga do zadania 5 '''
+
{{uwaga| ||
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
Linia 61: Linia 82:
 
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ć.
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Patrz plik [[media:Sortowanie.cpp | sortowanie.cpp]].
 +
</div></div>

Aktualna wersja na dzień 10:22, 2 paź 2006

Ć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

Ćwiczenie 2

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

Rozwiązanie

Ć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

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

Ć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