Programowanie uogólnione

• Paradygmat: Zadecyduj jakie chcesz mieć algorytmy, parametryzuj je w taki sposób, by działały dla różnych typów i struktur danych

• Programowanie uogólnione: program operuje nie na konkretnej strukturze danych ale na rodzinie takich struktur.

• Przykład 1: Obsługa stosu, stos jest przechowywany w tablicy określonej wielkości

// klasa wzorcowa (szablonowa)

template <class T> class Stos {

T *wsk_stosu; // adres tablicy dla stosu

int wierzcholek; // indeks wierzchołka stosu

int max_rozmiar; // rozmiar tablicy dla stosu

public:

class Niedomiar {}; // klasa dla wyjątku (pusty stos)

class Nadmiar {}; // klasa dla wyjątku (przepełnienie stosu)

class Zly_rozmiar {}; // klasa dla wyjątku (zły rozmiar stosu)

Stos (int s); // konstruktor

~Stos(); // destruktor

void wloz(T);

T zdejmij();

};

...

template<classT> void Stos<T>::wloz(T c)

{

if (wierzcholek == max_rozmiar) throw Nadmiar();

v[wierzcholek]=c;

wierzcholek++;

}

template<class T> T Stos<T>::zdejmij()

{

if (wierzcholek == 0) throw Niedomiar();

wierzcholek--;

return v[wierzcholek]

}

W main:

// używanie stosu

Stos<char> znaki(10) // stos 10 znaków

Stos<int> liczby(5) // stos 5 liczb całkowitych

Stos<zesplone> lz(10) // stos 10 liczb zespolonych

Przykład 2: Obsługa kolejki FIFO, kolejka przechowywana jest w tablicy

template <class Typ> class FIFO {

Typ *t;

int glowa, ogon, max_el;

public:

FIFO(int n) {

max_el=n;

glowa=ogon=0;

t=new Typ[max_el];

}

void wstaw (Typ x) {

t[ogon++]=x;

if (ogon>max_el) ogon=0;

}

int obsluz(Typ &w) {

if (glowa==ogon) return -1;

w=t[glowa++];

if (glowa>max_el) glowa=0;

return 1;

}

int pusta() {

if (glowa==ogon)

return 1;

else

return 0;

}

};

#include <iostream>

int main() {

FIFO<char*> kolejka(3);

char *tab[]={"Nowak",

"Adamska", "Burski"};

for (int i=0; i<3; i++)

kolejka.wstaw(tab[i]);

for (int i=0; i<5; i++)

{

char *s;

int res=kolejka.obsluz(s);

if (res==1)

cout << "Obsluzony klient: "

<< s << endl;

else {

cout << "Kolejka pusta!\n";

break;

}

}

}

Klasy pojemnikowe (ang. container class)

• Klasa, która może przechowywać obiekty pewnego typu nazywana jest klasą pojemnikową.

• Pojemnik jest obiektem, który przechowuje inne obiekty i potrafi nimi zarządzać.

• Inne nazwy: kolekcja, kontener, zasobnik

Przykład prostej klasy pojemnikowej

// Klasa do przechowywania liczb całkowitych

class schowek {

int liczba;

public:

void schowaj

(int x) { liczba = x }

int oddaj()

{ return liczba; }

};

// Ta sama klasa zapisana za pomocą wzorca

template <class typObiektu> class schowek {

typObiektu liczba;

public:

void schowaj(typObiektu x)

{ liczba = x }

typObiektu oddaj()

{ return liczba; }

};

Przykład klasy do przechowywania obiektów własnego typu

#include <iostream>

#include <string>

struct Osoba{

string imie;

int wiek;

};

ostream& operator << (ostream& wy, Osoba& os)

{

wy << os.imie << ' ';

wy << os.wiek << ' ';

return wy;

}

istream& operator >> (istream& we, Osoba& os)

{

cout << "Wpisz imie: ";

we >> os.imie;

cout << "Wpisz wiek: ";

we >> os.wiek;

return (we);

}

template <class T> class Dane {

private:

T d;

public:

Dane() {};

Dane(T n);

void Wczytaj();

void Drukuj();

};

template <class T> Dane<T>::Dane(T n)

{

d=n;

}

template <class T> void Dane<T>::Drukuj()

{

cout << d << endl;

}

template <class T> void Dane<T>::Czytaj()

{

cin >> d;

}

