Generičko programiranje

U računarstvu, generičko programiranje je tehnika koja dozvoljava da jedna promenljiva može da čuva različite tipove podataka (takozvana višeobličnost ili polimorfizam) sve dok su zadovoljeni određeni uslovi kao što su podklasa i pravilna deklaracija. Dakle, dozvoljava nam stvaranje funkcija i klasa koje ne zavise od tipa. Primer: vektor, lista, stek itd. Na primer, ako se želi napraviti lista koristeći generičnost, moguća deklaracija bi bila <T>, gde T predstavlja vrstu podataka. Kada se načini primerak može se napraviti ili . Prema listi se zatim postupa kao prema listi onog tipa podataka koji je naveden. Od objektno orijentisanih programskih jezika, programski jezici (1.5 i novije) podržavaju generičke tipove podataka. su počeli da podržavaju generičke tipove od verzije 2.0. Šabloni – osnova za generičko programiranje:  šablon je u stvari formula ili recept za stvaranje klase ili funkcije. Postoje funkcijski šabloni i šabloni klase.

Generičke funkcije i klase – [1]

Pod pojmom generičkog programiranja podrazumeva se izrada programskog koda koji se u nepromenjenom obliku može primeniti na različite tipove podataka.

U C jeziku se za generičko programiranje koriste predprocesorske makro naredbe, npr:

#define Kvadrat(x) x*x

Ovo je makro naredba kojom se deo koda koji je u zagradama označen sa x zamenjuje sa x*x. Makro naredbe nisu funkcije. One se realizuju u toku kompajliranja leksičkom zamenom teksta.

Primer:

Makro naredba:	Izvršava se kao:
int i; Kvadrat(i) * 3	int i; i*i*3
float x; x*Kvadrat(6.7)	float x; x*6.7*6.7
float x; x=Kvadrat(x+6.7)	float x; x=x+6.7*x+6.7 //greška

U prva dva primera pokazano je kako se ista makro naredba koristi za tipove i . Greška u trećem primeru, se može izbeći tako da se „argumenti“ makro naredbe napišu u zagradama tj.

#define Kvadrat(x) (x)*(x)

Problem kod makroa je da je kod makroa nepregledan i teško je uočiti – greške, budući da kompajler samo kod makroa nalepi umesto poziva i moguće su semantičke greške koje je vrlo teško otkriti

To je jedan od razloga zbog kojeg u C++-u imamo generičke (template) funkcije (funkcijske šablone). C++ je strogo tipizirani jezik, tj pri definiciji funkcije moramo navesti tipove parametara. dopušta korišćenje preopterećenih funkcija. To su funkcije koje imaju jednaka imena (i pripadaju istom dosegu – ) ali različitu listu parametara. Preopterećivanje funkcije ima nekoliko nedostataka: ukoliko želimo nešto promeniti u kodu funkcije moramo to učiniti na puno mesta, pa se povećava i mogućnost greške, ne možemo predvideti na kojim će sve tipovima korisnik hteti da pozove funkciju.

U C++ se isti efekat kao u C-u sa može postići korišćenjem definisanjem funkcija:

inline int Kvadrat(int x) {
    return x*x;
}
inline float Kvadrat(float x) {
    return x*x;
}
inline double Kvadrat(double x) {
    return x*x;
}

Preporuka: bolje je da se koriste funkcije nego makro naredbe, jer se time osigurava bolja kontrola tipova i izbegava mogućnost pojave prethodno opisane greške. Primetimo da sva tri tipa definicije funkcije Kvadrat imaju isti oblik:

T Kvadrat(T x) {
    return x*x;
}

gde T može biti ili . Ova definicija ima generički oblik. U C++ jeziku se može vršiti generičko definisanje funkcija, na način da se ispred definicije ili deklaracije funkcije, pomoću ključne reči , označi da T predstavlja „generički tip“.

template <class T> T Kvadrat (T x) {
    return x*x;
}

ili

template <typename T> T Kvadrat(T x) {
    return x*x;
}

Razlika u ova dva zapisa je u upotrebi ključne reči ili , ali značenje je potpuno isto. Izvršenje poziva funkcije se mora obaviti sa stvarnim tipovima:

int x,y;
y=Kvadrat<int>(x);

