PO W7 8 II ZIN

Wykład 7-8
Biblioteka standardowych szablonów (STL)
Programowanie obiektowe
1
Biblioteka standardowych szablonów
Biblioteka standardowych szablonów STL (Standard Template Library)
stanowi jedno z najwa\niejszych rozszerzeń języka C++ w ostatnich latach
Biblioteka ta zawiera szablony klas ogólnego przeznaczenia oraz funkcje
implementujące, dotyczące np. obsługi wektorów, list, kolejek i stosów
Programowanie obiektowe
2
Wprowadzenie do STL - Terminologia
Kontenery obiekty STL przeznaczone do przechowywania innych
obiektów (danych), zwykle tego samego typu; istnieje kilka rodzajów
kontenerów;
Ka\da klasa kontenera posiada definicje operujących na nim funkcji
Algorytmy operują na kontenerach; umo\liwiają manipulowanie ich
zawartością; biblioteka STL zawiera ponad 70 ró\nych algorytmów;
Iteratory obiekty pełniące rolę podobną do wskazników; umo\liwiają
poruszanie się po zawartości kontenera w podobny sposób, w jaki wskazniki
pozwalają przemieszczać się w obrębie tablicy;
Alokatory są definiowane dla ka\dego kontenera; umo\liwiają
zarządzanie pamięcią przydzieloną dla kontenera; domyślny alokator to
obiekt klasy allocator; programista mo\e zdefiniować własny alokator;
Programowanie obiektowe
3
Wprowadzenie do STL - Terminologia
Predykaty funkcje (jednoargumentowe, oznaczane jako UnPred lub
dwuargumentowe, oznaczane jako BinPred ), zwracające wartość logiczną
(prawda lub fałsz)
Obiekty funkcyjne szablony zdefiniowane w klasie functional; obiekty
funkcyjne mogą być stosowane w algorytmach STL;
przykłady obiektów funkcyjnych: less, less_equal, greater, greater_qual,
logical_and, logical_or, logical_not
Programowanie obiektowe
4
Wprowadzenie do STL
Rodzaje iteratorów:
Dostęp swobodny (RandIter) mo\liwe składowanie i pobieranie wartości;
swobodny dostęp do elementów kontenera;
Dostęp dwukierunkowy (BiIter) mo\liwe składowanie i pobieranie
wartości; poruszanie się w przód i w tył;
Dostęp jednokierunkowy (ForIter) mo\liwe składowanie i pobieranie
wartości; poruszanie się tylko do przodu;
Wejście (InIter), Wyjście (OutIter) - mo\liwe składowanie wartości, ale bez
mo\liwości pobierania; poruszanie się tylko do przodu;
Programowanie obiektowe
5
Wprowadzenie do STL
Klasy kontenerów:
bitset zbiór bitów; wymagany nagłówek
deque kolejka dwukierunkowa; wymagany nagłówek
list lista liniowa; wymagany nagłówek
map zbiór par (klucz, wartość), w których klucz jest związany tylko z jedna
wartością; wymagany nagłówek
multimap zbiór par (klucz, wartość), w których klucz jest związany z
kilkoma wartościami; wymagany nagłówek
multiset zbiór, w którym elementy nie musza być unikatowe; wymagany
nagłówek
priority_queue kolejka z priorytetami; wymagany nagłówek
queue kolejka FIFO; wymagany nagłówek
set zbiór, którego elementy muszą być unikatowe; wymagany nagłówek

