Uvod u C++ šablone

Uvod u C++ šablone

offline
  • Đuro Glumac
  • dipl. ing. informatike
  • Pridružio: 08 Feb 2004
  • Poruke: 3640
  • Gde živiš: ApAtIn

Uvod u C++ šablone

Nemanja Trifunović

Ovaj tekst je namenjen ljudima koji poznaju C++, ali nisu radili sa šablonima. Namera mi je da pomognem programerima da koriste biblioteke zasnovane na šablonima (pre svega STL), a ne da pišu takve biblioteke. Dakle, izostaviću mnoge "napredne" teme rada sa šablonima, kao što je meta-programiranje, liste tipova, itd i zadržaću se na osnovnim stvarima.

1. Šta su šabloni?

U programerskoj praksi je jedan od najznačajnijih pitanja, kako napisati kod koji se može koristiti za rešavanje što više praktičnih problema (tzv "code reuse"). Tako se došlo do zaključka da mnogi algoritmi izgledaju praktično isto kada rade sa različitim tipovima. Uzmimo sasvim jednostavan primer: funkciju max koja treba da vrati veću (u stvari "ne manju") od dve zadate vrednosti. Za celobrojne bojeve, ova funkcija bi izgledala ovako:


const int& max (const int& a, const int& b) {     return a > b ? a : b; }

A ako bismo hteli da napravimo istu funkciju za realne brojeve, dobili bismo nešto ovako:


const double& max (const double& a, const double& b) {     return a > b ? a : b; }  

Ili ako imamo klasu "titula" za koju je preklopljen operator <


const titula& max (const titula& a, const titula& b) {     return a > b ? a : b; }

U čemu se razlikuju ove tri funkcije? Jedino u tipu argumenata i povratne vrednosti. Kada bismo mogli da i tip prosledimo kao argument funkcije, onda bismo imali jednu funkciju koja radi sa svim tipovima koji "prepoznaju" operator >. Upravo tu dolaze šabloni kao rešenje za naš problem:


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

Ovde je T tip - int, double, titula ili ma koji drugi za koji postoji operator >. Šablon funkcija koju smo upravo definisali, strogo gledano, nije obična funkcija koja prihvata dodatni parametar za tip promenljivih, već upravo to što mu ime kaže: šablon na osnovu koga kompajler može da napravi potencijalno bezbroj funkcija koje se razlikuju samo po tipu. Osim šablon funkcija, postoje i šablon klase, koje se često koriste kao "kontejneri" za različite tipove. Tipičan primer takve šablon klase je STL klasa vector, koja se često koristi umesto C++ nizova.

Kako se u praksi koriste šabloni? Evo jednostavnog primera:


template <typename T> const T& max (const T& a, const T& b) {     return a > b ? a : b; } #include <vector> int main (void) {     std::vector<int> niz;     niz.push_back(1);     niz.push_back(2);     niz.push_back(3);     int m = max<int> (niz[1], niz[2]); }
Najpre smo definisali promenljivu niz kao vector<int>; onda smo joj dodali 3 cela broja, i na kraju smo promenljivoj m dodelili vrednost većeg od poslednja dva elementa u niz-u. vector-u smo naznačili da treba da sadrži promenljive tipa int, a kasnije smo i funkciji max naznačili da radi sa promenljivama tipa int (kod šablon funkcija, ovo često nije potrebno činiti, jer je kompajler dovoljno pametan da sam zaključi o kom se tipu radi - o tome nešto više kasnije). Kada bismo recimo umesto sa int-ovima, radili sa double-ovima, kod bi izgledao ovako:


std::vector<double> niz;     niz.push_back(1.);     niz.push_back(2.);     niz.push_back(3.);     double m = max<double> (niz[1], niz[2]);

Dakle, nismo morali da menjamo kod unutar funkcije max ili klase vector, već smo samo iskoristili šablone da dobijemo tipove koji rade sa double, umesto sa int.