Pogodno je da se klase i funkcije mogu pisati generički, parametrizovano tipovima podataka. Takve generičke klase i funkcije nazivaju se u jeziku C++  šablonima (templates). Iz šablona se generišu stvarne klase, odnosno funkcije, za konkretne tipove. Generički mehanizam^[2] je u potpunosti statički -substitucija parametara je u vreme prevođenja. Funkcijski šablon se ne koristi dok kompajler ne naiđe na poziv generičke funkcije. Tek tada se stvara i prevodi nova varijanta funkcije u zavisnosti o tipu na kojem je funkcija pozvana. Taj proces stvaranja nove konkretne varijante funkcije iz funkcijskog šablona naziva se instancijacija. Tipovi se kod funkcijskih šablona prepoznaju automatski. Zbog toga se i definicija i implementacija takvih funkcija piše u .h datoteku. Kompajler tek u trenutku poziva funkcije može odrediti način kako se prevodi generička funkcija, stoga su generičke funkcije po upotrebi  ekvivalentne makro naredbama. Da bi se moglo izvršiti kompajliranje programa u kojem se koristi generička funkcija, kompajleru mora biti na raspolaganju potpuna definicija funkcije, a ne samo deklaracija funkcije kao što je slučaj kod upotrebe regularnih funkcija.

Generički tip T se može koristiti unutar funkcije za oznaku tipa lokalne promenljive:

template <class T> T Kvadrat(T x){
    T result=x*x;
    return result;
}
int main() {
    int i=5,k;                     
    float a=10.9,b;
    k=Kvadrat<int>(i);     
    b=Kvadrat<float>(a);
    cout <<k<<endl;
    cout<<b<<endl;
    return 0;
}

25
118.81

Ne mora se uvek, pri pozivu funkcije, specificirati generički tip ako se iz tipova argumenata nedvosmisleno može zaključiti koji se parametarski tip koristi.

int i=5,k;
float a=10.9,b;
k=Kvadrat(i);
b=Kvadrat(a);
cout <<k<<endl;
cout<<b<<endl;

Preporuka je ipak, da se uvek eksplicitno specifira parametarski tip. Mogu se definisati generičke funkcije sa više generičkih tipova. Primer:

template <class T, class U> t GetMin (T a, U b){
    return (a<b?a:b);
}

definiše funkciju sa dva argumenata kojima se pridružuju generički tipovi T i U. Moguće je izvršiti poziv funkcije na sledeći način: ili još jednostavnije

i=GetMin (j,l);

Iako su j i l različitog tipa, kompajler sam vrši konverzije integralnih tipova.

Generički klasni tipovi[3]

Pretpostavimo da radimo sa nekim skupom objekata koje želimo da nekako organizujemo. U tom slučaju koriste se klase koje se označavaju kao kolekcije (kolekcija=zbirka, skupljanje). One definišu objekte koji se koriste za organizaciju drugih objekata odgovarajućeg tipa u kolekcije na odgovarajući način. Moguće je u kolekciju dodavati objekte različitog tipa, ali onda imamo problem utvrđivanja tipa objekta prilikom njegovog korišćenja. Ako pokušamo da neki objekat iz ove kolekcije upotrebimo kao objekat neke druge klase, nailazimo na problem. Npr. neka smo omogućili da kolekciji mogu da se dodaju objekti klasa i . Ako, primera radi, pokušamo da upotrebimo neki objekat klase ili kao objekat klase , program neće biti preveden. Da bi se izbegli ovakvi problemi, treba definisati kolekciju tako da se onemogući slučajno dodavanje objekta pogrešnog tipa. Jedan način za rešenje ovog problema je definisati zasebne kolekcije koje mogu da sadrže samo objekte jednog tipa. Ali onda se javlja drugi problem – imaćemo za svaki tip objekta po jednu klasu koja definiše odgovarajuću kolekciju. Drugi, efikasniji način, su upravo generički tipovi. Oni omogućuju da se definiše samo jedna klasa kojom je kolekcija predstavljena. Svi objekti u kolekciji su istog tipa, ali sada postoji mogućnost da taj tip može biti proizvoljan. Na ovaj način, imamo jednu kolekciju koja može da se ponaša i kao kolekcija tačaka, i kao kolekcija duži i kao kolekcija stringova itd. Generički tip je klasni ili interfejsni tip koji ima jedan ili više parametara. Definicija konkretne klase ili interfejsa iz generičkog tipa vrši se dodavanjem konkretnog argumenta za svaki od parametara generičkog tipa.

public class LinkedList<T>{
    …
}

Parametar T se upotrebljava u definiciji metoda i polja gde postoji zavisnost od tipa ovog argumenta. Pojave ovog parametra u definiciji generičkog tipa se označavaju kao promenljive tipa, jer  će biti zamenjene konkretnom vrednošću tog tipa, na isti način kao što parametri metoda bivaju zamenjeni argumentum koji se prosledi metodu. Kreiranje klase iz datog generičkog tipa vrši se navođenjem odgovarajućeg argumenta za parameter unutar <>. Sva pojavljivanja parametra T u definiciji generičkog tipa biće zamenjena datim argumentum. Generički tip na taj način definiše skup tipova, dobijenih za različite vrednosti parametra tipa T. Kao argument za parameter T može se proslediti samo klasni ili interfejsni tip. Primitivni tipovi ne mogu da se koriste. Umesto njih koristimo odgovarajuće klase koje ih enkapsuliraju. Generički tip koji čuva vrednosti:

