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