2. Šablon funkcije

Kao što sam napomenuo, šablon funkcije je šablon kojim se definiše skup funkcija koji imaju isti kod, ali rade sa različitim tipovima. Tako od šablon funkcije max možemo kreirati funkcije max<int>, max<long>, max<std::string>, max<neka_druga_klasa&gt. Pri tome često (ali ne uvek!!!) nije obavezno eksplicitno navesti tip, već kompajler može sam da zaključi o kom se tipu radi.


int i = max<int> (1,2);     long l = max<long> (1, 2);     double m = max<double> (1., 2.);         int b = max (1,2) // kompajler je sam odredio tip argumenata (int)             int c = max (1., 2) // Greska!!! Da li je tip int ili double?     int d = max<double> (1., 2) // nema greske - eksplicitno zadat tip double - drugi argument konvertovan u double

Mnoge šablon funkcije su dostupne programerima u STL biblioteci u headeru <algorithm>. Tu se nalaze šablon funkcije za sortiranje, sumiranje, permutacije i mnoge druge.

3. Šablon klase

Isto kao što šablon funkcije definišu skup funkcija koje rade ne isti način sa različitim tipovima, tako i šablon klase definišu skup klasa koje na neki način zavise od različitih tipova. Klasičan primer šablona klasa je dat u sledećem primeru:


template <typename T, int SIZE> class array {     T data[SIZE]; public:     T& operator[](int index) {return data[index];} }; int main (void) {     array<int, 40> celob; // niz od 40 int-ova     celob[2] = 4;     array<char*, 10> reci; // niz od 10 pointera na char*     reci[3] = "pevaj"; }
Šablon klasa array nije nešto preterano korisna u praksi, jer ne radi ništa što ne pružaju i C++ nizovi, ali je dovoljno jednostavna da nam posluži za ilustraciju kako rade šablon klase. Kao što se vidi, ovoj šablon klasi se zadaju dva parametra: prvi je tip i njime specificiramo kakve ćemo promenljive držati unutar niza, a drugi je celobrojna vrednost kojom određujemo veličinu niza. Parametri šablon klasa mogu biti:

1. Tipovi (klase, unije, C++ tipovi).
2. Celobrojne konstante čija je vrednost određena u trenutku kompajliranja.
3. Šabloni (u praksi, mnogi kompajleri ne dozvoljavaju ovakve parametre).

Skrenuo bih pažnju na br 2. Mnogi početnici pokušavaju da za parametar šablona daju celobrojnu vrednost koja nije poznata u vreme kompajliranja (npr neku vrednost koju unese korisnik). Takvi pokušaji se završavaju porukom o grešci koju prijavljuje kompajler.

Takođe, dozvoljeni su i podrazumevani parametri, pa smo mogli da uradimo nešto kao:


template <typename T = int, int SIZE = 50> class array {     T data[SIZE]; public:     T& operator[](int index) {return data[index];} }; int main (void) {     array<double> realni; // niz od 50 double-ova     array<> celob; // niz od 50 int-ova }
4. Eksplicitna specijalizacija šablona

Vratimo se za trenutak šablon funkciji max. Za veliki broj tipova, iz nje dobijamo funkcije koje rade upravo ono što mi želimo. Međutim, pretpostavimo da imamo neki tip za koji je vrednost max definisana na neki drugi način. U tom slučaju, možemo da napravimo tzv "eksplicitnu specijalizaciju" šablona za taj tip.


template<> const MojTip& max<MojTip> (const MojTip& a, const MojTip& b) (      if (a.vece(b))          return a;      else          return b; )

Ako negde u programu imamo recimo:


int celo = max (1,2); // ovde je pozvan "generalni" sablon
const MojTip& neki = max(nekiA, nekiB); // ovde je pozvan specijalizovani sablon

Ako za neki tip postoji specijalizacija šablona kompajler će iskoristiti tu specijalizaciju, a ako ne onda će koristiti originalni šablon da generiše funkciju za izračunavanje maksimuma.

Postoji i mogućnost parcijalne specijalizacije šablona (partial template specialization - PTS), ali samo za klase šablone. U tom slučaju se specijalizuje šablon za samo neke parametre, a ne za sve.

5. STL

Definitivno najbolji način da se počne sa upotrebom šablona je kroz korišćenje dela standardne C++ biblioteke koji se zove STL (standard template library). Korišćenje STL-a u svakodnevnom programiranju omogućava veću produktivnost i manje grešaka pri čemu se najčešće ne plaća nikakva cena u performansama. Krenimo sa prostim primerom: korisnik unosi razne reči (jednu po jednu) dok ne otkuca kraj. Program tad sortira reči po abecednom redu i prikaže ih na ekranu:


#include <vector> #include <iostream> #include <algorithm> #include <string> using namespace std; int main (void) {     // niz stringova     vector <string> nizStringova;         // Unos reci u niz dok se ne otkuca "kraj"     string unos;     while (true)     {         cout << "Unesite neku rec ili kraj\n";         cin >> unos;         if (unos.compare("kraj") == 0)             break;         nizStringova.push_back(unos);     }             // Sortiranje     sort(nizStringova.begin(), nizStringova.end());     // Prikaz stringova na ekranu:     copy(nizStringova.begin(), nizStringova.end(), ostream_iterator<string>(cout, "\n")); }
Osim poslednjeg reda, ovaj program je toliko čitljiv, da mu komentari gotovo nisu ni potrebni, čak ni za nekog ko ne zna ništa o STL-u.

U gornjem primeru se vide osnovni elementi koji sačinjavaju STL:

a) algoritmi - u ovom primeru sort i copy. STL sadrži 60-ak šablon funkcija za raznorazne operacije: pretraga, sortiranje, generisanje, rotiranje, traženje maksimuma, itd. Ove šablon funkcije su deklarisane u standardnom zaglavlju . Fleksibilnost ovih algoritama je u tome što oni mogu da operišu sa raznim tipovima podataka. Sve što im treba je "nešto" (iterator) što pokazuje na početak i kraj sekvence nad kojom će raditi.

b) kontejneri - u ovom primeru vector. Kontejneri su strukture podataka koje sadrže druge podatke. Npr, ovde smo imali vector<string> koji sadrži niz stringova. STL kontejneri su jako udobni za rad - posebno u poređenju sa C nizovima. Realokacija memorije se vrši automatski. Kontejneri (posebno vector) su ono sa čime treba početi rad u STL-u.

