Funktory, zbiory,mapy, iteratory

Funktory, zbiory, mapy,  iteratory Wykład 12 10/01/28 2 Predykaty  Predykaty są specjalnym rodzajem funkcji (obiektu  funkcyjnego)  Zwracają one wartości typu  true/false  Służą one do określania kryterium sortowania, wyszukiwania,  usuwania itp.  Predykaty mogą być jedno- lub dwuargumentowe  Predykaty dla takiego samego wywołania zwracają zawsze tą  samą wartość  Predykaty nie zmieniają swojego stanu wewnętrznego, np.  wartość zwracania nie zależy od liczby wywołań  Przykład cpp_12.1 i cpp_12.2 10/01/28 3 Obiekty funkcyjne  Argumenty funkcyjne algorytmów nie muszą być funkcjami – mogą to być obiekty zachowujące się jak funkcje  Obiekty funkcyjne nazywamy inaczej funktorami  fun(arg); //fun – klasa ze zdefiniowanym operatorem ()  Zalety funktorów  Obiekt funkcyjny posiada stan, możliwe są nawet różne stany  inicjalizowane przed użyciem  Posiadają typ  Funktory często działają szybciej niż funkcje  Przykładowe predefiniowane obiekty funkcyjne  Typowym obiektem funkcyjnym używającym operatora    służący do określania kryterium sortowania  Podobnie  greater  - operator   Przykład cpp_12.3 10/01/28 4 Obiekty funkcyjne  Predefiniowane obiekty funkcyjne w nagłówku   negate()  oznacza   -param  plus()  oznacza   param1 + param2  minus()  oznacza   param1 - param2  multiplies()  oznacza  param1 * param2  divides()  oznacza  param1 / param2  modulus()  oznacza  param1 % param2  equal_to()  oznacza  param1 == param2  not_equal_to()  oznacza  param1 != param2  less()  oznacza  param1 ()  oznacza  param1  param2  less_equal()  oznacza  param1 ()  oznacza  param1 = param2  logical_not()  oznacza  !param  logical_and()  oznacza  param1 && param2  logical_or()  oznacza  param1 || param2 10/01/28 5 Pary  Klasa  pair  umożliwia potraktowanie dwóch wartości jako  pojedynczego elementu  Jest wykorzystywana w kilku miejscach w bibliotece STL, a w  szczególności w kontenerach  map  oraz  multimap  Klasa  pair  zdefiniowana jest w pliku nagłówkowym   std::pair p;  Składowe  p.first  i  p.second  Operatory  ==  oraz 

(…)

…?

Jeżeli potrzebujemy szybkiego wyszukiwania elementów to
należy zastosować zbiór (wielozbiór) sortujący zgodnie z
kryterium wyszukiwania


Do przechowywania par należy stosować mapy




Jeszcze lepiej jest zastosować tablice mieszające (hash tables),
które zapewniają wyszukiwanie jeszcze o rząd wielkości szybsze, ale
nie ma ich w STL
Ewentualnie znowu tablice mieszające
Tablica asocjacyjna – mapa
Słownik…
… jest jednocześnie elementem
Mapy i multimapy posiadają interfejs bardzo zbliżony do
zbiorów i wielozbiorów





10/01/28
Elementami są pary, możliwość tworzenia tablic asocjacyjnych
Sortowanie jest automatyczne na podstawie kluczy
Szybkie wyszukiwanie wg klucza, natomiast wolne wg wartości
Nie udostępniają operacji bezpośredniego dostępu do
elementów
Z punktu widzenia iteratorów klucze w mapach są stałe
18…
…(make_pair("data", 3.14159));
Użycie definicji typu value_type


c.insert(pair<string, double>("data", 3.14159));
c.insert(map<string, double>::value_type("data",
3.14159));
Przykład cpp_12.7
10/01/28
23
Zastosowania map i multimap

Wykorzystanie mapy jako tablicy asocjacyjnej

Kontenery asocjacyjne na ogół nie udostępniają
bezpośredniego dostępu do elementów


Tablica asocjacyjna…
… to tak, w której kluczem może być
dowolny typ, nie tylko liczba naturalna



Wyjątkiem są mapy, które nie są stałe – udostępniają operator []
tab["dana1"] = 15;
tab["dana2"] = 56;
Indeks nie może być w takich sytuacjach nieprawidłowy
(oczywiście jeżeli jest odpowiedniego typu)
Przykład cpp_12.8 i cpp_12.9
10/01/28
24
Przegląd możliwości
Vector
Deque
List
Set
MultiSet
Map
Multimap
Tablica
dynamiczna
Tablica
tablic…
... zobacz całą notatkę