LinkedList<Double> temp= new LinkedList<Double>();
temp.addItem(10.8)

Pošto je tip parametra kompajler automatski umeće konverziju vrednosti 10.8 iz u . Možemo da definišemo generički tip koji definiše skup klasa koje obuhvataju par objekata proizvoljnog tipa. U tom slučaju definišemo generički tip sa dva parametra:

public class Par <TipKljuca, TipVrednosti> {

    public Par(TipKljuca kljuc, TipVrednosti vr) {

        this.kljuc = kljuc;
        this.vr = vr;
    }
    …
    private TipKljuca kljuc;
    private TipVrednosti vr;
}

Upotreba:

Par <String,String>unos =new Par<String,String>(“Milan”, “4445555”);

Oblast važenja parametarskog tipa je cela generička klasa, isključujući statičke članice klase. Statička polja ne mogu biti definisana promenljivom tipa, niti statički metodi mogu da imaju parametre ili povratne vrednosti koje su parametarskog tipa. Ukoliko generička klasa sadrži neko statičko polje, svaki tip proizveden iz datog generičkog tipa, imaće svoju kopiju statičkog polja. Neka generička klasa sadrži statičko polje za brojanje kreiranih objekata. Svaka klasa dobijena iz generičke za konkretan argument tipa imaće svoju kopiju ovog polja. Na taj način,

u klasi broji kreirane objekte ove klase

u klasi broji kreirane objekte ove klase itd.

Generički metod

Možemo da definišemo metod sa svojim nezavisnim skupom od jednog ili više parametara. Takav metod naziva se parametarski metod ili generički metod. Generički metod može da postoji i unutar obične klase.

public static <T> void ispisiSve(LinkedList lista){
    for(T objekat: lista)
    System.out.println(objekat);
}

<T> ispred koga se navodi ili ključna reč predstavlja parametarski tip (ili listu tipova) za generički metod. Ovde imamo samo jedan parametarski tip za metod , ali ih može biti više. Lista parametarskih tipova se uvek pojavljuje između uglastih zagrada i navodi se iza kvalifikatora pristupa, a pre povratne vrednosti metoda. Argument tipa će biti određen na osnovu parametra tipa koji je prosleđen pri pozivu metoda.

Nizovi i parametrizovani tipovi

Nizovi elemenata tipa dobijenog od generičkog tipa nisu dopušteni!

Kolekcije

kolekcija je skup generičkih tipova koje koristimo za kreiranje kolekcijskih klasa. Kolekcijska klasa je klasa koja organizuje skup objekata datog tipa na određen način (npr. lančane liste, stek,….). Najveći broj ovih klasa koje čine sistem kolekcija definisane su u paketu . Razmotrićemo sledeće generičke tipove:

• interfejsni tip - deklariše metode za iteriranje kroz jedan po jedan element kolekcije

• tip - ima strukturu dinamičkog niza, broj objekata koje možemo sačuvati se automatski povećava po potrebi.

• tip - dvostruko povezana lista, omogućeno je iteriranje u oba smera

Klasu koja definiše kolekciju objekata često nazivamo kontejnerskom klasom. Postoje tri osnovna tipa kolekcija koji organizuju objekte na različite načine:

• skupovi

• nizovi

• katalozi

Skup

Skup() je najjednostavnija kolekcija u kojoj objekti nisu na neki specijalan način uređeni I objekti se jednostavno dodaju skupu, bez ikakve kontrole gde idu. Možemo iterirati kroz sve objekte skupa, ispitati da li je neki objekat član skupa. Skup ne može da sadrži duplikate. Objekat možemo i obrisati iz skupa, ali samo ako imamo reference na njega u skupu.

Niz

Glavna karakteristika niza je da su objekti smešteni na linearan način, u proizvoljnom, fiksnom redosledu gde imamo početak i kraj. Kolekcije u opštem slučaju imaju sposobnost da se prošire da bi se smestio potreban broj objekata.Primeri:

• Nizovi

• Redovi

Pošto je niz linearan, moguće je dodati novi objekat na početak ili kraj ili umetnuti novi objekat iza date pozicije. Dobijanje objekta iz niza se može izvršiti na vise načina:

1. Može se selektovati prvi ili poslednji
2. Može se dobiti objekat sa date pozicije
3. Može se pretraživati niz unapred ili unazad da bi se ispitalo da li se neki objekat nalazi u nizu i slično

Iterator

Iterator je objekat koji se koristi za iteriranje kroz kolekciju, tj. pristup jednom po jednom objektu kolekcije. Upotreba iteratora omoguće upotrebu oblika for petlje karakterističnog za pretraživanje kolekcija. Bilo koji objekat koji predstavlja skup ili niz može da kreira objekat tipa . Objekat tipa sadrži reference na sve objekte kolekcije u nekom redosledu i njima se može pristupiti pomoću metoda interfejsa Iterator<>:

• -  vraća objekat tipa T i postavlja objekat da pri sledećem pozivu ovog metoda referiše na sledeći objekat kolekcije. Ako nema objekta koji će biti vraćen, izbacuje se izuzetak tipa

• - briše poslednji objekat vraćen pozivom metoda . Ako nije bio pozvan ili ako se pozove dva puta nakon poziva , biće izbačen izuzetak tipa

Primer:

Klasa primerak;

while(iterator.hasNext())
    primerak=iterator.next();

Ovde se podrazumeva da je iterator tipa i da čuva reference na objekat dobijen iz kolekcije. Jedan objekat koji implementira interfejs je za jednu iteraciju kroz kolekciju. Ukoliko je kasnije potrebno ponovo proći kroz sve elemente kolekcije , neophodno je kreirati novi objekat.

List iteratori

U paketu definisan je interfejs . Deklariše metode koji se koriste za kretanje kroz kolekciju napred i nazad, tako da se do objekta može doći vise nego jednom. interfejs nasleđuje interfejs.

Spisak metoda:

• -  kao kod

• - kao kod

• - vraća indeks objekta koji će biti vraćen pozivom metoda kao tip , ili vraća broj elemenata u listi ako je objekat na kraju liste

• – vraća prethodni objekat po redosledu u samoj listi. Koristimo ga za vraćanje kroz listu.

• – vraća true ako prethodni poziv vraća objekat.

• - vraća indeks objekta koji će biti vraćen sledećim pozivom metoda ili -1 ako je objekat na početku liste

• - briše poslednji objekat dobijen pozivom metoda ili . Ako ili nisu bili pozvani, izbacuje se izuzetak tipa , a ako operacija brisanja nije podržana za datu kolekciju, izbacuje se izuzetak tipa

• – dodaje argument neposredno pre objekta koji bi bio vraćen sledećem pozivom metoda ili iza objekta koji bi bio vraćen sledećim pozivom metoda . Poziv nakon dodavanja vraća dodati element, a za se ništa ne menja. Ako objekat ne može da se doda izbavuje se izuzetak tipa ukoliko postoji neki drugi razlog zbog kojeg dodavanje ne može da se izvrši.

• – menja poslednji objekat dobijen pozivom ili . I ovaj metod može da izbaci izuzetke tipa i .

definiše kolekciju sa elementima tipa T. Objekat radi kao i niz osim što dodatno raste automatski, kada je potreban veći kapacitet. Kao i nizovi, i sadrže reference na objekte, ne sam objekte. To je pravilo za sve kolekcije. se, za razliku od niza, karakteriše veličinom . Kapacitet je maksimalan broj objekata koje može da sadrži. Kapacitet je promenljiv, jer se automatski povećava kada se doda novi objekat u već pun vector. Metodom postavlja se minimalni kapacitet.

Primer:

v.ensureCapacity(150); /*ako je kapacitet objekta v manji od 150, kapacitet se uvećava na 150. AKo je 150 ili vise neće biti promenjen ovom naredbom.*/

Konstruktori

• – podrazumevani konstruktor kreira prazan podrazumevanog kapaciteta 10. Kapacitet se povećava za 50% ukoliko se doda element u već pun .

• - eksplicitno se zadaje kapacitet

Metode

• – vraća broj elemenata koji su smešteni u

• -  dodaje se objekat iza tekućeg poslednjeg objekta u

• – smešta se objekat na poziciju zadatu prvim argumentum, ostali se pomeraju za jedno mesto u desno.

• – postavljamo objekat u na poziciju zadatu prvim argumentum, briše se objekat koji je prethodno bio na toj poziciji.

• (lista) – dodaju se svi objekti druge kolekcije u

• ,lista)

• – vraća element na zadatoj poziciji

Činjenica da se kapacitet povećava za 50% svaki put kada se ArrayList popuni utiče na to da se memorija bespotrebno zauzima. Međutim, ovo može da se prevaziđe upotrebom metoda . Ovaj metod menja kapacitet tako da odgovara trenutnoj veličini.