c) iteratori - u ovom primeru ih nismo direktno videli, ali funkcije begin() i end() vraćaju iteratore. Ma koliko to izgledalo čudno na prvi pogled, algoritmi i kontejneri ne znaju ništa jedni o drugima. Ono što ih povezuje su iteratori - objekti koji pokazuju na pojedine članove kontejnera (slično kao što pointeri mogu da pokazuju na članove C niza). Da bi sort algoritam poređao neku sekvencu, nije mu potrebna informacija o tome koje je sekvenca u pitanju, već samo iteratori koji pokazuju na početak i kraj te sekvence. Ovo omogućava da u nekim slučajevima jako lako zamenimo jedan kontejner drugim, uz minimalne promene koda. Recimo, ako bismo u gornjem primeru hteli da umesto vector-a koristimo deque, dobili bismo:


#include <deque> #include <iostream> #include <algorithm> #include <string> using namespace std; int main (void) {     // niz stringova     deque <string> nizStringova;         // Unos reci u niz dok se ne otkuca "kraj"     string unos;     while (true)     {         cout << "Unesite neku rec ili kraj\n";         cin >> unos;         if (unos.compare("kraj") == 0)             break;         nizStringova.push_back(unos);     }             // Sortiranje     sort(nizStringova.begin(), nizStringova.end());     // Prikaz stringova na ekranu:     copy(nizStringova.begin(), nizStringova.end(), ostream_iterator<string>(cout, "\n")); }

