1
Programowanie obiektowe
Wykład 7-8
Biblioteka standardowych szablonów (
STL)
2
Programowanie obiektowe
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
3
Programowanie obiektowe
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 wskaźników; umożliwiają
poruszanie się po zawartości kontenera w podobny sposób, w jaki wskaźniki
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;
4
Programowanie obiektowe
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
Wprowadzenie do STL - Terminologia
5
Programowanie obiektowe
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;
6
Programowanie obiektowe
Wprowadzenie do STL
Klasy kontenerów:
bitset – zbiór bitów; wymagany nagłówek
<bitset>
deque – kolejka dwukierunkowa; wymagany nagłówek
<deque>
list – lista liniowa; wymagany nagłówek
<list>
map – zbiór par (klucz, wartość), w których klucz jest związany tylko z jedna
wartością; wymagany nagłówek
<map>
multimap – zbiór par (klucz, wartość), w których klucz jest związany z
kilkoma wartościami; wymagany nagłówek
<set>
multiset – zbiór, w którym elementy nie musza być unikatowe; wymagany
nagłówek
<set>
priority_queue – kolejka z priorytetami; wymagany nagłówek
<queue>
queue – kolejka FIFO; wymagany nagłówek
<queue>
set – zbiór, którego elementy muszą być unikatowe; wymagany nagłówek
<set>
stack – kolejka LIFO (stos); wymagany nagłówek
<stack>
vector – tablica dynamiczna; wymagany nagłówek
<vector>
7
Programowanie obiektowe
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 T, class Allocator=allocator<T>> class vector
gdzie T oznacza typ elementów wektora
8
Programowanie obiektowe
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 <T, Allocator>& ob);
template <class InIter> vector(InIter start, InIter end,
const Allocator &a=Allocator());
Przykłady działania konstruktorów klasy vector:
1)
vector<int> iv;
// tworzy zerowej długości wektor wartości typu int
2)
vector<char> cv(5);
// tworzy 5-elementowy wektor wartości typu char
3)
vector<char> cv(5, 'x');
// inicjuje 5-elementowy wektor wartości typu char
4)
vector<int> iv2(iv1);
// tworzy wektor int z innego wektora int
9
Programowanie obiektowe
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
10
Programowanie obiektowe
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
11
Programowanie obiektowe
Kontener vector
Wstawianie i usuwanie elementów wektora
Przykład wykorzystania funkcji insert() i erase()
Program 6.15
12
Programowanie obiektowe
Kontener vector
Możliwe jest przechowywanie obiektów w wektorze
Przykład wykorzystania kontenera vector do przechowywania obiektów
Program 6.16
13
Programowanie obiektowe
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 T, class Allocator=allocator <T>> class list
gdzie T oznacza typ danych elementów listy
Alokator jest określony przez Allocator, przy czym domyślnie stosowany
jest alokator standardowy
14
Programowanie obiektowe
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 <T, Allocator>& ob);
template <class InIter> list(InIter start, InIter end,
const Allocator &a=Allocator());
Specyfikator explicit dotyczy wyłącznie konstruktorów
Ilustracja działania specyfikatora explicit:
Program 7.1a
Program 7.1b
15
Programowanie obiektowe
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;
16
Programowanie obiektowe
Kontener list
Przykład ilustrujący podstawowe operacje na liście:
Program 7.2
17
Programowanie obiektowe
Kontener list
Przykład ilustrujący dodawanie elementów na początek listy:
Działanie iteratora end(), zwracającego wskaźnik 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.3
Program 7.4
18
Programowanie obiektowe
Kontener list
Listę można sortować za pomocą funkcji sort()
Przykład sortowania listy, zawierającej elementy o wartościach
określanych losowo
Łączenie dwóch list umożliwia funkcja merge()
Przykład łączenia list
Program 7.5
Program 7.6
19
Programowanie obiektowe
Kontener list
Elementy listy mogą być obiektami
Przykład listy obiektów (z przeciążeniem operatorów <, >, != oraz ==)
Program 7.7
20
Programowanie obiektowe
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
<algorithm>
W bibliotece STL zdefiniowano bardzo wiele algorytmów, np.
algorytmy zliczania elementów,
usuwania i zamiany elementów,
zmiana kolejności elementów.
21
Programowanie obiektowe
Algorytmy - zliczanie elementów
Zliczanie elementów kontenera umożliwiają algorytmy count() i count_if()
Składnia funkcji count():
template <class InIter, class T> 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 <class InIter, class UnPred> 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
22
Programowanie obiektowe
Algorytmy - zliczanie elementów
Przykład użycia algorytmów count() i count_if()
Program 7.8
Program 7.9
23
Programowanie obiektowe
Algorytmy – usuwanie i zamiana elementów
Składnia algorytmu remove_copy():
template <class InIter, class OutIter, class T> 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 <class InIter, class OutIter, class T> 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
24
Programowanie obiektowe
Algorytmy – usuwanie i zamiana elementów
Przykład użycia algorytmów remove_copy() i replace_copy ()
Program 7.10
25
Programowanie obiektowe
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 <class BiIter> void reverse(BiIter start, BiIter end);
Przykład użycia algorytmu reverse()
Program 7.11
26
Programowanie obiektowe
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 <class InIter, class OutIter, class Func>
OutIter transform(InIter start, InIter end, OutIter result,
Func unaryfunc);
template <class InIter1, class InIter2, class OutIter, class Func>
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;
Przykład użycia algorytmu transform()
Program 7.12
27
Programowanie obiektowe
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
28
Programowanie obiektowe
Obiekty funkcyjne
Przykład wykorzystania jednoargumentowego obiektu funkcyjnego negate()
Przykład wykorzystania dwuargumentowego obiektu funkcyjnego divides()
Program 8.1
Program 8.2
29
Programowanie obiektowe
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 <class Argument, class Result> struct unary_function {
typedef Argument argument_type;
typedef Result result_type;
};
template <class Argument1, class Argument2, class Result>
struct binary_function {
typedef Argument1 first_argument_type;
typedef Argument2 second_argument_type;
typedef Result result_type;
};
30
Programowanie obiektowe
Obiekty funkcyjne
Przykład definicji własnego obiektu funkcyjnego
Program 8.3
31
Programowanie obiektowe
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)
32
Programowanie obiektowe
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);
33
Programowanie obiektowe
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:
=, +, +=, ==, !=, <, <=, >, >=, [], <<, >>
34
Programowanie obiektowe
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
35
Programowanie obiektowe
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
36
Programowanie obiektowe
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
37
Programowanie obiektowe
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);
38
Programowanie obiektowe
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);
39
Programowanie obiektowe
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
40
Programowanie obiektowe
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
41
Programowanie obiektowe
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 wskaźnik 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 wskaźnik do
standardowego, zakończonego znakiem null łańcucha znakowego
42
Programowanie obiektowe
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
Obiekty typu string można umieszczać także w innych kontenerach
Program 8.7
Program 8.8
43
Programowanie obiektowe