names.trimToSize(); /*postavlja  kapacitet na trenutnu veličinu. Ako je veličina u trenutku izvršavanja metoda 30 i kapacitet se postavlja na 30. Naravno i dalje se mogu dodavati novi objekti u ArrayList.*/

Možemo dobiti i referencu iz vektora pozivanjem metoda .

ListIterator<String> it = names.listIterator(); /* sada je moguće kretati se u oba smera kroz ArrayList upotrebom metoda iz klase ListIterator. */
ListIterator <String>it = names.listIterator(2); /* ovim se dobija ListIterator objekat koji se odnosi samo na deo ArrayList, pri čemu je argument metoda listIterator() upravo prvi element date sekvence ArrayList. */
List <String>list = names.subList(2,5); /* dobija se podskup objekata iz ArrayList kao kolekcija tipa List<>. Argumetni metoda subList() su početak i kraj sekvence objekata koja čini podskup, pri čemu poslednji element nije uključen. */

Moguće su i kombinacije:

vraća podlistu objekata od pozicije 5 do pozicije 14 zaključno. Nakon toga se za datu listu poziva metod koji vraća list iterator nad elementima liste počevši od elementa sa indeksom 2, pa do kraja. To odgovara elementima polaznog sa indeksima od 7 do 14. Ovim iteratorom se kroz datu sekvencu objekata polaznog može kretati u oba smera. */

Metod omogućava da se elementi vektora dobiju u obliku običnog niza.

String[] data = names.toArray(new String[names.size()]); /* argument metoda toArray() mora biti niz elemenata istog tipa kao i elementi ArrayList  ili nadtipa. Ako niz nije dovoljne veličine da primi sve elemente ArrayList, kreiraće se novi niz i referenca na taj niz će biti vraćena. Ovde metod toArray() vraća niz String[] koji sadrži sve elemente ArrayList names u odgovarajućem redosledu.*/
String[] people = {“Bill”, “Barbara”, “Brian”};
List<String> nameList = java.util.Arrays.asList(people);

Statički parametarski metod definisan u klasi konvertuje niz elemenata datog tipa T u kolekciju. Argument metoda je niz koji se konvertuje i vraća se referenca tipa . Ova referenca se može proslediti kao argument konstruktoru klase :

ArrayList<String> names = new ArrayList(nameList); /* Time se dobija ArrayList koji sadrži elemente datog niza. */

Brisanje elemenata:

• – brisanje reference na objekat na zadatoj poziciji. Vraća se referenca  na uklonjeni objekat, tako da ostaje mogućnost da se sačuva referenca nakon što se ukloni iz .

• – brisanje prvog objekta sa zadatom referencom. Ukoliko je pronađen i uklonjen objekat, vraća se , inače

• - brišu se elementi sa indeksima od 2 do 4

• - ostaju samo elementi sa indeksima od 2 do 4

• – uklanja sve elemente iz

Da li je prazan može se utvrditi metodom . Ukoliko je veličina 0, metod vraća , inače . Ukoliko sadrži samo elemente, to ne znači da je prazan tj da je veličina 0 ili da će metod vratiti . Da bi se ispraznio elementi tj reference na objekte moraju biti uklonjene, a ne samo postavljene na .

Pretraživanje :

• – vraća poziciju datog objekta u

• – vraća prvu poziciju datog objekta u , počevši od pozicije zadate kao drugi argument

Za sortiranje elemenata kolekcije najbolje je implementirati interfejs . On deklariše samo jedan metod – vraća -1, 0 ili 1 ako je objekat manji, jednak ili veći od argumenta. Ako je interfejs implementiran za tip objekta smešten u kolekciji, možemo samo objekat kolekcije predati kao argument metodu interfejsa .

Povezana lista ()

Konstuktori

• bez argumenata

• sa argumentom koji kreira objekat koji sadrži objekte kolekcije koja se prosleđuje kao argument

Metode

• – kao kod klase

• – dodaje objekat na početak liste

• – dodaje objekat na kraj liste

• – kao kod klase Vector<>

• getFirst(),getLast()

• remove(),removeFirst(),removeLast()

• set()

• size() – vraća broj elemenata liste

Meotdom dobija se objekat nad listom. Metodom objekat , kao i kod klase

Katalozi

