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: STL vektor, lista, stek itd. Na primer, ako se želi napraviti lista koristeći generičnost, moguća deklaracija bi bila List <T>, gde T predstavlja vrstu podataka. Kada se načini primerak može se napraviti List<Integer> ili List<Animal>. Prema listi se zatim postupa kao prema listi onog tipa podataka koji je naveden. Od objektno orijentisanih programskih jezika, programski jezici C++, D, BETA, Eiffel, Ada i neke verzije Jave (1.5 i novije) podržavaju generičke tipove podataka. VB.NET i C# su počeli da podržavaju generičke tipove od verzije .NET 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 – template

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 int i float. 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 compile – 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. C++ dopušta korišćenje preopterećenih (overloaded) funkcija. To su funkcije koje imaju jednaka imena (i pripadaju istom dosegu – namespaceu) 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 #define može postići korišćenjem definisanjem inline 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 inline 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 int, float ili double. 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 template, 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 class ili typename, 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 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

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 Tacka, Duz i String. Ako, primera radi, pokušamo da upotrebimo neki objekat klase Duz ili String kao objekat klase Tacka, 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 LinkedList<T> koji čuva double vrednosti:

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

Pošto je tip parametra Double kompajler automatski umeće konverziju vrednosti 10.8 iz double u Double. 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 LinkedList<> sadrži statičko polje count za brojanje kreiranih objekata. Svaka klasa dobijena iz generičke za konkretan argument tipa imaće svoju kopiju ovog polja. Na taj način,

count u klasi LinkedList<String> broji kreirane objekte ove klase

count u klasi LinkedList<Point> 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 public ili static ključna reč predstavlja parametarski tip (ili listu tipova) za generički metod. Ovde imamo samo jedan parametarski tip za metod ispisiSve, 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

Java system 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 java.util. Razmotrićemo sledeće generičke tipove:

• Iterator<T> interfejsni tip - deklariše metode za iteriranje kroz jedan po jedan element kolekcije

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

• LinkedList<T> 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(Set) 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

• • ArrayList, Vector

• • LinkedList

• Redovi

• • Stack(LIFO)

• • Queue(FIFO)

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 Iterator<>. Objekat tipa Iterator<> sadrži reference na sve objekte kolekcije u nekom redosledu i njima se može pristupiti pomoću metoda interfejsa Iterator<>:

• T next() -  vraća objekat tipa T i postavlja Iterator<T> 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 NoSuchElementException

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

Primer:

Klasa primerak;

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

Ovde se podrazumeva da je iterator tipa Iterator<Klasa> i da čuva reference na objekat dobijen iz kolekcije. Jedan objekat koji implementira interfejs Iterator<> 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 java.util definisan je interfejs ListIterator<>. 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. ListIterator<> interfejs nasleđuje Iterator<> interfejs.

Spisak metoda:

• T next() -  kao kod Iterator<>

• Boolean hasNext() - kao kod Iterator<>

• int nextIndex() - vraća indeks objekta koji će biti vraćen pozivom metoda next() kao tip int, ili vraća broj elemenata u listi ako je *ListIterator<> objekat na kraju liste

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

• Boolean hasPrevious() – vraća true ako prethodni poziv previous() vraća objekat.

• int previousIndex() - vraća indeks objekta koji će biti vraćen sledećim pozivom metoda previous() ili -1 ako je ListIterator<> objekat na početku liste

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

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

• void set(T obj) – menja poslednji objekat dobijen pozivom next() ili previous(). I ovaj metod može da izbaci izuzetke tipa UnsupportedOperationException, ClassCastException i IllegalArgumentException.

ArrayList

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

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

• ArrayList<String> a= new ArrayList<String>();

• ArrayList<String> a= new ArrayList<String>(100); - eksplicitno se zadaje kapacitet

Metode

• size() – vraća broj elemenata koji su smešteni u ArrayList

• add(T) -  dodaje se objekat iza tekućeg poslednjeg objekta u ArrayList

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

• set(int,T) – postavljamo objekat u ArrayList na poziciju zadatu prvim argumentum, briše se objekat koji je prethodno bio na toj poziciji.

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

• addAll(int,lista)

• get(int) – vraća element na zadatoj poziciji

