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