Katalog () takođe nazivamo i rečnikom. Zajedno se čuvaju i ključ i objekat. Svaki objekat je jedinstveno određen svojim ključem. Svi ključevi, iz tog razloga, moraju da budu različiti. Izdvajanje objekata iz kataloga vrši se pomoću odgovarajućeg ključa, jer ključ određuje gde se u katalogu nalazi objekat. Sve klase za rad sa katalozima implementiraju generički interfejs . Razmatraćemo generičku klasu .  Implementacija kataloga pomoću generičke klase podrazumeva da su parovi ključ/objekat smešteni u niz. Indeks u nizu dobija se na osnovu ključa za šta se koristi metod .Ovaj metod nasleđuje se iz klase i on proizvodi podrazumevani heškod, osim ako nije predefinisan u nekoj od izvedenih klasa. Stoga, bilo koji objekat može da bude korišćen kao ključ. Na osnovu njega se metodom generiše heškod kojim se određuje indeks para sa datim ključem u nizu.

Heširanje

Ako želimo da kao ključeve koristimo objekte koje sami definišemo, treba da predefinišemo metod iz klase . Da bi se obezbedila potrebna funkcionalnost, nova verzija treba da vrati kada dva različita objekta sadrže iste vrednosti. Takođe, moguće je predefinisati metod tako da raspodela bude prilično uniformna na skupu mogućih vrednosti za ključeve. Jedan način je da se za svaki podatak-članicu klase generiše ceo broj npr. postojećim metodom koji se zatim množi prostim brojem (svaki član različitim) i na kraju se dobijeni rezultati sumiraju. Generisanje celog broja za podatak-članicu klase se obično vrši pozivanjem metoda . Proste brojeve treba birati tako da ne budu preveliki, kako rezultat ne bi bio van opsega za . Kad god je podatak-članica klase objekat neke druge klase, a ne primitivnog tipa, neophodno je implementirati metod za datu klasu.

Konstuktori za

• – podrazumevani, kreira katalog podrazumevanog kapaciteta 16, a podrazumevani load faktor je 0.75

• – kreira katalog datog kapaciteta, sa podrazumevanim load faktorom

• – kreira katalog sa datim kapacitetom i load faktorom

• četvri konstuktor kreira katalog na osnovu postojećeg kataloga

Kapacitet kataloga je broj parova ključ/objekat koji mogu da se čuvaju. Automatski se povećava, ako je neophodno.  Poželjno je da se za kapacitet kataloga zadaje prost broj, kako bi se izbegla kolizija. Faktor punjenja (load faktor) se koristi za odlučivanje kada kapacitet heš tabele treba da se poveća . Kada veličina tabele dostigne vrednost proizvoda faktora punjenja i kapaciteta, kapacitet se automatski povećava dva puta uz dodavanje 1 da bi se osiguralo da je novi kapacitet barem neparan, ako već nije prost.

Smeštanje, dobijanje i uklanjanje objekata kataloga:

• – smešta objekat u katalog koristeći ključ .

• – uklanja par povezan sa ključem ako postoji i vraća referencu na objekat. Ukoliko ne postoji odgovarajući par sa datim ključem, ili je objekat pridružen ključu , vraća se .

• – vraća objekat sa istim ključem kao . Objekat ostaje u katalogu. Ako nema nijednog objekta sa datim ključem, ili je smešteno umesto objekta, vraća se

Ako vrati , ne znamo da li objekat povezan sa ključem ne postoji ili je objekat . Za ovo služi metod koji kao argument ima dati ključ. On vraća ako je ključ smešten u katalogu.

interfejs obezbeđuje 3 načina za dobijanje kolekcionog pregleda sadržaja kataloga:

• – vraća objekat koji referiše na ključeve kataloga

• – vraća objekat koji referiše na parove ključ/objekat – svaki par je objekat tipa je generički interfejsni tip definisan unutar interfejsa

• – vraća objekat koji referiše na objekte iz kataloga.

Generičke klase

Na isti način, kao što se definišu generičke funkcije, mogu se definisati I generičke klase. Definicija članova klase se provodi pomoću generičkog tipa. Na primer

template<class T> class array {
    ...
}

pomoću koje se može realizovati nizovi proizvoljnog tipa. Na primer deklaracijom

array<int> myints(5);

se formira niz od 5 celobrojnih elemenata, a sa

array<string> mystrings(5);

se formira niz od 5 stringova.

template <class T> class array{
    T *m_pbuff;
    int m_size;
    public:
    array(int N = 10): 
        m_size(N) {
            m_pbuff=new T[N];
        }
    ~array() {
        delete []
        m_pbuff;
    }
    int size() {
        return m_size;
    }
    void set(int x, T value);
    T get(int x);
    T & operator [] (int i){
        return m_pbuff[i];
    }
    const T & operator [] (int i) const {
        return m_pbuff[i];
    }
}
template <class T> void array<T>::set(int x, T value){
    m_pbuff[x]=value;
}
template <class T> T array<T>::get(int x){
    return m_pbuff[x];
}