Uporedite gornja dva primera. Razlikuju se samo dve linije (umesto vector-a, koristimo deque). Algoritmi sort i copy rade kao i pre - oni "nemaju pojma" da je došlo do neke izmene.

STL je biblioteka koju treba koristiti iz prostog razloga što je lakše programirati sa njom nego bez nje.

6. Zaključak

U mnogim knjigama o C++u, šabloni se obrađuju na kraju, kao jedan od najtežih elemenata ovog jezika. To je samo delimično opravdano. Jeste komplikovano razvijati šablone, ali je jako lako koristiti gotove šablone. Ako uporedimo C nizove i vector, teško je smisliti razlog zbog kog bi neko danas koristio ovo prvo: C nizovi su komplikovaniji i lakše se prave greške u radu sa njima, a da i ne pominjemo probleme sa realokacijom memorije kod rasta niza.

Šabloni omogućavaju generičko programiranje - koncept koji je noviji i u mnogo čemu moćniji od objektnog programiranja. Najlepše od svega je to što se ova dva koncepta međusobno ne isključuju, već se mogu kombinovati na razne načine, a sve to vodi kodu koji je lakše projektovati, kodirati i održavati.

Preuzeto sa: http://www.novetehnologije.com



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • Pridružio: 23 Jul 2010
  • Poruke: 39

Je'l moze neko da mi napise neki program u c-u za svodjenje na kanonski oblik?



offline
  • Software developer
  • Pridružio: 06 Sep 2005
  • Poruke: 3800
  • Gde živiš: Beograd

Kanonski oblik reci? Jel na to mislis?
I jel to bese, npr. za string "aababdc" kanonski oblik je: "aaabbcd" ?
Ako ne, objasni malo detaljnije sta treba....

offline
  • Pridružio: 23 Jul 2010
  • Poruke: 39

Ne, mislila sam na svodjenje jednacine na kanonski oblik.

offline
  • Pridružio: 30 Dec 2007
  • Poruke: 4759
  • Gde živiš: Niš

Napisano: 10 Jun 2011 23:54

ali to je komplikovano Confused (to svođenje na kanonički oblik)
Postoje oni matematički programi koji to rade Ziveli

bila je tema u jednom pod-forumu za te programe
http://www.mycity.rs/Matematika/
http://www.mycity.rs/Matematika/Matematicki-programi.html

Dopuna: 11 Jun 2011 0:00

Natasa 23 ::Ne, mislila sam na svodjenje jednacine na kanonski oblik.
koje tačno jednačine ? neke konkretne ili bilo koje ?

na primer ako bi bio krug u pitanju onda je to trivijalno
a za neku proizvoljnu jednačinu i ne mora da bude moguće

http://en.wikipedia.org/wiki/Canonical_form#Geometry
Citat:
* The equation of a line: Ax + By = C
o C = 0 or C = 1

* The equation of a circle: (x - h)^2 + (y - k)^2 = r^2\,

Ko je trenutno na forumu
 

Ukupno su 551 korisnika na forumu :: 45 registrovanih, 3 sakrivenih i 503 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 1567 - dana 15 Jul 2016 19:18

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: A.R.Chafee.Jr., Alojz Hauptman, Apok, awathorn, bankulen, blue2, bojank2, branko7, cicus91, d.arsenal321, darkangel, Davor Kondic, dimitrovskid, Djokislav, Dorcolac, dragon986, eighty-one, ekser222, goranvas, havoc995, Ilija Cvorovic, kljift, Kubovac, kvcali, ltcolonel, marko308, MB120mm, Mercury2, miodrag2, mladen.zovko, nuke92, RADOVAN.S, renoje2, sasa.zoric, Srki94, suton2, USSVoyager, vasa.93, vdeki, VJ, Vojne Strasti, wizzardone, xandar, zodiac94, Zvrk2