stack kolejka LIFO (stos); wymagany nagłówek
vector tablica dynamiczna; wymagany nagłówek
Programowanie obiektowe
6
Kontener vector
klasa vector obsługuje tablice dynamiczne (tablice, które w razie potrzeby
mogą być powiększane);
mimo \e wektory są dynamiczne, mo\liwy jest dostęp do jego elementów za
pomocą standardowej składni, wykorzystującej indeks tablicy;
specyfikacja szablonu dla klasy vector
template > class vector
gdzie T oznacza typ elementów wektora
Programowanie obiektowe
7
Kontener vector
Konstruktory kontenera vector:
explicit vector(const Allocator &a=Allocator());
explicit vector(size_type num, const T &val=T(),
const Allocator &a=Allocator());
vector(const vector & ob);
template vector(InIter start, InIter end,
const Allocator &a=Allocator());
Przykłady działania konstruktorów klasy vector:
1) vector iv; // tworzy zerowej długości wektor wartości typu int
2) vector cv(5); // tworzy 5-elementowy wektor wartości typu char
3) vector cv(5, 'x'); // inicjuje 5-elementowy wektor wartości typu char
4) vector iv2(iv1); // tworzy wektor int z innego wektora int
Programowanie obiektowe
8
Kontener vector
Dla kontenera vector zdefiniowane są następujące operatory:
++, <, <=, !=, >, >=, []
Najczęściej wykorzystywane funkcje składowe kontenera vector:
size() zwraca aktualny rozmiar wektora;
begin() zwraca iterator wskazujący początek wektora;
end() zwraca iterator wskazujący koniec wektora;
push_back(&val) umieszcza wartość na końcu wektora;
pop_back() usuwa ostatni element wektora;
insert(...) umieszcza wartość w środku wektora;
erase(...) usuwa elementy wektora;
Przykład ilustrujący podstawowe operacje na wektorze:
Program 6.13
Programowanie obiektowe
9
Kontener vector
Dostęp do składowych wektora mo\na uzyskać za pomocą indeksów
albo za pomocą iteratorów
Uzyskiwanie dostępu do wektora za pomocą iteratora
Program 6.14
Programowanie obiektowe
10
Kontener vector
Wstawianie i usuwanie elementów wektora
Przykład wykorzystania funkcji insert() i erase()
Program 6.15
Programowanie obiektowe
11
Kontener vector
Mo\liwe jest przechowywanie obiektów w wektorze
Przykład wykorzystania kontenera vector do przechowywania obiektów
Program 6.16
Programowanie obiektowe
12
Kontener list
Klasa list obsługuje listy jednokierunkowe i dwukierunkowe
W przeciwieństwie do wektorów, które umo\liwiają dostęp swobodny
(bezpośredni), listy umo\liwiają wyłącznie dostęp sekwencyjny
Specyfikacja szablonu kontenera list:
template > class list
gdzie T oznacza typ danych elementów listy
Alokator jest określony przez Allocator, przy czym domyślnie stosowany
jest alokator standardowy
Programowanie obiektowe
13
Kontener list
Dostępne są następujące konstruktory:
explicit list(const Allocator &a=Allocator());
explicit list(size_type num, const T &val=T(),
const Allocator &a=Allocator());
list(const list & ob);
template list(InIter start, InIter end,
const Allocator &a=Allocator());
Specyfikator explicit dotyczy wyłącznie konstruktorów
Ilustracja działania specyfikatora explicit:
Program 7.1b
Program 7.1a
Programowanie obiektowe
14
Kontener list
Operatory dostępne dla listy:
++, <, <=, ==, !=, >, >=,
Najczęściej wykorzystywane funkcje składowe kontenera list:
size() zwraca liczbę elementów listy;
begin() zwraca iterator wskazujący pierwszy element listy;
end() zwraca iterator wskazujący ostatni element listy;
push_front(&val) umieszcza element określony przez val na
początku listy;
push_back(&val) umieszcza element określony przez val na końcu
listy;
pop_front() usuwa pierwszy element listy;
pop_back() usuwa ostatni element listy;
insert(...) umieszcza wartość val w środku listy;
erase(...) usuwa elementy listy;
Programowanie obiektowe
15
Kontener list
Przykład ilustrujący podstawowe operacje na liście:
Program 7.2
Programowanie obiektowe
16
Kontener list
Przykład ilustrujący dodawanie elementów na początek listy:
Program 7.3
Działanie iteratora end(), zwracającego wskaznik na koniec listy:
funkcja end() działa w taki sposób, \e ostatni element listy
wskazywany jest przez end()-1; oznacza to, \e end() wskazuje poza
listę!
zwiększa to wydajność algorytmów przeglądających listę (gdy iterator
przyjmie taką samą wartość jak ta, którą zwraca end(), wiadomo \e
przejrzane zostały wszystkie elementy listy);
Przykład przeglądania listy
Program 7.4
Programowanie obiektowe
17
Kontener list
Listę mo\na sortować za pomocą funkcji sort()
Przykład sortowania listy, zawierającej elementy o wartościach
określanych losowo
Program 7.5
Aączenie dwóch list umo\liwia funkcja merge()
Przykład łączenia list
Program 7.6
Programowanie obiektowe
18
Kontener list
Elementy listy mogą być obiektami
Przykład listy obiektów (z przecią\eniem operatorów <, >, != oraz ==)
Program 7.7
Programowanie obiektowe
19
Algorytmy
Algorytmy operują na kontenerach, z których ka\dy udostępnia zestaw
podstawowych operacji na przechowywanych elementach
Algorytmy pozwalają na bardziej rozbudowane i zło\one akcje
Umo\liwiają tak\e pracę z dwoma kontenerami ró\nych typów
Aby uzyskać dostęp do algorytmów STL nale\y u\yć nagłówka