i funkcije smo mogli definisati unutar definicije klase. One su definisane izvan klase kako bi se pokazalo da se tada uvek ispred definicije funkcije mora napisati generički prefiks: .

int main () {
    array <int> myints(5);
    array<float> myfloats(5);
    myints.set (0, 100);
    myfloats.set(3, 3.1416);
    cout << "myints ima: " << myints.size() <<" elemenata"<< '\n';
    cout << myints[0] << '\n';
    cout << myfloats[3] << '\n';
    return 0;
}

Rezultat je:

ima: 5 elemenata

100

3.1416

Elementima niza se pristupa pomoću funkcija ili pomoću indeksne notacije.

Primer:

Klasa služi kao kontenjer dva elementa koji mogu biti različitih tipova. Formiraćemo niz takvih parova pomoću generičke klase . U taj niz ćemo upisati i iz njega ispisati niz parova kojima prvi element predstavlja redni broj , a drugi element je kvadratni koren prvoga .

template<class T1, class T2> class pair{
    T1 value1;
    T2 value2;
    public:
        pair (T1 first=0, T2 second=0){
            value1=first;
            value2=second;
        }
    T1 GetFirst () {return value1;}
    void SetFirst (T1 val) {
        value1 = val;
    }
    T2 GetSecond () {
        return value2;
    }
    void SetSecond (T2 val) {
        value2 = val;
    }
};
int main (){
    
// niz od 5 parova int,float
    array <pair<int,float> > arr(5);
    for(int i=0; i<arr.size(); i++){
        arr[i].SetFirst(i);//prvi sadrži redni broj
        arr[i].SetSecond(sqrt(i));//kvadratni koren prvog
    }
    for(int i=0; i<arr.size(); i++)
        cout<<arr[i].GetFirst() <<':'
    <<arr[i].GetSecond()<< endl;
    cout << endl;
    return 0;
}

Rezultat je:

0:0
1:1
2:1.41421
3:1.73205
4:2

Važno je upozoriti na oblik deklaracije niza parova:

array <pair<int,float> > arr(5);

1. Vidimo da se konkretna realizacija generičkog tipa može izvršiti i pomoću drugih generičkih tipova.
2. U deklaraciji se pojavljuju dva znaka > >. Između njih obvezno treba napisati razmak, jer ako bi napisali

   array <pair<int,float>> arr(5); // greška : >>
   

   kompajler bi prijavio grešku zbog toga jer se znak >> tretira kao operator.

Da bi se izbegle ovakove greške, preporučuje se korišćenje  deklaracije oblika:

typedef pair <int,float> if_pair;
array <if_pair>  arr(5);

Specijalizacija šablona

Standardna biblioteka šablona^[4] je softverksa biblioteka programskog jezika C++ koja je delimično uključena u S++ standardnu biblioteku. Obezbeđuje četiri kopmonente: kontejnere, iteratore, algoritme i  funktore. obezbeđuje gotov skup osnovnih klasa za C++ kao što su kontejneri i asocijativni nizovi,  koji se može koristiti uz bilo koji ugrađeni tip i uz bilo koji korisnički definisan tip koji podržava neke osnovne operacije (kao što su kopiranje i dodela). algoritmi su nezavisni od kontejnera, što značajno smanjuje kompleksnost biblioteke. ostvaruje rezultate kroz upotrebu šablona. Ovaj pristup obezbeđuje polimorfizam vremena kompajliranja koji je često efikasniji od tradicionalnog polimorfizma vremena pokretanja. Moderni C++ prevodioci podešeni su tako da minimalizuju bilo kakvu kaznz apstrakcije nastalu intezivnom upotrebom je nastao kao prva biblioteka generičkih algoritama i struktura podataka za C++, sa četiri ideje na umu: generičko programiranje, apstrakcija bez gubitka efikasnosti, fon Nojmanova arhitektura i vrednosna semantika.

Ponekad se s jednim šablonom ne mogu obuhvatiti svi slučajevi realizacije s različitim tipovima. U tom slučaju, za tipove kojima realizacija odstupa od šablona, može definisati poseban slučaj realizacije koji nazivamo specijalizacija šablona.

Za klasu koju definišemo šablon:

template<class gen_tip> identifikator{
    …
}

Specijalizacija za konkretan tip se zapisuje u obliku:

template<>class identifikator<konkretan_tip>{
    …
}

Specijalizacija se smatra delom šablona, stoga njena deklaracija započinje sa . U njoj se moraju definisati svi članovi šablona, ali isključivo sa konkretnim tipovima za koje se vrši specijalizacija šablona. Podrazumeva se da moraju biti definisani konstruktor i destruktor, ukoliko su definisani u opštem šablonu.