main ()

{

Dane<Osoba> x;

x.Czytaj();

x.Drukuj();

return 0;

}

Typy pojemników

• Sekwencyjne, nazywane również ciągami; przykładem jest vector, do wartości sięga się za pomocą wskazania położenia wartości

• Asocjacyjne: służące do przechowywania par wartości (klucz, wartość), do wartości sięga się za pomocą wskazania klucza

• Budowane są one jako klasy wzorcowe, których parametrami są:

• typ przechowywanego elementu

• funkcja zajmująca się przydziałem i zwalnianiem pamięci (alokator)

Pojemniki z biblioteki STL (Standard Template Library)

• Sekwencyjne

• Pojemnik vector odpowiada tablicy, jest to ciąg optymalizowany ze względu na indeksowanie.

• Pojemnik list odpowiada liście dwustronnie dowiązanej, jest to ciąg optymalizowany ze względu na wstawianie i usuwanie elementów.

• Pojemnik deque odpowiada kolejce o dwóch końcach. Jest to ciąg optymalizowany w taki sposób, że operacje wykonywane na obu końcach są prawie tak efektywne jak dla listy, zaś efektywność indeksowania jest zbliżona do efektywności tej operacji na wektorze.

• Przykłady pojemników sekwencyjnych z STL

vector<float> ld; /* pusty wektor elementów typu float */

list <int> li; /* pusta lista elementów typu int */

list<punkt> lp; /* pusta lista elementów typu punkt */

Operacje	Pojemnik
	vector	list	deque
operacje na początku	trudne	łatwe	łatwe
operacje w środku	trudne	łatwe	trudne
operacje na końcu	łatwe	łatwe	łatwe
dostęp do elementów	natychmiastowy	żmudny	natychmiastowy

• Asocjacyjne (skojarzeniowe):

• map i multimap - do przechowywania ciągów par (klucz, wartość), nazwywane są również słownikami

• set i multiset - kluczem jest tutaj sam przechowywany element

Przykład klasy pojemnikowej typu wektor - wersja specjalizowana do przechowywania obiektów klasy osoba

/* J.Grębosz, Pasja C++ , wyd.2, str. 246-274 */

const int pojemnosc_wektora = 20 ;

class wektor{

osoba tabl[pojemnosc_wektora];

int ile_ob ;

public:

wektor() : ile_obiektow(0) { }

int wstaw(const osoba & nowy, int gdzie = -1);

void usun(int nr);

osoba & co_na(int pozycja)

{ return tabl[pozycja]; }

friend ostream& operator<<(ostream & s, wektor & x);

private:

void rozsun(int pozycja);

void zsun(int nr);

};

ostream& operator<<(ostream& s, wektor& spis)

{

stru << " " ;

for(int i = 0 ; i < spis.ile_ob ; i++)

stru << i << ") " << spis.tabl[i] << " " ;

stru << endl ;

return stru ;

}

void wektor::rozsun(int pozycja){

for(int i = ile_ob ; i > pozycja ; i--)

tabl[i] = tabl[i-1];

}

void wektor::zsun(int nr)