W bibliotece STL zdefiniowano bardzo wiele algorytmów, np.
algorytmy zliczania elementów,
usuwania i zamiany elementów,
zmiana kolejności elementów.
Programowanie obiektowe
20
Algorytmy - zliczanie elementów
Zliczanie elementów kontenera umo\liwiają algorytmy count() i count_if()
Składnia funkcji count():
template size_t count(InIter start, InIter end,
const T &val);
Algorytm count() zwraca liczbę elementów odpowiadających val,
przechowywanych w kontenerze począwszy od miejsca wskazywanego
przez start, do miejsca wskazywanego przez end
Składnia funkcji count_if():
template size_t count_if(InIter start, InIter end,
UnPred pnf);
Algorytm count_if() zwraca liczbę elementów przechowywanych w
kontenerze począwszy od miejsca wskazywanego przez start, do miejsca
wskazywanego przez end, dla których predykat unarny pnf zwraca wartość
Prawda
Programowanie obiektowe
21
Algorytmy - zliczanie elementów
Przykład u\ycia algorytmów count() i count_if()
Program 7.8
Program 7.9
Programowanie obiektowe
22
Algorytmy usuwanie i zamiana elementów
Składnia algorytmu remove_copy():
template OutIter remove_copy(InIter start,
InIter end, OutIter result, const T &val);
Algorytm remove_copy() kopiuje elementy ze wskazanego zakresu,
począwszy od miejsca wskazywanego przez start, do miejsca
wskazywanego przez end, usuwajac te, których wartość wynosi val
Składnia algorytmu replace_copy():
template OutIter replace_copy(InIter start,
InIter end, OutIter result, const T &old, const T &new);
Algorytm replace_copy() kopiuje elementy ze wskazanego zakresu,
począwszy od miejsca wskazywanego przez start, do miejsca
wskazywanego przez end, zamieniając elementy wskazywane przez old na
wskazywane przez new
Programowanie obiektowe
23
Algorytmy usuwanie i zamiana elementów
Przykład u\ycia algorytmów remove_copy() i replace_copy ()
Program 7.10
Programowanie obiektowe
24
Algorytmy przekształcanie elementów
Często wykorzystywanym algorytmem jest algorytm reverse(),
umo\liwiający zmianę (odwrócenie) kolejności elementów kontenerera
Składnia:
template void reverse(BiIter start, BiIter end);
Przykład u\ycia algorytmu reverse()
Program 7.11
Programowanie obiektowe
25
Algorytmy przekształcanie elementów
Innym, często wykorzystywanym algorytmem jest algorytm transform(),
umo\liwiający przekształcenie elementów kontenera, za pomocą wskazanej
funkcji
Algorytm transform() ma dwie ogólne postaci:
template
OutIter transform(InIter start, InIter end, OutIter result,
Func unaryfunc);
template
OutIter transform(InIter1 start1, InIter1 end1, InIter2 start2,
OutIter result, Func binaryfunc);
Algorytm stosuje funkcję (jedno- lub dwuargumentową) do wszystkich
elementów podanego zakresu i umieszcza rezultat w result; obie wersje
zwracają iterator, wskazujący koniec sekwencji wynikowej;
Program 7.12
Przykład u\ycia algorytmu transform()
Programowanie obiektowe
26
Obiekty funkcyjne
Obiekty funkcyjne (funktory) nale\ą do biblioteki STL
Obiekt funkcyjny to szablon klasy, dla której zdefiniowano operator()
Biblioteka STL zawiera wiele wbudowanych obiektów funkcyjnych, takich
jak:
plus, minus, multiples, divides, less, less_equal, greater, greater_qual,
logical_and, logical_or, logical_not, negate
Mo\liwe jest tak\e definiowanie własnych obiektów funkcyjnych
Obiekty funkcyjne, podobnie jak predykaty, mogą być jednoargumentowe lub
dwuargumentowe
Programowanie obiektowe
27
Obiekty funkcyjne
Przykład wykorzystania jednoargumentowego obiektu funkcyjnego negate()
Program 8.1
Przykład wykorzystania dwuargumentowego obiektu funkcyjnego divides()
Program 8.2
Programowanie obiektowe
28
Obiekty funkcyjne
W celu zdefiniowania własnego obiektu funkcyjnego nale\y utworzyć klasę
z przecią\oną funkcją operator
Dla zwiększenia elastyczności warto wykorzystywać jako klasę bazową jedną
z następujących klas ogólnych zdefiniowanych w bibliotece STL
template struct unary_function {
typedef Argument argument_type;
typedef Result result_type;
};
template
struct binary_function {
typedef Argument1 first_argument_type;
typedef Argument2 second_argument_type;
typedef Result result_type;
};
Programowanie obiektowe
29
Obiekty funkcyjne
Przykład definicji własnego obiektu funkcyjnego
Program 8.3
Programowanie obiektowe
30
Klasa string
Języki C/C++ nie posiadają wbudowanego typu string; w konsekwencji nie
są dostępne standardowe operacje na napisach;
Istnieją dwa sposoby obsługi łańcuchów znakowych:
1) wykorzystanie tablic znakowych, zakończonych znakiem null
2) wykorzystanie klasy string, obsługującej łańcuchy znaków 8-bitowych
(istnieje tak\e klasa wstring, obsługująca tzw. znaki rozszerzone)
Klasa string dodana została do biblioteki standardowej C++ z trzech
powodów:
1) uzupełnienie listy tzw. typów wbudowanych o typ string
2) wygoda (mo\na korzystać ze standardowych operatorów C++)
3) bezpieczeństwo (nie ma zagro\enia przekroczenia zakresu tablicy
znakowej)
Programowanie obiektowe
31
Klasa string
Przykłady niedozwolonych działań na napisach:
char s1[80], s2[80], s3[80];
s1 = "Alpha"; // tak nie mo\na
s2 = "Beta"; // tak nie mo\na
s3 = s1 + s2; // błąd, operacja niedozwolona
Przykłady dozwolonych działań na napisach (z wykorzystaniem funkcji z
biblioteki cstring):
strcpy(s1, "Alpha");
strcpy(s2, "Beta");
strcpy(s3, s1);
strcat(s3, s2);
Programowanie obiektowe
32
Klasa string
Klasa string jest bardzo rozbudowana; ma wiele konstruktorów i funkcji
składowych;
Prototypy trzech, najczęściej u\ywanych konstruktorów klasy string:
string(); // tworzy pusty obiekt klasy string
string(const char *str); // tworzy obiekt klasy string, zawierający tzw.
// C-string, tj. zakończony symbolem null łańcuch
// znakowy, wskazywany przez str
string(const string &str); // tworzy obiekt klasy string z innego obiektu typu
// string
Przykłady operatorów, dostępnych w klasie string:
=, +, +=, ==, !=, <, <=, >, >=, [], <<, >>
Programowanie obiektowe
33
Klasa string
Obecność standardowych operatorów eliminuje potrzebę korzystania z
funkcji bibliotecznych z biblioteki cstring;
Operator + słu\y do konkatenacji obiektów string z innymi obiektami tego
typu lub z C-stringami, tzn. dozwolone są np. operacje:
string + string
string + C-string
C-string + string
Długość łańcucha typu string nie jest określona (nie istnieje zagro\enie
przekroczenia zakresu); obiekty typu string mają dynamiczną naturę;
Przykład wykorzystania klasy string
Program 8.4
Programowanie obiektowe
34
Klasa string
Większość operacji na obiektach typu string mo\na przeprowadzić
posługując się standardowymi operatorami;
Bardziej zło\one operacje realizuje się za pomocą funkcji składowych klasy
string
Przykłady prototypów funkcji składowych klasy string
Funkcja assign()
1) do wywołującego obiektu przypisywanych jest num znaków ze strob,
począwszy od pozycji wyznaczonej przez start
string &assign(const string &strob, size_type start, size_type num);
2) do wywołującego obiektu przypisywanych jest num znaków
z zakończonego przez null łańcucha str typu C-string
string &assign(const char *str, size_type num);
Funkcja assign() nie mo\e być zastąpiona operatorem przypisania =, gdy
operacje na łańcuchu dotyczą jego części
Programowanie obiektowe
35
Klasa string
Funkcja append()
1) do wywołującego obiektu dołączanych jest num znaków ze strob,
począwszy od pozycji wyznaczonej przez start
string &append(const string &strob, size_type start, size_type num);
2) do wywołującego obiektu dołączanych jest num znaków
z zakończonego przez null łańcucha str typu C-string
string &append(const char *str, size_type num);
Funkcja append() nie mo\e być zastąpiona operatorem +, gdy dołączany jest
fragment łańcucha
Programowanie obiektowe
36
Klasa string
Funkcja insert()
1) do wywołującego obiektu wstawiany jest napis strob, począwszy od
pozycji wyznaczonej przez start
string &insert(size_type start, const string &strob);
2) do wywołującego obiektu wstawianych jest num znaków ze strob,
począwszy od pozycji wyznaczonej przez insStart, w miejscu
wskazywanym przez start
string &insert(size_type start, const string &strob, size_type insStart,
size_type num);
Programowanie obiektowe
37
Klasa string
Funkcja replace()
1) w wywołującym obiekcie zamienianych jest num znaków, począwszy
od pozycji wyznaczonej przez start, na łańcuch strob
string &replace(size_type start, size_type num, const string &strob);
2) w wywołującym obiekcie zamienianych jest orgNum znaków,
począwszy od pozycji wyznaczonej przez start na repNum znaków z
łańcucha strob, począwszy od pozycji wyznaczonej przez repStart
string &replace(size_type start, size_type orgNum, const string &strob,
size_type repStart, size_type repNum);
Programowanie obiektowe
38
Klasa string
Funkcja erase()
z wywołującego obiektu usuwanych jest num znaków, począwszy od pozycji
wyznaczonej przez start
string &erase(size_type start=0, size_type num=npos);
gdzie npos jest stałą, oznaczającą rozmiar najdłu\szego łańcucha
Przykład
Program 8.5
Programowanie obiektowe
39
Klasa string
Funkcja find()
w wywołującym obiekcie, począwszy od pozycji wyznaczonej przez start
poszukiwane jest pierwsze wystąpienie łańcucha zawierającego strob;
size_type find(const string &strob, size_type start=0) const;
Funkcja rfind()
w wywołującym obiekcie, począwszy od pozycji wyznaczonej przez start
poszukiwane jest ostatnie wystąpienie łańcucha zawierającego strob
size_type rfind(const string &strob, size_type start=npos) const;
Funkcje find(), rfind() zwracają indeks wskazujący poło\enie poszukiwanego
łańcucha lub npos, jeśli poszukiwanie się nie powiedzie;
Przykład
Program 8.6
Programowanie obiektowe
40
Klasa string
Funkcja compare()
z wywołującym obiektem porównywanych jest num znaków ze strob,
począwszy od pozycji wyznaczonej przez start;
int_compare(size_type start, size_type num, const string &strob) const;
jeśli łańcuch wywołujący jest mniejszy ni\ strob funkcja zwraca wartość
mniejszą od zera; jeśli jeśli łańcuch wywołujący jest większy ni\ strob
funkcja zwraca wartość większą od zera; gdy napisy są równe funkcja
zwraca wartość 0;
Funkcja c_str()
zwraca wskaznik do zakończonego symbolem null łańcucha znakowego,
powstałego z obiektu typu string; tak otrzymanego łańcucha nie mo\na
modyfikować;
const char *c_str() const;
Przykład zastosowania: podczas otwierania pliku niezbędny jest wskaznik do
standardowego, zakończonego znakiem null łańcucha znakowego
Programowanie obiektowe
41
Klasa string
Obiekty typu string są kontenerami
Dostępne są zatem typowe iteratory, a operacje na kontenerach string mo\na
przeprowadzać za pomocą algorytmów STL
Przykład wykorzystania obiektu string jako kontenera
Program 8.7
Obiekty typu string mo\na umieszczać tak\e w innych kontenerach
Program 8.8
Programowanie obiektowe
42
Programowanie obiektowe
43

Wyszukiwarka

Podobne podstrony:
PO W3 II ZIN
PO W1 2 II ZIN
PO W3 II ZIN
PO W4 II ZIN
PO W 5 6 II ZIN
PO W4 IV ZIN
Matematyka krok po kroku II
PO W2 IV ZIN
PO W3 IV ZIN
(Ekumenizm przed i po Soborze Watykańskim II)
02 Stalinizacja życia w Polsce po II Wojnie Światowej
Zimna wojna, konferencje, sprawa niemiec po II wojnie swiatowej
Slowo Abp A Dzięgi po Beatyfikacji JP II
Świat po II Wojnie Światowej, prezentacja

więcej podobnych podstron