Šabloni sa konstantnim parametrima

Parametri šablona mogu biti i integralne konstante . Na primer,

template <class T, int N>  class array {
    ...
}

je šablon za definiranje klase pomoću generičkog tipa T i integralne konstante . Vrednost integralne konstante se mora specificirati pri deklaraciji objekta. Na primer,

array <float,5> myfloats;

deklariše se kao niz realnih brojeva kojem se dodatna svojstva zadaju s konstantom =5. U sledećem primeru koristićemo ovaj konstantni parametar za postavljanje veličine niza.

template <class T, int N>
class array{
    T m_buff[N]; // niz od N elemenata
    int m_size;
    public:
        array() : m_size(N) {}
    int size() {
        return m_size;
    }
    T & operator [] (int i) {
        return m_buff[i];
    }
    const T & operator [] (int i) const{ 
        return m_buff[i];
    }
};

int main () {
    array <int,5> myints;
    array<float,5> myfloats;
    myints[0]= 100;
    myfloats[3]= 3.1416; 13
    cout << "myints ima: "<<myints.size()
    <<" elemenata"<< '\n';
    cout << myints[0] << '\n';
    cout << myfloats[3] << '\n';
    return 0;
}

Dobije se ispis:

100
3.1416

Predodređeni i funkcijski parametri šablona

U šablonima se mogu koristiti predodređeni parametri. Na primer, šablonom

template <class T=int, int N=10> class array {
    …
}

se omogućuju deklaracije oblika:

array<> a_int_10; // niz od 10 int
array<float> a_float_10; // niz od 10 float
array<char, 100> a_char_100; // niz od 100 char

Napomena: predodređeni parametri se ne smeju koristiti u funkcijskim šablonima Parametri šablona mogu biti funkcije:

template <int Tfunc(int)>
class X {
    ...
    y = Tfunc(x); !!!
    ...
}

Moramo paziti da uzimamo što manje pretpostavki na tipove koji su parametri šablona. Preporučuje se: parametri generičkih funkcija su reference (da bismo izbegli zahtev da se objekti moraju kopirati, da postoji i da je dobro definisan konstruktor), za upoređivanje koristimo samo operator < (ne i operator >, operator >=, itd)

template <class T>
T min(const T &a, const T &b){
    return a < b ? a : b;
}

Poređenje šablona i makro naredbi

Šablone možemo smatrati integralnim makro naredbama. Primena šablona ima nekoliko prednosti u odnosu na makro naredbe:

1. Lakše ih je shvatiti jer šabloni izgledaju kao regularne klase(ili funkcije)
2. U razvoju šablona lakše se prevodi testiranje s različitim tipovima
3. Kompajler osigurava znatno veću kontrolu grešaka nego je to slučaj s makro naredbama
4. Funkcijski šabloni imaju definisan doseg, jer se mogu definisati kao deo klase () ili
5. Funkcijski šabloni mogu biti rekurzivni
6. Funkcijski šabloni se mogu preopteretiti
7. Pri komplajliranju neke datoteke, kompajler mora raspolagati s potpunom implementacijom šablona. Stoga je uobičajeno da se specifikacija i implementacija funkcija zapisuje u istoj „.h“ datoteci. Makro karakter šablona se posebno očitava kod klasa koje imaju statičke članove. U tom slučaju se za svaku realizaciju šablona inicira posebno statička promenljiva (kod regularnih se klasa za sve objekte jedne klase generiše samo jedna statička promenljiva)

Definicija i upotreba klase

Generička klasa predstavlja podskup standardne klase . Namenjeno joj je manipulisanje s homogenim kolekcijama elemenata proizvoljnog tipa. Izvršičemo specifikaciju i implementa klase temeljem znanja koja smo stekli razmatrajući generičku klasu i klasu .

Objekti klase imaju sledeće karakteristike:

• – kapacitet vektor je broj ćelija koje se automatski alociraju za spremanje elemenata vektora
• – veličina vektora je broj elemenata koje stvarno sadrži vektor
• – ako je potreban veći kapacitet vektora, on se može dobiti pozivom funkcije
• [] – pojedinom elementu vektora se pristupa pomoću indeksnog operatora, ili se koriste dve funkcije:
  • dodaje element na indeksu iza poslednje upisanog elementa
  • briše poslednji element iz vektora

Pri pozivu funkcije vodi se računa o kapacitetu vektora i vrši se automatsko alociranje potrebne memorije (memorija se udvostručuje ako potrebna veličina vektora premašuje trenutni kapacitet). Namena ove dve funkcije je da se vektor može koristiti kao dinamička kolekcija elemenata (kontejner).