{

for(int i = nr ; i < ile_ob ; i++) {

tabl[i] = tabl[i+1];

}

int wektor::wstaw(const osoba & nowy, int gdzie)

{

if(ile_ob == pojemnosc_wektora) {

cout << "wektor juz zapelniony\n" ;

return 0;

}

if(gdzie < 0 || gdzie > ile_ob)

gdzie = ile_ob;

rozsun(gdzie);

tabl[gdzie] = nowy ;

ile_obiektow++;

return 1 ;

}

void wektor::usun(int nr){

if(nr < ile_ob) {

zsun(nr);

ile_obiektow--;

}

}

#include "osoba.h"

main() {

wektor studenci ;

osoba s1("Kowalski");

osoba s2("Nowak");

studenci.wstaw(s1);

studenci.wstaw(s2);

cout << "Zawartosc spisu studentow:\n"

<< studenci ;

osoba s3("Bender");

studenci.wstaw(s3);

cout << "Zawartosc spisu studentow:\n"

<< studenci ;

return 0 ;

}

• Plik osoba.h

class osoba {

char nazwisko[30] ;

public:

osoba(char* n= 0)

{ if (n) strcpy(nazwisko, n); }

friend ostream & operator<<(ostream &s, const osoba & o);

friend ostream & operator<<(ostream &s, const osoba * wsk);

};

ostream & operator<<(ostream &s, const osoba & o){

s << o.nazwisko ;

return s ;

}

ostream & operator<<(ostream &s, const osoba * wsk){

s << wsk->nazwisko ;

return s ;

}

Przykład klasy pojemnikowej typu wektor - wersja z klasą wzorcową (szablonową)

/* J.Grębosz, Pasja C++, wyd.2, str. 246-274 */

#include <iostream.h>

#include <string.h>

const int pojemnosc_wektora = 15 ;

template <class twoj_typ>

class wektor{

twoj_typ tabl[pojemnosc_wektora];

int ile_ob ;

public:

wektor() : ile_ob(0) { }

int wstaw(const twoj_typ & nowy, int gdzie = -1);

void usun(int nr);

twoj_typ & co_na(int pozycja)

{ return tabl[pozycja] ; }

friend ostream & operator<<

(ostream & stru ,wektor<twoj_typ>& x);

private:

void wektor::rozsun(int pozycja);

void zsun(int nr);

};

template <class twoj_typ>

void wektor<twoj_typ>::rozsun(int pozycja)

{

for(int i = ile_ob; i > pozycja; i--)

tabl[i] = tabl[i-1];

}

template <class twoj_typ>

void wektor<twoj_typ>::zsun(int nr)

{

for(int i = nr ; i < ile_ob ; i++)

tabl[i] = tabl[i+1];

}

template <class twoj_typ>

int wektor<twoj_typ>::wstaw(const twoj_typ & nowy, int gdzie)

{

if(ile_ob == pojemnosc_wektora) {

cout << "wektor juz zapelniony\n" ;

return 0;

}

if(gdzie < 0 || gdzie > ile_ob)

gdzie = ile_obiektow;

rozsun(gdzie);

tabl[gdzie] = nowy ;

ile_obiektow++;

return 1 ;

}

template <class twoj_typ>

void wektor<twoj_typ>::usun(int nr)

{

if(nr < ile_ob.) {

zsun(nr);

ile_obiektow--;

}

}

template <class twoj_typ>

ostream & operator<<(ostream & stru, wektor<twoj_typ> &spis)

{

stru << " " ;

for(int i=0; i < spis.ile_ob ; i++)

stru << i << ") " << spis.tabl[i] << " " ;

stru << endl ;

return stru ;

}

#include <osoba.h>

main() {

wektor<osoba> studenci ;

osoba s1("Kowalski"), s2("Nowak");

studenci.wstaw(s1);

studenci.wstaw(s2);

cout << "Zawartosc spisu studentow:\n"

<< studenci ;

osoba s3("Bender");

studenci.wstaw(s3);

cout << "Zawartosc spisu studentow:\n"

<< studenci ;

wektor<osoba*> pracownicy;

osoba *wsk1;

wsk1=new osoba("Adamska");

osoba *wsk2;

wsk2=new osoba("Kunik");

osoba wsk3("Hercen");

pracownicy.wstaw(wsk1);

pracownicy.wstaw(wsk2);

pracownicy.wstaw(&wsk3,0);

cout << "Zawartosc spisu pracownikow:\n" << pracownicy;

wektor<char> literki;

literki.wstaw('b');

literki.wstaw('c');

literki.wstaw('a',0);

cout << "Pojemnik zawiera literki:\n" << literki;

return 0;

}

Przykłady użycia klasy pojemnikowej vector z biblioteki STL

(por. wykład 4)

• Pojemnik klasy vector automatycznie rozszerza się, gdy zachodzi tego potrzeba.

Przykład:

#include <vector>

#include <iostream>

using namespace std;

void main()

{

vector <int> vi;

// czytaj z klawiatury liczby, aż zostanie wpisane 0

for (;;)

{

int robocza;

cout<<"Wpisz liczbe; napisnij 0 aby zakonczyc" <<endl;

cin>>robocza;

if (robocza == 0 ) break;

vi.push_back(robocza); // wstaw liczbę na koniec buforu vi

}

cout<< "Wstawiles "<< vi.size()

<<" elementow do pojemnika " << endl;

}

Użyte funkcje:

push_back() - dodaj element na końcu pojemnika, zwiększ o 1 liczbę elementów przechowywanych

w pojemniku

size() - podaj liczbę elementów przechowywanych w pojemniku

• Przykład:

#include <vector>

#include <iostream>

#include <string>

using namespace std;

void main()

{

vector <string> vs;

for (;;)

{

string robocza;

cout<<"Wpisz tekst i nacisnij Enter; aby zakoczyc wpisz \"stop\" "

<<endl;

cin>>robocza;

if (robocza == "stop" ) break;

vs.push_back(robocza);

}

cout<< " Wstawiles "<< vs.size() <<" elementow do pojemnika "

<< endl;

}

• Dostęp do obiektów przechowywanych w pojemniku realizowany jest za pomocą operatora [] - szybki dostęp kosztem nie sprawdzania zakresu indeksu lub funkcji at().- z kontrolą indeksów, zwracany jest wtedy wyjątek std::out_of_range.

Przykład: drukowanie składowych wektora rozdzielanych spacją

#include <iostream>

#include <vector>

using namespace std ;

void drukuj(vector<int> &);

int main()

{

int i ;

int t[] = {1,2,3,4,5,6,7,8,9,10} ;

vector<int> v(t,t+10);

drukuj(v);

return 0;

}

void drukuj(vector<int> &v)

{

cout << '{ ' ;

for (int i=0 ; i<v.size(); i++)

cout << v[i] << ' ' ; // dostęp do elementów wektora

cout << '}' << endl;

}

• Modyfikowanie elementu pojemnika

#include <vector>

#include <iostream>

#include <string>

using namespace std;

void main()

{

vector <string> vs;

string roboczy = "Dzien dobry";

vs.push_back(roboczy);

cout<<"Wstawiono za pomoca []: "<< vs[0] <<endl;

cout<<"Wstawiono za pomoca at(): "<< vs.at(0) <<endl;

roboczy = "Witam";

vs[0] = roboczy;

cout<<"Modyfikacja za pomoca []: "<< vs[0] <<endl;

roboczy = "Czesc";

vs.at(0) = roboczy;

cout<<"Modyfikacja za pomoca at(): "<< vs.at(0) <<endl;

}

• Automatyczna realokacja pojemnika i ochrona przed nią

Pojemnik automatycznie zwiększa pamięć, gdy tego potrzebuje. Oznacza to kopiowanie przechowywanych obiektów w inne miejsce. Nie zawsze to sprzyja wydajności.

Przykład:jedna z strategii postępowania - aloakacja wystarczająco dużej pamięci, gdy potrafimy przewidzieć potrzeby. Np. wiemy, że serwer pocztowy potrzebuje dużo pamięci tylko w godzinach szczytu i potrafimy to zapotrzebowanie oszacować.

#include <iostream>

#include <vector>

using namespace std;

// uproszczona wiadomość pocztowa

struct message { char text[1000];};

class MailServer {

public:

bool RushHour() const; // czy godziny szczytu

bool MoreMessages() const; // czy nadchodzą dalsze wiadomości

message& GetNewMsg() const; // pobierz wiadomość

};

bool MailServer::RushHour() const

{

bool rush = true;

return rush;

}

bool MailServer::MoreMessages() const

{

bool more = true;

return more;

}

message& MailServer::GetNewMsg() const

{

static message msg;

return msg;

}

void main()

{

MailServer server;

vector <message> vm;

if (server.RushHour())

vm.reserve(5000); // zarezerwuj dostaczenie dużo pamięci

while (server.MoreMessages())

{

static int count =0;

vm.push_back( server.GetNewMsg() );

if (count > 5000)

break;

}

}

Przglądanie elementów pojemnika czyli iteratory

• Iterator jest to obiekt, który pełni rolę podobną do wskaźnika: wskazuje na element pojemnika i posiada co najmniej takie własności jak:

• może być zwiększany za pomocą operatora ++ i wskazuje wtedy następny element

• można za jego pośrednictwem docierać do zawartości wskazywanego elementu pojemnika (podobnie do dereferencji wskaźnika) posługując się notacją *it, gdzie it jest iteratorem pojemnika

• dwa iteratory tego samego pojemnika można porównywać co do równości lub nierówności za pomocą operatora ==

• Rodzaje iteratorów:

• iterator wejściowy: pozwala odczytywać (pobierać obiekty z pojemnika) po kolei wszystkie elementy pojemnika, umie poruszać się tylko do przodu,

• iterator wyjściowy: pozwala modyfikować kolejne obiekty w pojemniku, umie poruszać się tylko do przodu,

• iterator chodzący do przodu: umie odczytywać i modyfikować obiekty w pojemniku, umie poruszać się tylko do przodu,

• iterator dwukierunkowy: umie odczytywać i modyfikować obiekty w pojemniku, umie poruszać się w obydwu kierunkach

• iterator o swobodnym dostępie: umie odczytywać i modyfikować obiekty w pojemniku, umie skoczyć w dowolne miejsce w pojemniku, by pokazać na schowany tam obiekt

• Każda klasa pojemnikowa biblioteki STL dostarcza podstawowy typ iteratora o nazwie iterator, do wskazywania elementów.

• Przykład: w klasie vector iterator o nazwie iterator pozwala przeglądać elementy po kolei. Iterator ten musi być zainicjalizowany - wykorzystywana jest do tego funkcja begin(), która zwraca adres pierwszego elementu w danym pojemniku. Funkcja end() zwraca adres pozycji za ostatnim elemenetem pojemnika (analogia do znaku kończacego napis w C). Dla iteratora zdefiniowano podobne operacje jak dla wskaźnika - za pomocą odpowiednio przeciążonych funkcji operatorowych.

#include <iostream>

#include <vector>

using namespace std;

void main()

{

vector <double> zarobki;

zarobki.push_back(2300.2);

zarobki.push_back(1860.4);

zarobki.push_back(3450.);

vector<double>::iterator p = zarobki.begin();

while ( p != zarobki.end())

{

cout<<"Zarobki przed podwyzka: "<< *p <<endl;

*p = *p * 1.15;

cout<<"Zarobki po 15% podwyzce: "<< *p <<endl;

p++;

}

}

Przykład listy podwójnie dowiązywanej z iteratorami

/* J.Grębosz, Pasja C++, wyd.2, str. 336-378 */

// plik Dlista.h

template <class typOBJ> class iteratorL ; // iterator

// Wzorzec listy podwójnie dowiązywanej

template <class typOBJ> class DLista{

struct wezel {

typOBJ * wskobj ;

wezel * nastepca ;

wezel * poprzednik;

wezel():nastepca(NULL),wskobj(NULL),poprzednik(NULL)

{ }

};

wezel *pierwszyW ;

wezel *ostatniW ;

int dlugosc ;

public:

typedef iteratorL<typOBJ> itLis ;

DLista() {

pierwszyW = ostatniW = NULL;

dlugosc = 0 ;

}

~DLista();

void wstaw(typOBJ & obj, itLis & iter);

void wstaw(typOBJ & obj, int nr)

{

itLis iter(*this);

iter.na_wezel(nr) ;

wstaw(obj, iter) ;

}

void wstaw(typOBJ & obj)

{

itLis iter(*this);

iter.za_koniec();

wstaw(obj, iter) ;

}

void usun(itLis & iter);

void usun(int nr)

{

itLis it(*this);

usun(it.na_wezel(nr)) ;

}

int rozmiar() const

{

return dlugosc ;

}

private:

void daje_na_poczatek(wezel* nowyW, itLis & iter);

void daje_w_srodku(wezel* nowyW, itLis & iter);

void daje_na_koniec(wezel* nowyW);

void usuwam_pierwszy(itLis & iter);

void usuwam_ostatni(itLis & iter);

void usuwam_ze_srodka(itLis & iter);

friend ostream & operator<<(ostream & stru, DLista<typOBJ> & x);

friend class iteratorL<typOBJ> ;

};

template <class typOBJ>

void DLista<typOBJ>::wstaw(typOBJ & obj, itLis & iter)

{

wezel * nowyW = new wezel ;

nowyW->wskobj = &obj ;

dlugosc++ ;

if(iter.wybranyW !=NULL)

{

if(iter.wybranyW==pierwszyW)

daje_na_poczatek(nowyW, iter);

else

daje_w_srodku(nowyW, iter);

}

else daje_na_koniec(nowyW);

}

template <class typOBJ>

void DLista<typOBJ>::daje_na_poczatek(wezel* nowyW,itLis& iter)

{

pierwszyW = nowyW ;

nowyW->nastepca = iter.wybranyW ;

iter.wybranyW->poprzednik = nowyW ;

nowyW->poprzednik = NULL ;

iter.wybranyW = nowyW ;

}

template <class typOBJ>

void DLista<typOBJ>::daje_w_srodku(wezel* nowyW, itLis & iter)

{

(iter.wybranyW->poprzednik)->nastepca = nowyW;

nowyW->nastepca = iter.wybranyW ;

nowyW->poprzednik=iter.wybranyW->poprzednik;

iter.wybranyW->poprzednik = nowyW ;

}

template <class typOBJ>

void DLista<typOBJ>::daje_na_koniec(wezel* nowyW)

{

if(!pierwszyW)

pierwszyW = nowyW ;

else {

ostatniW->nastepca = nowyW ;

nowyW->poprzednik = ostatniW ;

}

ostatniW = nowyW ;

}

template <class typOBJ>

void DLista<typOBJ>::usun(itLis & iter)

{

if(iter.wybranyW == NULL)return ;

dlugosc-- ;

if(iter.wybranyW == pierwszyW)

usuwam_pierwszy(iter);

else

{

if(iter.wybranyW == ostatniW)

usuwam_ostatni(iter);

else

usuwam_ze_srodka(iter);

}

}

template <class typOBJ>

void DLista<typOBJ>::usuwam_pierwszy(itLis & iter)

{

pierwszyW = pierwszyW->nastepca;

delete iter.wybranyW ;

iter.wybranyW = pierwszyW ;

pierwszyW->poprzednik = NULL ;

}

template <class typOBJ>

void DLista<typOBJ>::usuwam_ze_srodka(itLis & iter)

{

wezel * poprzW = iter.wybranyW->poprzednik;

poprzW->nastepca = iter.wybranyW->nastepca ;

(iter.wybranyW->nastepca)->poprzednik = poprzW;

delete iter.wybranyW ;

iter.wybranyW = poprzW ;

}

template <class typOBJ>

void DLista<typOBJ>::usuwam_ostatni(itLis & iter)

{

wezel * poprzW = iter.wybranyW->poprzednik;

poprzW->nastepca = NULL ;

ostatniW = poprzW ;

delete iter.wybranyW ;

iter.wybranyW = NULL ;

}

template <class typOBJ>

DLista<typOBJ>::~DLista()

{

itLis iter(*this) ;

for(int i = 0 ; i < dlugosc ; i++)

delete (iter++).wybranyW ;

}

template <class typOBJ>

ostream & operator<<(ostream & stru , DLista<typOBJ> & spis)

{

iteratorL<typOBJ> skoczek(spis) ;

for(int i = 0 ; i < spis.rozmiar() ; i++)

{

stru << i << ") " << *(skoczek++) << " " ;

if(!( (i+1)%3 ))

stru << endl ;

}

stru << endl ;

return stru ;

}

// wzorzec iteratora

template <class typOBJ> class iteratorL

{

protected:

friend class DLista<typOBJ> ;

DLista<typOBJ>::wezel * wybranyW ; // wskaźnik do aktualnego węzeła listy

DLista<typOBJ> & pojemnik ; // referencja do obsługiwanego pojemnika

public:

iteratorL(DLista<typOBJ> & pojem) : pojemnik(pojem)

{

wybranyW=pojemnik.pierwszyW;

}

iteratorL & na_poczatek()

{

wybranyW = pojemnik.pierwszyW ;

return *this ;

}

iteratorL & na_koniec()

{

wybranyW = pojemnik.ostatniW;

return *this ;

}

iteratorL & za_koniec()

{

wybranyW = NULL ;

return *this ;

}

iteratorL & operator++()

{

wybranyW = wybranyW->nastepca ;

return *this;

}

iteratorL & operator--()

{

wybranyW = wybranyW->poprzednik ;

return *this;

}

iteratorL operator++(int)

{

iteratorL stary = *this;

++*this;

return stary;

}

iteratorL operator--(int)

{

iteratorL stary = *this;

--*this;

return stary;

}

typOBJ & operator*()

{

return *(wybranyW ->wskobj) ;

}

iteratorL & na_wezel(int nr);

iteratorL & operator=(const iteratorL & prawy)

{

wybranyW = prawy.wybranyW ;

return *this;

}

int operator==(const iteratorL & prawy)

{

if(wybranyW == prawy.wybranyW) return 1 ;

else return 0 ;

}

int operator!=(const iteratorL & prawy)

{

if(wybranyW != prawy.wybranyW) return 1 ;

else return 0 ;

}

operator int()

{

if(wybranyW != NULL) return 1;

else return 0;

}

};

template <class typOBJ>

iteratorL<typOBJ> & iteratorL<typOBJ>::na_wezel(int nr)

{

wybranyW = pojemnik.pierwszyW ;

for(int i = 0 ; i < nr ; i++, ++(*this) );

return *this ;

}

// Lista wykorzystana jest do przechowywania opisów punktów

// kontrolnych biegu terenowego

#include <iostream.h>

#include <iomanip.h>

#include <string.h>

#include "osoba.h"

#include "Dlista.h"

main()

{

osoba

punktD("Stary Dab"),

punktG("Glaz nad strumieniem"),

punktA("Ambona mysliwska"),

punktW("Wyspa"),

punktKP("Kurhan"),

punktKA("Kamieniolom");

DLista<osoba> trasa ; // definicja pojemnika

// organizator biegu ustawia kolejne punkty kontrolne

iteratorL<osoba> organizator(trasa);

trasa.wstaw(punktD, organizator);

trasa.wstaw(punktG, organizator);

trasa.wstaw(punktA, organizator);

trasa.wstaw(punktW, 1);

trasa.wstaw(punktKP, organizator);

cout << trasa << endl;

cout << "Wyspa na zlej pozycji, skorygujemy to\n" ;

trasa.usun(1);

organizator.na_wezel(3) ;

trasa.wstaw(punktW, organizator);

cout << trasa << endl;

// mamy dwóch uczestników, którzy rozpoczynają bieg z dwóch przeciwstawnych

// końców

cout << "---- Dwa przeciwbiezne iteratory ------\n";

iteratorL<osoba> Kasia(trasa);

iteratorL<osoba> Marek(trasa);

Marek.na_koniec();

// --- przebiegniecie trasy

cout << setw(20) << "Kasia:"<<" "<< setw(20) << "Marek:"<<endl ;

for(int i = 0 ; i < trasa.rozmiar() ; i++,Kasia++)

cout<< setw(20)<< *Kasia << " "

<< setw(20) << *(Marek--)<< endl ;

cout << endl;

cout << "Dla utrudnienia dolaczamy kamieniolom\n";

trasa.wstaw(punktKA, 3);

cout << trasa <<endl;

// rozpoczynamy jeszcze raz

Kasia.na_koniec();

Marek.na_poczatek();

cout << setw(20) << "Kasia:"<<" "<< setw(20) << "Marek:"<<endl ;

for(int i = 0 ; i < trasa.rozmiar() ; i++)

cout << setw(20) << *(Kasia--) << " "

<< setw(20) << *(Marek++) << endl ;

cout << endl;

cout << "Ktos nie umie plywac, wiec usuniecie wyspy\n" ;

trasa.usun(3);

cout << trasa ;

// oszczedzmy sobie juz biegania.....

}

Złożone operacje wykonywane na pojemnikach czyli algorytmy

• Wiele operacji może mieć zastosowania do pojemnika, niezależnie od rodzaju przechowywanych w nim elementów, np. zliczanie obiektów, kopiowanie, wyszukiwanie, sortowanie.

• Definiowane są one w postaci funkcji wzorcowych, nazywanych algorytmami, dla których parametrem są typy iteratorów dostarczających im argumenty.

• Algorytmy nie są funkcjami składowymi klas pojemnikowych, działają na elementach pojemników tylko pośrednio przez iteratory.

Przykład 1: kopiowanie

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

using namespace std ;

main()

{ int t[5] = { 1, 2, 3, 4, 5 } ;

vector<int> v(t, t+5) ; /* v zawiera : 1, 2, 3, 4, 5 */

list<int> l(8, 0) ; /* lista 8 elementów równych 0 */

void drukuj(vector<int>) ;

void drukuj(list<int>) ;

cout << "lista poczatkowa : " ; drukuj(l) ;

copy (v.begin(), v.end(), l.begin()) ;

cout << "lista po 1-szym kopiowaniu : " ; drukuj(l) ;

l.erase(l.begin(), l.end()) ; /* l jest teraz pusta */

copy (v.begin(), v.end(), inserter(l, l.begin())) ;

cout << "lista po 2-gim kopiowaniu : " ; drukuj(l) ;

}

void drukuj(list<int> l)

{ list<int>::iterator il ;

for (il=l.begin() ; il!=l.end() ; il++) cout << *il << " " ;

cout << "\n" ;

}

1

20

---