Klasy pojemnikowe
" jedno z podstawowych narzędzi budowy programów
obiektowo orientowanych  sprawiają, \
e programy takie
łatwiej konstruować
" klasa pojemnikowa (kolekcja)  klasa której obiekty mogą
zawierać i manipulować obiektami innych klas
" w C++ - część biblioteki standarowej, realizowana zwykle
przy u\
yciu szablonów klas
" potrzeba u\
ywania:
o rozwiązując problem nie wiemy z góry ile obiektów
danego rodzaju będziemy potrzebować, ani jaki
będzie ich czas \
ycia
o wyjście  zastosowanie pojemnika, który przechowuje
i manipuluje potrzebną ilością obiektów; powiększa
lub zmniejsza swoją pojemność w miarę potrzeb
Pojemniki sekwencyjne
" najprostszy rodzaj pojemników  takie, w których obiekty
mo\
na ponumerować (uporządkować liniowo)
" mo\
liwe ró\
ne realizacje ró\
niące się kosztem wstawienia,
usunięcia i dostępu do elementu w sekwencji:
o wektor (vector)
o lista (list)
o talia (deque)
" wektor  pojemnik w którym kolejne obiekty zajmują
przylegające miejsca w pamięci  uogólnienie tablicy
jednowymiarowej
" wektor to coś więcej ni\
tablica  wyposa\
ony jest w
dodatkową inteligencję pozwalający na przykład na:
o zapisanie zawartości pojemnika na dysk
o wczytanie zawartości z dysku
o wsadzenie obiektu do pojemnika na określone
miejsce
o usunięcie obiektu na określonej pozycji z pojemnika
o wypisanie ilości elementów zawartych w pojemniku
o wypisanie zawartości pojemnika
Cechy wektora
" swobodny dostęp do wszystkich elementów (taki sam czas
dostępu do ka\
dego elementu zawartego w pojemniku)
" gorsze własności przy usuwaniu bądz
wstawianiu
elementów  konieczność reorganizacji wektora, by
wstawianie zachowało porządek, zaś usuwanie nie robiło
dziur
o koszt wstawiania/usuwania zale\
y od pozycji
elementu w wektorze
o koszt wstawiania/usuwania  liniowa funkcja
odległości od końca wektora
" inne realizacje pojemników sekwencyjnych mają inne
własności (np. lista  gorszy dostęp, łatwiejsze
wstawianie/usuwanie)
Przykład  pojemnik typu wektor do gromadzenia wizytówek
#include
#include
class wizytowka {
char *imie;
char *nazw;
public:
wizytowka(char *im="", char* na="");
wizytowka(const wizytowka &w);
~wizytowka();
wizytowka & operator=(const wizytowka &w);
friend ostream & operator<<(ostream & s, const wizytowka & w);
friend ostream & operator<<(ostream & s, const wizytowka *wsk);
};
wizytowka::wizytowka(char *im, char *na)
{
imie=new char[strlen(im)+1];
strcpy(imie,im);
nazw=new char[strlen(na)+1];
strcpy(nazw,na);
}
wizytowka::~wizytowka()
{
delete imie;
delete nazw;
}
wizytowka::wizytowka(const wizytowka &w)
{
imie=new char[strlen(w.imie)+1];
strcpy(imie,w.imie);
nazw=new char[strlen(w.nazw)+1];
strcpy(nazw,w.nazw);
}
wizytowka & wizytowka::operator=(const wizytowka &w)
{
delete imie;
delete nazw;
imie=new char[strlen(w.imie)+1];
strcpy(imie,w.imie);
nazw=new char[strlen(w.nazw)+1];
strcpy(nazw,w.nazw);
return *this;
}
ostream & operator<<(ostream & s, const wizytowka & w)
{
s << w.imie << " " << w.nazw;
return s;
}
ostream & operator<<(ostream & s, const wizytowka *wsk)
{
s << wsk->imie << " " << wsk->nazw;
return s;
}
class wektor {
static const int delta=3;
wizytowka *tabl;
int max,ile;
public:
wektor(int size=delta);
~wektor();
void wstaw(const wizytowka &nowa, int gdzie=-1);
void usun(int nr);
wizytowka & operator[](int p) {return tabl[p];}
friend ostream & operator<<(ostream &s, const wektor &x);
void raport();
private:
void kopiuj(int pm);
void rozsun(int p);
void zsun(int p);
};
// ----------- konstruktor --------------------------------
wektor::wektor(int size) : max(size), ile(size-delta)
{
tabl=new wizytowka[size];
}
wektor::~wektor()
{
delete [ ] tabl;
}
// ----------- powiększa lub zmniejsza rozmiary wektora ----------
void wektor::kopiuj(int pm)
{
wizytowka *nowy;
int size;
if(pm>0)
max+=delta;
else
max-=delta;
size=max;
nowy=new wizytowka[size];
for(int i=0;i {
nowy[i]=tabl[i];
}
delete [ ] tabl;
tabl=nowy;
}
// ----------- robi miejsce na wstawienie elementu -------------------------
void wektor::rozsun(int p)
{
for(int i=ile; i>p; i--)
{
tabl[i]=tabl[i-1];
}
}
// ----------- usuwa  dziure --------------------------------
void wektor::zsun(int p)
{
for(int i=p; i {
tabl[i]=tabl[i+1];
}
}
// ----------- wstawia element na wybraną pozycję --------
void wektor::wstaw(const wizytowka &nowa, int gdzie)
{
if(ile==max) kopiuj(1);
if(gdzie<0||gdzie>ile) gdzie=ile;
rozsun(gdzie);
tabl[gdzie]=nowa;
ile++;
}
// ----------- usuwa element z wybranej pozycji ----------------
void wektor::usun(int nr)
{
if(nr>=ile) return;
if(max-ile==delta) kopiuj(-1);
if(nr {
zsun(nr);
ile--;
}
}
ostream & operator<<(ostream &s, const wektor &x)
{
for(int i=0; i s << " " << i+1 << ") " << x.tabl[i] << endl;
return s;
}
void wektor::raport()
{
cout << "Pojemnik na " << max << " wizytowki, zawiera "
<< ile << " :" << endl;
cout << *this;
}
main()
{
wizytowka prezes("Kazimierz","Marcinkiewicz"),
premier("Jaroslaw","Kaczynski"),
prezydent("Lech","Kaczynski"),
trener("Leo","Benhaaker"),
bramkarz("Artur","Boruc");
cout << "Polityka:\n\t premier:\t" << premier << endl;
cout << "\t prezes:\t" << prezes << endl;
cout << "\t prezydent:\t" << prezydent << endl;
cout << "Sport:\n\t trener:\t" << trener << endl;
cout << "\t bramkarz:\t" << bramkarz << endl;
 wektor album;
album.wstaw(trener);
album.wstaw(prezydent);
album.wstaw(prezes);
cout << "Raport po dopisaniu 3 pozycji do konca pojemnika:\n";
album.raport();
album.wstaw(bramkarz,1);
cout << "Raport po wpisie na pozycji 2:\n";
album.raport();
album.wstaw(premier,2);
cout << "Raport po wpisie na pozycji 3:\n";
album.raport();
album.usun(3);
cout << "Raport po usunieciu wpisu z pozycji 4:\n";
album.raport();
cout << "Na pozycji 3 jest: " << album[2] << endl;
wektor polityka;
polityka.wstaw(premier);
polityka.wstaw(prezes);
cout << "Raport z pojemnika polityka:\n";
polityka.raport();
}
" klasa wizytówka  omawiana poprzednio; nowość 
przedefiniowanie operatora<< dla argumentu wizytówka *
" klasa wizytówka: dynamicznie zadana tablica wizytówek,
aktualny maksymalny rozmiar tablicy, aktualna ilość
przechowywanych elementów
" rozmiar maksymalny  dopasowuje się do potrzeb,
kontroluje to parametr delta, zmiana rozmiaru
maksymalnego (połączona z kopiowaniem tablicy) 
procedura kopiuj(int pm)
" prywatne metody rozsun(int p) i zsun(int p)  wspierają
wstawianie i usuwanie elementów do tablicy
" konstruktor  tworzy tablicę o rozmiarze delta
" przeładowanie operatora operator[ ]  ułatwia dostęp do
elementów pojemnika
" metoda raport()  wypisuje rozmiar i zawartość pojemnika
Polityka:
premier: Jaroslaw Kaczynski
prezes: Kazimierz Marcinkiewicz
prezydent: Lech Kaczynski
Sport:
trener: Leo Benhaaker
bramkarz: Artur Boruc
Raport po dopisaniu 3 pozycji do konca pojemnika:
Pojemnik na 3 wizytowki, zawiera 3 :
1) Leo Benhaaker
2) Lech Kaczynski
3) Kazimierz Marcinkiewicz
Raport po wpisie na pozycji 2:
Pojemnik na 6 wizytowki, zawiera 4 :
1) Leo Benhaaker
2) Artur Boruc
3) Lech Kaczynski
4) Kazimierz Marcinkiewicz
Raport po wpisie na pozycji 3:
Pojemnik na 6 wizytowki, zawiera 5 :
1) Leo Benhaaker
2) Artur Boruc
3) Jaroslaw Kaczynski
4) Lech Kaczynski
5) Kazimierz Marcinkiewicz
Raport po usunieciu wpisu z pozycji 4:
Pojemnik na 6 wizytowki, zawiera 4 :
1) Leo Benhaaker
2) Artur Boruc
3) Jaroslaw Kaczynski
4) Kazimierz Marcinkiewicz
Na pozycji 3 jest: Jaroslaw Kaczynski
Raport z pojemnika polityka:
Pojemnik na 3 wizytowki, zawiera 2 :
1) Jaroslaw Kaczynski
2) Kazimierz Marcinkiewicz
" powy\
szy pojemnik  nie jest uniwersalny; nadaje się tylko
do gromadzenia i manipulacji obiektami klasy wizytówka
" mimo to oddaje istotę klasy pojemnikowej  obiektu do
gromadzenia i manipulacji obiektami innej klasy
" w wy\
ej zdefiniowanym pojemniku: dodanie obiektu do
pojemnika to: utworzenie jego kopii, kopię umieszczamy w
pojemniku  pojemnik bezpośredni
" inna mo\
liwość: pojemnik przechowuje nie obiekty, ale
adresy do nich  pojemnik pośredni; ten sam obiekt mo\
e
być jednocześnie w kilku pojemnikach (zmiana obiektu
będzie widziana we wszystkich pojemnikach)
" kiedy stosować pojemniki bezpośrednie/pośrednie?
o bezpośrednie  łatwiejsze w obsłudze, raczej do
składowania mniejszych obiektów
o pośrednie:
bardziej do składowania du\
ych obiektów
w sytuacjach gdy ten sam obiekt ma się znalez
ć
jednocześnie w kilku pojemnikach
mo\
e manipulować oprócz obiektami danej
klasy (dla której został powołany) obiektami klas
pochodnych)
" aby osiągnąć uniwersalność  realizacja klasy
pojemnikowej poprzez szablon klas
" definicja klasy wizytówka  identyczna jak w przekładzie
powy\
ej  zawarta w pliku wizytowka.h
#include
#include
template
class wektor {
static const int delta=3;
typA *tabl;
int max;
int ile;
public:
wektor(int size=delta);
~wektor();
void wstaw(const typA &nowa, int gdzie=-1);
void usun(int nr);
typA & operator[](int p) {return tabl[p];}
void raport();
friend ostream & operator<<(ostream &s, wektor &x)
{
for(int i=0; i s << " " << i+1 << ") " << x.tabl[i] << endl;
return s;
}
private:
void kopiuj(int pm);
void rozsun(int p);
void zsun(int p);
};
template
wektor::wektor(int size) : max(size), ile(size-delta)
{
tabl=new typA[size];
}
template
wektor::~wektor()
{
delete [ ] tabl;
}
template
void wektor::kopiuj(int pm)
{
typA *nowy;
int size;
if(pm>0)
max+=delta;
else
max-=delta;
size=max;
nowy=new typA[size];
for(int i=0;i {
nowy[i]=tabl[i];
}
delete [] tabl;
tabl=nowy;
}
template
void wektor::rozsun(int p)
{
for(int i=ile; i>p; i--)
{
tabl[i]=tabl[i-1];
}
}
template
void wektor::zsun(int p)
{
for(int i=p; i {
tabl[i]=tabl[i+1];
}
}
template
void wektor::wstaw(const typA &nowa, int gdzie)
{
if(ile==max) kopiuj(1);
if(gdzie<0||gdzie>ile) gdzie=ile;
rozsun(gdzie);
tabl[gdzie]=nowa;
ile++;
}
template
void wektor::usun(int nr)
{
if(nr>=ile) return;
if(max-ile==delta) kopiuj(-1);
if(nr {
zsun(nr);
ile--;
}
}
template
void wektor::raport()
{
cout << "Pojemnik na " << max << " elementy, zawiera "
<< ile << " :" << endl;
cout << *this;
}
ostream & operator<<(ostream & s,float* w)
{
s << *w;
return s;
}
#include "wizytowka.h"
main()
{
wizytowka prezes("Kazimierz","Marcinkiewicz"),
premier("Jaroslaw","Kaczynski"),
prezydent("Lech","Kaczynski"),
trener("Leo","Benhaaker"),
bramkarz("Artur","Boruc");
cout << "Polityka:\n\t premier:\t" << premier << endl;
cout << "\t prezes:\t" << prezes << endl;
cout << "\t prezydent:\t" << prezydent << endl;
 cout << "Sport:\n\t trener:\t" << trener << endl;
cout << "\t bramkarz:\t" << bramkarz << endl;
wektor album;
album.wstaw(trener);
album.wstaw(prezydent);
album.wstaw(prezes);
cout << "Raport po dopisaniu 3 pozycji do konca pojemnika:\n";
album.raport();
album.wstaw(bramkarz,1);
cout << "Raport po wpisie na pozycji 2:\n";
album.raport();
album.wstaw(premier,2);
cout << "Raport po wpisie na pozycji 3:\n";
album.raport();
album.usun(3);
cout << "Raport po usunieciu wpisu z pozycji 4:\n";
album.raport();
cout << "Na pozycji 3 jest: " << album[2] << endl;
wektor polityka;
polityka.wstaw(premier);
polityka.wstaw(prezes);
cout << "Raport z pojemnika polityka:\n";
polityka.raport();
wektor sport;
sport.wstaw(&bramkarz);
sport.wstaw(&trener,0);
wizytowka * ww=new wizytowka("Robert","Kubica");
sport.wstaw(ww,10);
cout << "Raport z pojemnika sport - pojemnika posredniego:\n";
sport.raport();
cout << "A teraz pojemnik na liczby rzeczywiste ...\n";
wektor dolar;
float d1=2.87, d2=2.8678, d3=2.8763;
dolar.wstaw(d1);
dolar.wstaw(d2);
dolar.wstaw(d3);
cout << "Raport z kursu dolara ...\n";
dolar.raport();
wektor euro;
float e1=3.8043, e2=3.7889, e3=3.8110;
euro.wstaw(&e1);
euro.wstaw(&e2);
euro.wstaw(&e3);
cout << "Raport z kursu euro ...\n";
euro.raport();
system("pause");
}
Polityka:
premier: Jaroslaw Kaczynski
prezes: Kazimierz Marcinkiewicz
prezydent: Lech Kaczynski
Sport:
trener: Leo Benhaaker
bramkarz: Artur Boruc
Raport po dopisaniu 3 pozycji do konca pojemnika:
Pojemnik na 3 elementy, zawiera 3 :
1) Leo Benhaaker
2) Lech Kaczynski
3) Kazimierz Marcinkiewicz
Raport po wpisie na pozycji 2:
Pojemnik na 6 elementy, zawiera 4 :
1) Leo Benhaaker
2) Artur Boruc
3) Lech Kaczynski
4) Kazimierz Marcinkiewicz
Raport po wpisie na pozycji 3:
Pojemnik na 6 elementy, zawiera 5 :
1) Leo Benhaaker
2) Artur Boruc
3) Jaroslaw Kaczynski
4) Lech Kaczynski
5) Kazimierz Marcinkiewicz
Raport po usunieciu wpisu z pozycji 4:
Pojemnik na 6 elementy, zawiera 4 :
1) Leo Benhaaker
2) Artur Boruc
3) Jaroslaw Kaczynski
4) Kazimierz Marcinkiewicz
Na pozycji 3 jest: Jaroslaw Kaczynski
Raport z pojemnika polityka:
Pojemnik na 3 elementy, zawiera 2 :
1) Jaroslaw Kaczynski
2) Kazimierz Marcinkiewicz
Raport z pojemnika sport - pojemnika posredniego:
Pojemnik na 3 elementy, zawiera 3 :
1) Leo Benhaaker
2) Artur Boruc
3) Robert Kubica
A teraz pojemnik na liczby rzeczywiste ...
Raport z kursu dolara ...
Pojemnik na 3 elementy, zawiera 3 :
1) 2.87
2) 2.8678
3) 2.8763
Raport z kursu euro ...
Pojemnik na 3 elementy, zawiera 3 :
1) 3.8043
2) 3.7889
3) 3.811
" uwaga  potrzeba przedefiniowania operatora<< dla klasy
float* - bez tego mielibyśmy wydruk adresów a nie
zawartości liczb
Inne pojemniki ogólnego przeznaczenia
sekwencyjne vector list deque
wektor lista talia
adaptery queue stack
kolejka stos
asocjacyjne set map
zbiór mapa
" wszystkie one są zaimplementowane w bibliotece
standardowej C++
" ich efektywne u\
ycie wymaga stosowania tzw. iteratorów 
klas współpracujących z pojemnikami, pełniących rolę
uogólnionych wskaz
ników
" szablony iteratorów są równie\
częścią biblioteki C++
Przykład: u\
ycie biblioteki standarowej (pojemnik wektor)
" potrzebne włączenie właściwego pliku nagłówkowego
#include
" podstawowe operacje:
o dopisywanie elementu do listy
push_back(element)
insert(iterator, element)
o usuwanie
pop_back()
erase(iterator)
o dostęp
przeładowanie operatora[ ]
#include
#include
#include
#include "wizytowka.h"
template
void raport(vector &x, char* tytul)
{
cout << "Raport z pojemnika " << tytul
<< " - liczba elementow: "<< x.size() << endl;
for(int i=0; i {
cout << " " << i+1 << ") " << x[i] << endl;
}
}
main()
{
wizytowka prezes("Kazimierz","Marcinkiewicz"),
premier("Jaroslaw","Kaczynski"),
prezydent("Lech","Kaczynski"),
trener("Leo","Benhaaker"),
bramkarz("Artur","Boruc");
cout << "Polityka:\n\t premier:\t" << premier << endl;
cout << "\t prezes:\t" << prezes << endl;
cout << "\t prezydent:\t" << prezydent << endl;
cout << "Sport:\n\t trener:\t" << trener << endl;
cout << "\t bramkarz:\t" << bramkarz << endl;
vector album;
album.push_back(trener);
album.push_back(prezydent);
album.push_back(prezes);
cout << "Raport po dopisaniu 3 pozycji do konca pojemnika:\n";
raport(album,"album");
album[1]=bramkarz;
cout << "Raport po wpisie na pozycji 2 (przepisuje element):\n";
raport(album,"album");
cout << "Wstawiamy przed pozycje 3\n";
album.insert(album.begin()+2,premier);
cout << "Raport po wpisie na pozycji 3:\n";
raport(album,"album");
cout << "Usuwanie elementow:\n";
album.pop_back(); // usuniecie ostatniego
album.erase(album.begin()+1);
cout << "Raport po usunieciu 2 pozycji:\n";
raport(album,"album");
 vector sport;
sport.push_back(&bramkarz);
sport.insert(sport.begin(),&trener);
wizytowka * ww=new wizytowka("Robert","Kubica");
sport.push_back(ww);
cout << "Raport z pojemnika sport - pojemnika posredniego:\n";
raport(sport,"sport");
}