Činjenica da se kapacitet ArrayList 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 trimToSIze(). 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 ListIterator referencu iz vektora pozivanjem metoda listIterator().

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:

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

Metod toArray() 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 asList() definisan u klasi java.util.Arrays konvertuje niz elemenata datog tipa T u List<T> kolekciju. Argument metoda je niz koji se konvertuje i vraća se referenca tipa List<T>. Ova referenca se može proslediti kao argument konstruktoru klase ArrayList:

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

Brisanje elemenata:

• remove(int) – 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 ArrayList.

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

• removeAll(names.subList(2,5)); - brišu se elementi sa indeksima od 2 do 4

• retailAll(names.subList(2,5)); - ostaju samo elementi sa indeksima od 2 do 4

• removeAllElements() – uklanja sve elemente iz ArrayList

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

Pretraživanje ArrayList:

• int indexOf(T) – vraća poziciju datog objekta u ArrayList

• int indexOf(T,int) – vraća prvu poziciju datog objekta u ArrayList, počevši od pozicije zadate kao drugi argument

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

Povezana lista (LinkedList)

Konstuktori

• bez argumenata

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

Metode

• add(),addAll() – kao kod klase Vector<>

• addFirst() – dodaje objekat na početak liste

• addLast() – dodaje objekat na kraj liste

• get(int) – kao kod klase Vector<>

• getFirst(),getLast()

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

• set()

• size() – vraća broj elemenata liste

Meotdom iterator() dobija se Iterator<> objekat nad listom. Metodom listIterator() objekat ListIterator<>, kao i kod klase Vector<>

Katalozi

Katalog (HashMap<K,V>) 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 Map<K,V>. Razmatraćemo generičku klasu HashMap<K,V>.  Implementacija kataloga pomoću generičke klase HashMap<> podrazumeva da su parovi ključ/objekat smešteni u niz. Indeks u nizu dobija se na osnovu ključa za šta se koristi metod hashCode().Ovaj metod nasleđuje se iz klase Object 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 hashCode() 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 equals() iz klase Object. Da bi se obezbedila potrebna funkcionalnost, nova verzija treba da vrati true kada dva različita objekta sadrže iste vrednosti. Takođe, moguće je predefinisati metod hashCode() 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 hashCode() 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 hashCode(). Proste brojeve treba birati tako da ne budu preveliki, kako rezultat ne bi bio van opsega za int. Kad god je podatak-članica klase objekat neke druge klase, a ne primitivnog tipa, neophodno je implementirati hashCode() metod za datu klasu.

Konstuktori za HashMap<>

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

• HashMap(int capacity) – kreira katalog datog kapaciteta, sa podrazumevanim load faktorom

• HashMap(int capacity, float loadFactor) – 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:

• V put(K key, V value) – smešta objekat value u katalog koristeći ključ key.

• V remove(Object key) – 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 null, vraća se null.

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

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

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

• keySet() – vraća Set objekat koji referiše na ključeve kataloga

• entrySet() – vraća Set<Map.Entry> objekat koji referiše na parove ključ/objekat – svaki par je objekat tipa Map.Entry. Entry je generički interfejsni tip definisan unutar interfejsa Map<>.

• values() – vraća Collection 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];
}

Get() i set() funkcije smo mogli definisati inline unutar definicije klase. One su definisane izvan klase kako bi se pokazalo da se tada uvek ispred definicije funkcije mora napisati generički prefiks: template <class T>.

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:

myints ima: 5 elemenata

100

3.1416

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

Primer:

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

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  typedef deklaracije oblika:

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

Specijalizacija šablona

Standardna biblioteka šablona 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. STL 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). STL algoritmi su nezavisni od kontejnera, što značajno smanjuje kompleksnost biblioteke. STL 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 STL-a. STL 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 template<>. 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 (int,char,long, unsigned). Na primer,

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

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

array <float,5> myfloats;

deklariše se myfloat kao niz realnih brojeva kojem se dodatna svojstva zadaju s konstantom N=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 const reference (da bismo izbegli zahtev da se objekti moraju kopirati, da postoji i da je dobro definisan copy 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 (friend) ili namespace
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 tvector<class T>

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

Objekti tvector klase imaju sledeće karakteristike:

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

Pri pozivu push_back() 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).