Programovací techniky
1
Obsah 1 Objektově orientované programování ..............................................................................................3 1.1 Objekty – třídy a instance tříd...................................................................................................................................3 Objekt..............................................................................................................................................................................3 Třída................................................................................................................................................................................3 1.2 Metody, atributy, konstruktory, destruktory..............................................................................................................3 1.3 Vlastnosti OOP – dědičnost, zapouzdření, polymorfismus.......................................................................................4 1.4 Statické a virtuální metody.......................................................................................................................................5 1.5 Vztahy mezi objekty, diagramy tříd..........................................................................................................................6
2 Datové struktury................................................................................................................................9 2.1 Abstraktní datový typ - ADT, abstraktní datová struktura - ADS, aplikace paradigmat OOP v datových strukturách.......................................................................................................................................................................9 2.2 Metody porovnávání datových struktur - výpočetní složitosti algoritmů a složitosti paměťových reprezentací.....9 2.3 Lineární ADT (pole, seznam, zásobník, fronta) - základní charakteristiky, kategorizace a aplikace.....................10 2.4 Hierarchické ADT (unární strom, binární strom, k-cestný strom) - základní charakteristiky, kategorizace a aplikace.........................................................................................................................................................................11 2.5 ADT prioritní fronta - základní charakteristiky, kategorizace a aplikace...............................................................12 2.6 ADT tabulka - základní charakteristiky, kategorizace a aplikace...........................................................................12 2.7 ADT graf - základní charakteristiky, kategorizace a aplikace.................................................................................13
3 Úvod do jazyka C a jazyk C++ I - III .............................................................................................15 3.1 Základní datové typy,výčtové typy, struktury a unie v jazyce C a C++.................................................................15 3.2 Příkazy jazyka C a C++ - kategorizace, základní charakteristiky..........................................................................16 3.3 Pole, ukazatele a dynamické proměnné v jazyce C a C++ - deklarace a použití polí a ukazatelů, alokace a dealokace v paměti C a C++.........................................................................................................................................17 3.4 Funkce v jazyce C a C++ - deklarace, parametry, použití......................................................................................18 3.5 Objektové typy – deklarace, složky a jejich přístupová práva, konstruktory a destruktory, použití......................19 3.6 Odvozené třídy – význam, druhy dědění, polymorfní a abstraktní třídy................................................................21 3.7 Přetěžování operátorů – význam, základní pravidla, kategorizace, použití............................................................23 3.8 Šablony – význam, deklarace, použití....................................................................................................................24 3.9 Výjímky – význam, deklarace a použití výjimek dle normy C++..........................................................................26 3.10 Vstupy a výstupy v jazyce C a C++ - kategorizace, základní charakteristiky......................................................28 3.11 Generické programování v C++ - principy, koncepty, modely, všeobecné koncepty, iterátory............................29 3.12 Generické programování v C++ - funktory, adaptabilní funktory, adaptéry funktorů, koncepty a modely kontejnerů......................................................................................................................................................................33
2
1
1.1
Objektově orientované programování
Objekty – třídy a instance tříd.
Objektově orientované programování – spojení dat a práce s nimi do jednoho balíku, znuvupoužitelnost.
Objekt • Má stav a chování, • Stav je uložen v proměnných – atributech, • Chování implementují funkce – metody, • Žádný atribut ani metoda nejsou vidět z vnějšku – tato vlastnost se nazývá zapouzdření – encapsulation.
Třída • Více objektů má často stejné vzorce chování (metody) a stejné atributy: – Alík, Punt’a i Rex jsou Psi. – mají stejné metody – umí štěkat, běhat, žrát, spát, … – mají stejné atributy – jméno, srst, oči, výšku, … • Zavedeme novou (vyšší) abstrakci – třídu objektů Pes: – Alík, Punt’a, Rex i další psi jsou objekty ze třídy Pes.
1.2
Metody, atributy, konstruktory, destruktory. METODY
Objekt obsahuje metody objektu, což jsou procedury nebo funkce (resp. obecněji posloupnost kódu programu), které vykonávají nějakou činnost nad vnitřní pamětí objektu (a pouze nad ní). Také metody objektu jsou zvnějšku neviditelné – nepřístupné. Z uvedeného vyplývá, že nemůžeme metodu objektu zavolat přímo. Vnitřní paměť a vnitřní metody téhož objektu jsou vůči sobě „velmi přátelské“ v tom smyslu, že jsou plně viditelné. Metoda objektu má v dosahu své viditelnosti vnitřní paměť a naopak. Jinými slovy, metoda objektu je to, co je schopno pracovat s vnitřní pamětí objektu a nic jiného. Můžeme si představit, že metoda objektu je jedinou možností jak zpracovat vnitřní paměť objektu. ATRIBUTY Objekt obsahuje vnitřní paměť, tj. má vlastnost si něco pamatovat. Tato vnitřní paměť se nazývá atributy objektu. Záleží na programovacím jazyku, jak je tato vnitřní paměť, tj. atributy, implementována konkrétně. V každém jazyku však takováto paměť v objektu existuje. Vnitřní paměť objektu je zvnějšku objektu nepřístupná (není v dosahu viditelnosti), takže se nelze v paměti objektu „hrabat“ zvenčí. Je jeho soukromou záležitostí, co si objekt pamatuje a jak. Zvnějšku tedy vnitřní paměť nevidíme. 3
KONSTRUKTORY V souvislosti se zrodem objektu se hovoří často o takzvaných konstruktorech (constructor) metod objektu. Jsou to takové metody, které vyvolají zrod objektu a následují bezprostředně po zrodu objektu. Zavoláním konstruktoru vlastně nejenom zrodíme objekt (například alokujeme jej), ale současně se vykoná nějaká metoda související s potřebnými věcmi ohledně zrodu objektu. Do metody spojené se zrodem se většinou umisťují další zrody jiných, podřízených objektů, které je potřeba zrodit spolu s objektem, aby mohl fungovat. Objekt může mít několik konstruktorů a můžeme vyvolat podle potřeby ten, který odpovídá dané situaci, výsledkem je však vždy alokace paměti pro objekt a vyvolání metody daného konstruktoru. DESTRUKTORY Podobný význam má destruktor – metoda vyvolávající „zničení“ objektu, jeho dealokaci a současně vyvolání metody zapsané v destruktoru. Opět se většinou v destruktoru vyvolá zničení (zavolají destruktory) podřízených objektů.
1.3
Vlastnosti OOP – dědičnost, zapouzdření, polymorfismus. Zapouzdření
Proměnné objektu jsou umístěny uprostřed (v jádru) objektu. Metody obklopují a skrývají jádro objektu před ostatními objekty v programu. Zabalení proměnných objektu v jádru chráněném svými metodami se nazývá zapouzdření. Zapouzdření je obvykle použito k ukrytí implementačních detailů před jinými objekty. Když chceme změnit převodový stupeň, nepotřebujeme znát jak převodový mechanismus pracuje, stačí pouze přesunout páčku. Podobně v programu, nepotřebujeme znát jak třída je implementována, potřebujeme pouze vědět, kterou metodu vyvolat. Implementační detaily je tedy možno měnit bez ovlivnění ostatních částí programu. Nyní je třeba zdůraznit, že tato vlastnost je skutečně vlastností zásadní. Dědičnost Objektově orientované systémy umožňují aby třídy byly definovány pomocí jiných tříd. Např. horská kola, závodní kola a tandemy jsou různé typy jízdních kol. V objektově orientované terminologii, horská kola, závodní kola a tandemy jsou všechno podtřídy (potomci) třídy jízdní kolo. Obdobně třída jízdní kolo je nadtřída (předek) tříd horské kolo, závodní kolo a tandem. Každá podtřída dědí stav (ve formě instancí proměnných) od nadtřídy. Horská kola, závodní kola a tandemy sdílejí nějaký stav (např. rychlost). Každá podtřída také dědí metody od nadtřídy. Horská kola, závodní kola a tandemy sdílejí nějaké chování (např. brzdění). Podtřída ale není omezena stavem a chováním poskytnutým ji její nadtřídou. Podtřída může k zděděným proměnným a metodám přidat své vlastní proměnné a metody. Tandemy mají dvě sedla a dvojici řidítek; některá horská kola mají speciální převod s malým převodovým poměrem. Podtřídy také mohou přepisovat zděděné metody a poskytují specializovanou implementaci těchto metod. Např. jestliže máme horské kolo se speciálním převodem, musíme změnit metodu Změna převodu, tak aby jezdec mohl použít tento nový převod. Nejsme omezeni jen na jednu vrstvu dědění. Strom dědičnosti nebo hierarchie tříd může mít libovolný počet úrovní. Metody a proměnné se dědí přes tyto úrovně. Obecně, čím hlouběji v hierarchii tříd se třída vyskytuje, tím více specializované je její chování. Podtřídy poskytují specializované chování na základě společných prvků poskytnutých nadtřídou. 4
Pomocí použití dědičnosti, programátoři mohou mnohokrát opětovně používat kód v nadtřídě. Programátoři mohou implementovat nadtřídy nazývané abstraktní třídy, které definují všeobecné chování. Abstraktní nadtřídy definují a mají částečnou implementaci chování, ale většina třídy je nedefinovaná a neimplementovaná. Tyto detaily jsou doplněny ve specializovaných podtřídách. Polymorfismus Polymorfismus je vlastnost OOP, která umožňuje pojmenovat metodu jedním jménem a tato metoda může být společná pro různé objekty ve stromové hierarchii, i když pro každý objekt v této hierarchii se bude chovat různě. Jinak řečeno: polymorfismus umožňuje, aby každý objekt ve stromové hierarchii objektů volal metodu se stejným jménem. Přitom může mít každý objekt tuto metodu jinak definovanou. Výsledkem je, že pro každý objekt ve stromové hierarchii bude mít volání metody jinou odezvu, avšak pro každý objekt vždy tu správnou.
1.4
Statické a virtuální metody
Všechny metody, které jsou v každé třídě, pokud nejsou virtual, jsou statické metody. Můžeme je přirovnat ke statickým proměnným. Překladač jim vyhradí místo v paměti již v době překladu a také řeší všechny vztahy mezi metodami a objekty již v době překladu. Těmto vztahům se říká early binding - brzká vazba. Díky těmto vlastnostem jsou statické metody velmi rychlé při jejich vykonávání a jejich kód je velice efektivní. program Kresleni; type Lokace = object X:integer; Y:integer; end;
Bod=object(Lokace) procedure zobraz; end; Kruh=object(Bod) procedure zobraz; end;
var B:Bod; K:Kruh; procedureVykresli(Co:Bod) begin CO.zobraz; end;
begin Vykresli(K); end; V hlavním programu požadujeme, aby procedura Vykresli vykreslila objekt, který je určen jako parametr této procedury. Program je po syntaktické stránce správný, poněvadž za formální parametr Co typu Bod můžeme dosadit skutečný parametr K typu Kruh. Problém nastává až v tomto místě. Protože metoda Zobraz je statická metoda, překladač určuje její adresu již v době překladu. Překladač tedy při překladu zjistí, že formální parametr Co je typu Bod a dosadí tedy při překladu volání metody Zobraz adresu metody Bod.Zobraz. I když bude skutečným parametrem Kruh, bude volána metoda objeku Bod. Tento problém řeší až virtuální metody. Virtuální metody nabízejí pro řešení těchto situací možnosti vytvářet vazby mezi objekty a jejich metodami až v době výpočtu. Těmto vazbám se říká late binding - pozdní vazba. Tyto metody jsou pomalejší při vykonávání než metody statické. 5
Virtuální metody řeší pojem zvaný polymorfismus. Díky těmto metodám můžeme pojmenovat jedním jménem metodu, která je stejná pro všechny objekty ve stromové hierarchii, avšak pro každý objekt má tato metoda jinou implementaci. A nyní již konkrétněji. Virtuální metoda se označuje v objektu direktivou virtual. Adresa této metody je uložena v tabulce virtuálních metod (dále jen VMT - z anglického Virtual method table). Potřebujeme-li vyvolat nějakou metodu, její adresa je nalezena právě v této tabulce. VMT musí být naplněna ještě předtím, než se s objektem začne vůbec pracovat. K naplnění tabulky VMT slouží speciální metoda, zvaná konstruktor. V definici objektu se používá místo vyhrazeného slova procedure slovo constructor. Konstruktor inicializuje mechanismus virtuálních metod. Konstruktor se musí vyskytovat v definici každého objektu, který využívá alespoň jednu virtuální metodu. Než je jakákoliv virtuální metoda daného objektu použita, je nutné spustit metodu konstruktoru. Pokud bychom to neudělali, došlo by k zablokování programu. Metoda, definovaná v objektu jako virtuální, musí být definovaná i ve všech potomcích tohoto objektu jako virtuální.
1.5
Vztahy mezi objekty, diagramy tříd
Pokud chceme vytvořit objektově orientovanou aplikaci, musí mezi sebou zúčastněné objekty nějak komunikovat. Tato komunikace představuje volání metod (někdy se také říká zasílání zpráv) mezi objekty, které jsou spolu svázány pomocí spojení (link). Spojení jsou v programovacích jazycích implementována nejčastěji jako ukazatele nebo objektové reference. Spojení mezi dvěma objekty mohou být obousměrná, kdy oba objekty mají na sebe navzájem k dispozici odkaz, nebo pouze jednosměrná, kdy odkaz má pouze jeden z této dvojice objektů, který pak druhý objekt řídí. Jednosměrné spojení se zobrazuje šipkou, která vede od objektu obsahujícího odkaz směrem k řízenému objektu, obousměrná spojení se zobrazují jednoduchou spojovací čárou bez šipek.
V každém spojení mohou propojené objekty zastávat určité role. Například ve spojení dvou osob může jedna z nich zastávat roli zaměstnance, druhá roli zaměstnavatele. Názvy rolí můžeme uvést nad příslušným koncem spojení. Grafické znázornění objektů a jejich vztahů v určitém čase se nazývá objektový diagram a je jedním z prostředků, jak můžeme vyjádřit výsledky analýzy a návrhu části systému. Představuje vlastně ukázku konkrétní situace, která může za běhu systému nastat. Asociace Spojení mezi objekty však nelze vytvářet zcela libovolně, musí být v souladu s tím, jak jsou definovány vztahy mezi jejich třídami. Na úrovni tříd spojením odpovídají asociace, spojení jsou vlastně instancemi asociací. Každá asociace může být podrobněji popsána dalšími vlastnosti jako název asociace, názvy rolí asociovaných tříd, násobnost a řiditelnost asociace. Název asociace vyjadřuje obvykle slovesnou frází akci, kterou vykonává jeden objekt pomocí druhého objektu. Na6
příklad vztah „Firma zaměstnává Osobu“ vyjádříme jako asociaci mezi třídou Firma a Osoba pojmenovanou "zaměstnává". V této asociaci má Firma roli zaměstnavatele a Osoba roli zaměstnance. Uvádíme buď pouze název asociace (případně se šipkou označující směr asociace), nebo pouze názvy rolí, ne obojí současně. Dále můžeme uvést omezení, že Firma zaměstnává 0 a více Osob (znak hvězdička), zatímco Osoba je zaměstnána v právě jedné Firmě (číslo 1). Řiditelnost můžeme vyjádřit podobně jako u spojení šipkou na straně řízeného objektu.
Násobnost asociace můžeme uvést také jako interval, např. 0..1, 1..* nebo 1..10. Uvádění násobnosti asociací je užitečné pro pochopení omezujících podmínek v námi navrženém modelu a jejich konfrontaci s modelovanou realitou. Vždy bychom se měli u každé asociace zamyslet alespoň nad tím, zda je nebo není násobná, případně zda může na některé straně asociace být i nulový počet prvků. Grafické znázornění tříd a jejich asociací se nazývá třídní diagram. Tento diagram představuje statickou strukturu modelovaného systému, zachycuje jeho prvky a vztahy mezi nimi. Společně s diagramy zachycujícími dynamiku systému a jeho chování v čase patří k základním podkladům pro implementaci objektově orientovaných systémů. Agregace a kompozice Agregace představuje volnou vazbu mezi celkem a součástí, kdy jeden objekt (celek) využívá služby dalších objektů (součástí). Například vztah mezi počítačem a tiskárnou je vztah typu agregace, kdy počítač s tiskárnou tvoří jeden celek, ale tiskárna může existovat i tehdy, pokud není k žádnému počítači připojena. Agregace je formou asociace a v grafické podobě se odlišuje prázdným kosočtvercem na straně celku.
Ke každému počítači může být připojen libovolný počet tiskáren a že tiskárna může být připojena k nejvýše jednomu počítači. Podstatné je, že odpojíme-li tiskárnu od počítače a počítač dáme do šrotu, je tiskárna stále použitelná s jiným počítačem. Silnější formou agregace je kompozice. Jde opět o vztah mezi celkem a součástí, ale tento vztah je velmi těsný a neumožňuje samostatnou existenci součásti, aniž by byla připojena k nějakému celku. Navíc na rozdíl od agregace tato součást musí patřit jen jedinému celku a není možné ji sdílet více celky.
7
Příkladem kompozice je vztah mezi fakturou a jejími položkami. Každá položka musí být součástí právě jedné faktury, faktura má jednu a více položek. Jestliže fakturu zahodíme, nezbudou nám po ni ani žádné položky.
8
2 Datové struktury
2.1 Abstraktní datový typ - ADT, abstraktní datová struktura - ADS, aplikace paradigmat OOP v datových strukturách Datová struktura - potřeba zpracování údajů vede k modelování reality, vymezení objektu zkoumání; abstrakce reality; DS představují způsob uchování a organizace dat s cílem umožňovat zpřístupňování a modifikaci. ADT je matematická struktura složená ze dvou částí - třídy a operace nad prvky. ADT zapouzdřuje před uživatelem svoji vnitřní strukturu, zajímají nás operace a jejich výsledky, neimplementujeme operace. ADS je konkrétní realizace ADT, konkrétně implementujeme algoritmy operací, uživatel zná jen vstup a očekává výstup. Doména - sestava blíže nespecifikovaných prvků. Kategorizace operací ADS/ADT: • konstruktory - konstrukce a inicializace struktury • destruktory - zrušení celé struktury • selektory - zpřístupňovací operace bez reorganizace struktury • prohlídky celé struktury Klasifikační kritéria DS: Logická úroveň - přímý/sekvenční přístup k prvkům, ne/lineární množina - prvky ne/porovnatelné Fyzická implementační úroveň - elementární, strukturované datové typy Složení struktury - homogenní, nehomogenní prvky Zapouzdření - neznáme vnitřní uspořádání DS, jen metody, zajímá nás, co nám DS nabízí, ne, jak to dělá Dědičnost - možnost vytvoření hierarchie od ADS po uživatelskou DS s konkrétním typem dat. Objekt ADS nevytváříme, jen využíváme jeho dědičných vlastností (vlož, odeber, prohlídka) Polymorfismus - akce uskutečňované nad různými uživatelskými daty jsou pojmenovány stejně, ale realizují se jinak. Datové struktury
2.2 Metody porovnávání datových struktur - výpočetní složitosti algoritmů a složitosti paměťových reprezentací Pro vyhodnocení různých algoritmů je nutné vymezit objektivní kritéria, jež umožní provádět jejich vzájemné porovnání
9
Časově paměťové kritérium - čas potřebný k provedení algoritmu, paměťový prostor potřebný k realizaci, výpočetní složitost - počet operací, které je nutné vykonat. Důležitost efektivního algoritmu narůstá s přibývajícím množstvím dat. Velké množství dat - je nutné spolupracovat s externí pamětí - neefektivní swapping (skoková změna složitosti) Složitost - polynomiální, exponenciální O(n2), logaritmická O(log n) - třídění půlením pole, lineární, linearitmická O(n log2n) - quicksort, konstantní O(1) Paměťová složitost je vyjádřena množstvím paměti počítače, jež je nutná pro kód a data. Paměťová velikost kódu je obvykle zanedbatelná proti velikosti dat. Nejčastěji bývá složitost konstantní, lineární nebo logaritmická. O programu, který nevyžaduje více paměťového prostoru než zabírají zpracovávaná data, říkáme, že pracuje in-situ (na svém vlastním prostoru).
2.3 Lineární ADT (pole, seznam, zásobník, fronta) - základní charakteristiky, kategorizace a aplikace Lineárně uspořádaná množina - existuje-li v množině M relace R-lineární, pak je množina M lineárně uspořádaná. Nejobecnější interpretace lineárně uspořádané množiny může být specifikována jako Super ADT Sekvence. Sekvence vymezuje “maximální možnosti”: • zpřístupnění logických vstupních bran • zpřístupnění nejbližších sousedů • zpřístupnění prvku s definovaným pořadím od začátku začátek, konec, následník, předchůdce, bezúrovňová struktura, porovnatelné prvky Pole • všechny prvky pole existují od okamžiku jeho vytvoření až do okamžiku jeho zrušení • prvky pole jsou zpřístupňovány na základě svého pořadí od definovaného začátku pole • klasická operace odeber absentuje Pro implementaci homogenního pole je vhodné využít organizaci s implicitními vztahy -zpřístupnění i-tého prvku založeného na výpočtu jeho paměťové adresy při znalosti počáteční adresy pole a paměťové velikosti prvku. Lineární seznamy Jednosměrně a obousměrně zřetězené. Zpřístupňování prvků je založeno na sekvenčním přístupu. Implementace - dynamický lineární seznam (nejčastěji), seznam na poli, seznam s hlavou, bez hlavy, ne/cyklicky zřetězené. U všech typů implementací jsou složitosti základních operací 0(1), kromě operace prohlídka O(n). Příklad: zastávky v rámci MHD, souprava železničních vagónů Zásobník (LIFO) Standardní typ charakterizovaný zejména možností zpřístupňování pouze jednoho prvku, nacházejícího se na začátku struktury. Vrchol struktury je jediným možným místem struktury pro realizace vkládání a odebírání prvků. Absentuje tradiční operace prohlídka. 10
Implementace - dynamický zásobník (lineární seznam), zásobník na poli. Složitost všech operací je O(1). Příklad: zásobník pistole. Fronta (FIFO) Standardní typ disponující jednu vstupní, resp. výstupní bránou, které umožňují vkládání prvků do, resp. odebírání ze struktury. Implementace - dynamická fronta (obousměrný lineární seznam), fronta na poli Složitost základní operací je O(1). Příklad: fronta klientů
2.4 Hierarchické ADT (unární strom, binární strom, k-cestný strom) základní charakteristiky, kategorizace a aplikace Existuje v množině M relace R - hierarchické uspořádání, pak o množině M říkáme, že je hierarchicky uspořádaná. kořen, listy, potomek/syn, předek/otec, úrovňová struktura, neporovnatelné prvky Unární strom - každý prvek unárního stromu má přístup pouze k jednomu prvku (otci) Implementace: kořen a1, listy: b2, d4, j10,... Příklad: vodstvo, kanalizační systém Datové struktury Binarní strom - každý prvek binárního stromu má maximálně dva syny, strom je uspořádaný rozlišení pravého a levého syna. Impplementace - dynamický binární strom - organizace s explicitními vztahy, orientovaný směrem od kořene k listům, zpřístupni bratra a otce nejsou základní operace; binární strom na poli - organizace s implicitními vztahy, implementujícím typem je homogenní souvislé pole Složitosti - složitosti základních operací O(1), kromě operace prohlídka Prohlídka: PreOrder akce-levá-pravá, InOrder levá-akce-pravá, PostOrder levápravá-akce Příklad: symbolické vyjádření matematických výrazů Uspořádaný k-cestný strom disponuje-li kořenový strom vlastností, že každý z jeho prvků může mít maximálně k synů 11
Uspořádaný strom je strom, pro nějž platí, že synové každého jeho prvku představují lineárně uspořádanou množinu. Prohlídky: do hloubky - LIFO, do šířky - FIFO
2.5 ADT prioritní fronta - základní charakteristiky, kategorizace a aplikace Množina s lineárním uspořádáním, přičemž uspořádání je určováno prioritami prvků vzhledem k jejich pořadí odebíráním ze struktury. Speciální případy prioritní fronty: Zásobník - LIFO, nejvyšší prioritu má časově nejmladší prvek; Fronta - FIFO, nejvyšší prioritu má časově nejstarší prvek. prioritní fronta nad lineárním seznamem (ne/utříděný) Datové struktury Implementace dvojseznamová struktura - utříděná (časté vyhledávání), neutříděná (časté vkládání) dvojúrovňová prioritní fronta - bázová struktura - utříděný seznam, přístupová struktura -utříděné vyhledávací pole Nevýhodou dvojseznamové a dvojúrovňové prioritní fronty je složitost samoorganizujícího mechanismu při nutných reorganizací. Prioritní fronta na haldě - halda je označení pro binární strom, pro jehož každý vrchol platí, že jeho priorita je větší než priority obou jeho synů (pokud existují). Halda vytváří vždy vyvážený strom - úrovně listů se liší nejvýše o jednotku. Příklad: fronta kamionů na celní odbavení (kazící se náklad)
2.6
ADT tabulka - základní charakteristiky, kategorizace a aplikace
Množina s lineárním uspořádáním, přičemž uspořádání je určováno jednoznačnými klíčovými hodnotami prvků. (Abecední seznam studentů) Implementace: tabulka na poli, tabulka na seznamu, tabulka na binární vyhledávacím stromu, tabulka na implicitní kosočtvercové vyhledávací síti, rozptýlené (hashovací) tabulky
12
algoritmy třídění tabulek: přímým vkládáním (insert sort), výběrem (selection sort), přímou výměnou, výměnou s rozdělováním (quick sort), spojováním (merge sort), číslicové ) (radix sort) Binární vyhledávací strom BVS je označení pro binární strom, pro jehož každý vrchol x, charakterizovaný klíčem K(x) platí: je-li vrchol y z levého podstromu vrcholu x, pak K(y)<=K(x) a je-li vrchol y z pravého podstromu vrcholu x, pak K(y)>=K(x) Operace Najdi, Vlož, Odeber, Prohlídka - InOrder představuje výstup v utříděném pořadí Pro každý vrchol dokonale vyváženého binárního stromu platí, že počet vrcholů v jeho levém a pravém podstromu se liší nejvíce o jedna. Složitost: vlož, odeber, najdi - log2n Implicitní kosočtvercová vyhledávací síť utříděný ve vzestupném pořadí ve směru logických šipek (zdola šikmo vpravo nahoru, shora šikmo vpravo dolů). Pro každý prvek platí, že jeho následník vpravo dole má větší hodnotu klíče a předchůdce vlevo dole má větší hodnotu klíče a předchůdce vlevo dole menší hodnotu klíče -> prvky na jedné úrovni jsou též utříděny vzestupně doprava Operace najdi, vlož, odeber mají složitost O(√n) Datové struktury Rozptýlené tabulky (hashovací tabulky) Princip hashovacích tabulek spočívá v určení adresy (indexu) hledaného prvku přímo z jeho klíče (z jeho transformace) bez nutnosti uplatnění asociativního algoritmu založeného na porovnávání hledaného klíče s klíči uložených prvků. Transformace klíče je nutná k tomu, aby byl omezen prostor možných hodnot klíče, jenž je daleko větší než prostor použitelných adres pro uložení záznamů Příklad: identifikace železničních vozů Implementace pole-seznam operace vlož - výpočet primární adresy prvku, je-li volná, je vkládaný prvek uložen, pokud je obsazena, je vkládaný prvek uložen do nové, dynamicky vyblokované paměťové místo a je připojen k seznamu prvků této kolizní skupiny operace najdi/odeber - výpočet primární adresy prvku Při vhodné volbě rozptylové funkce činí složitosti základních operací Najdui, Vlož, Zruš O(1) Příklad: kartotéky u lékaře, elektronické slovníky, telefonní seznam
2.7
ADT graf - základní charakteristiky, kategorizace a aplikace
Abstraktní datový typ Graf (odrážející binární relaci v množině) představuje heterogenní bipartitní strukturu pracující se dvěma odlišnými třídami prvků - vrcholy a hranami. Vrcholově orientovaný přístup Vstupní branou do datové struktury je vrchol(y), s nímž jsou spojeny další informace/data o jeho následnících, resp. předchůdcích a tím i o incidentních hranách. Při 13
vyhledávání ve struktuře jsou přímo k dispozici informace o sousedních vrcholech (následnících a předchůdcích) a tím i informace o incidentních hranách. Hvězdy mohou být realizovány jako čtyři abstraktní typy: pole-pole, pole-tabulka, tabulka-pole, tabulka-tabulka Hranově ohodnocený přístup Vyhledávací operace orientovány na vyhledávání hran - zpřístupnění vrcholů je až druhotné. Hranově orientovaný přístup je vhodný pro aplikace pracující s úseky dopravních sítí, po nichž se přemisťují dopravní prostředky.Označení opačných konců hran pomocí polaritních znamének umožňuje adresovat opačné konce úseků. K identifikaci hran se používá - dvojice incidentních vrcholů (tabulka hran), pevné očíslování hran prvními m přirozenými čísly (pole hran)
14
3
3.1
Úvod do jazyka C a jazyk C++ I - III
Základní datové typy,výčtové typy, struktury a unie v jazyce C a C++
Logický typ bool – false a true. V paměti zabírá jeden byte. Platí false < true. Jestliže je očekávána logická hodnota, tak libovolné nenulové číslo konvertuje na true, nula na false, použije-li se místo celého čísla logická hodnota, automaticky se převede na celé číslo - false na 0, true na 1 Znakové typy 1bytové znakové typy: char, unsigned char a signed char 2bytový wchar_t - pro práci s asijskými znaky nebo s kódem UNICODE. znakové konstanty, např ‘a’ jsou typu char (v jazyce C jsou typu int). Celá čísla celočíselné typy (stdint.h): long long int, unsigned long unsigned long int (int lze vynechat), long, unsigned long • typy s přesně určenou šířkou • int8_t, int16_t • uint8_t,uint16_t • typy s určitou minimální šířkou – typy se šířkou alespoň N bitů • int_least8_t, int_least16_t • uint_least8_t, uint_least16_t • typy s určitou minimální šířkou, pro něž jsou v dané architektuře výpočty nejrychlejší • int_fast8_t, int_fast16_t • uint_least8_t, uint_fast16_t • typům které mohou obsahovat ukazatele n objekty, neboli do nichž lze uložit hodnotu typu void* a pak ji přenést zpět aniž se změní • intptr_t • uintptr_t • typy s maximální šířkou • intmax_t • uintmax_t Celočíselné konstantní výrazy je to výraz, který dokáže překladač vyhodnotit již v době překladu (makro, konstanta, sizeof) Ukazatele void* nelze v C++ přiřadit ukazateli s doménovým typem void * v; int a,*b; v=&a; // C++ a C b=v; // C lze ale v C++ nikoliv
15
Výčtové typy deklarace_výčtového_typu: enum jmenovkanep { seznam_enumerátorů } seznam_deklarátorůnep; Jazyk C a C++ Např. enum barvy { cerna = 22, bila = -33, modra = 2*cerna, zelena }; C: enum barvy b=cerna; C++ stačí: barvy b=cerna; Aby se v jazyce C mohlo klíčové slovo enum vynechat, musí se deklarovat výčtový typ pomocí klíčového slova typedef. Struktury a unie v C++ patří mezi objektové typy. Struktury struct jmenovkanep { deklarace_složek } seznam_deklarátorůnep; Např.: struct TOsoba { char Jmeno[30]; int Cislo; }; • jazyce C se na strukturu musí odvolávat „úplným zápisem“, tj. konstrukcí struct TOsoba Osoba; • C++ stačí jmenovka, tj. TOsoba Osoba; Aby se v jazyce C mohlo klíčové slovo struct vynechat, musí se deklarovat nový typ pomocí klíčového slova typedef: typedef struct TOsoba TTOsoba; Unie VC++ lze deklarovat anonymní unie, v jazyku C nejsou k dispozici. Ke složce anonymní unie se přistupuje pomocí samotného identifikátoru složky. Globální anonymní unie musí být statické.
3.2
Příkazy jazyka C a C++ - kategorizace, základní charakteristiky
Příkazy Příkazem je též deklarace, tj. deklarace se může vyskytnout všude tam, kde syntaxe jazyka povoluje příkaz. Blok (složený příkaz) v C++ je definován následovně: blok: posloupnost_příkazů Blok v jazyce C je definován takto: blok_v_C: { posloupnost_deklarací posloupnost_příkazů } Deklarace proměnné je dále povolena ve výrazu podmínka těchto příkazů: if, switch, while, for Ve všech těchto příkazech je deklarovaná proměnná lokální proměnou v rámci tohoto příkazu (bloku). Skoky Nelze přeskočit deklaraci s inicializací, pokud se nepřeskočí celý blok, ve kterém se takový příkaz nachází. Toto omezení se týká příkazů goto a switch. Následující zápis je nesprávný: if (x) goto Pokracovani; int y = 10; //... Pokracovani: // ... Následující zápisy jsou správné: if (x) goto Pokracovani; int y; y = 10;//... Pokracovani: // ... if (x) goto Pokracovani; 16
{ int y = 10;//... } Pokracovani: Jazyk C a C++ // ... Nesprávná konstrukce příkazu switch: switch (c) { case 0: int x = 10;// ... break; case 1:// ... } Správné konstrukce příkazu switch: switch (c) { case 0: int x; x = 10; // ... break; case 1: // ... } switch (c) { case 0: { int x = 10; // ... break; } case 1: // ... }
3.3 Pole, ukazatele a dynamické proměnné v jazyce C a C++ deklarace a použití polí a ukazatelů, alokace a dealokace v paměti C a C++ Pole Pole má přesně takovou velikost, aby obsáhlo všechny své prvky. Prvky pole mají indexy od 0 do "počet prvků pole - 1". Velikost pole musí být během překladu konstantní. Překladač musí znát při překladu kolik místa alokovat pro pole. Nemůžeme tedy použít proměnnou k určení velikosti pole. Např. int mojePole[5]; Deklarace pole inicializací: h[15] = {10, 20, 50, 100, 200, 500, 1000, 2000}; Řetězce v programech C++ jsou reprezentovány poli datového typu char. Např. znakovému poli lze přiřadit řetězec takto: char text[] = "Toto je řetězec."; Tím alokujeme 17 slabik v paměti a uložíme řetězec na toto místo. Pokud spočítáme znaky našeho řetězce, zjistíme, že jich je pouze 16. Poslední 17 slabika je alokována pro uložení ukončujícího znaku řetězce (tento znak je na konec řetězce vložen automaticky). Ukončující znak je speciální znak, který je reprezentován konstantou '\0', což je ekvivalentní s číslem 0. Ukazatel dvě základní kategorie: ukazatele na data (objekty) a ukazatele na funkce. Oba dva typy ukazatelů jsou speciální objekty, které obsahují adresy v paměti. Mají různé vlastnosti, účely použití a pravidla zacházení. Obecně řečeno, ukazatelé na funkce se používají pro přístup k funkcím a pro předávání funkcí jako parametrů jiným funkcím. S těmito ukazateli není možné provádět žádné aritmetické operace. Ukazatele na objekty můžeme inkrementovat a dekrementovat tak, jak je to při prohlížení polí nebo složitějších struktur potřeba. Např. po deklaraci void (*fce)(int); je fce ukazatel na funkci s parametrem typu int, která nic nevrací. Dynamické proměnné C pro alokaci a uvolnění paměti funkce: malloc ,calloc ,realloc a free Ty lze použít i v C++, ale zpravidla se místo nich používají operátory new a delete. Výsledkem operátoru new je ukazatel na označení_typu. Bez inicializace: int* a = new int; Výraz *a má nedefinovanou hodnotu. S inicializací: int* b = new int(10); Výraz *b má hodnotu 10. Alokace jednorozměrných polí int *c=new int [10] Alokuje pole 10 prvků typu int. Vrací ukazatel na první prvek pole. Inicializace pomocí new nelze provést. Musí se 17
provést cyklem for. Alokace vícerozměrných polí matice (10x10) Matice=new int* [10]; for( i=0;i<10;i++) Matice[i]=new int [10]; Pokud se alokace nepodaří, operátor new vrací 0, novější překladače vyvolají výjimku bad_alloc. Jazyk C a C++
3.4
Funkce v jazyce C a C++ - deklarace, parametry, použití
Funkce je část kódu, která provádí jednoduché, dobře definované akce. Parametr je hodnota předávaná funkci, která ji použije ve svých operacích. Prototyp je deklarace funkce, která je uvedena před definicí funkce. Volání funkce je vyvolání příkazů tvořících funkci. Rekurze je proces, ve kterém funkce volá sama sebe. Lokální proměnná je proměnná deklarovaná uvnitř funkce (existuje pouze do návratu z funkce). Globální proměnná je proměnná deklarovaná mimo funkci (existuje do ukončení programu). Funkci která nemá parametry lze zapsat v C++ dvěma způsoby. int f(void); int f(); Vjazyce C je přípustná pouze první varianta. Druhá varianta znamená funkci, u níž není znám počet a typ parametrů. Informativní deklarace=prototyp funkce. VC++ musí být před voláním funkce deklarován alespoň její prototyp. V jazyce C může volání funkce předcházet její deklaraci. Parametry funkce mohou být předávány - hodnotou – v C a C++ - odkazem – pouze v C++ Implicitní hodnoty parametrů VC++ se mohou definovat implicitní hodnoty parametrů funkcí. void f(int a, int b=0, int c=getch()) Předepíše-li se implicitní hodnota pro některý z parametrů, musí se předepsat implicitní hodnoty i pro všechny parametry které za ním následují. Pokud se některý z parametrů vynechá, musí se vynechat i následující. f(3,5); - pro c se použije implicitní hodnota Referenční funkce Funkce která vrací referenci. Vložené funkce Je-li tělo funkce malé – jednořádkové, volání takové funkce není příliš efektivní, neboť počítač spotřebuje více času na předávání parametrů, skok do funkce a návrat z ní, než na vykonání samotného těla funkce. V C++ lze použít vloženou funkci, která se deklaruje pomocí specifikátoru inline. Překladač tak místo hlavičky funkci vloží samotné tělo. Přetěžování funkcí VC++ lze v jednom programu definovat několik funkcí se stejným identifikátorem, pokud se liší počtem nebo typem parametrů. void f(); int f(int); double f(double); void f(int,double); 18
Při volání vybere překladač funkci, jejíž formální parametry nejlépe odpovídají skutečným parametrům v zápisu funkce. Pokud typy skutečných parametrů neodpovídají přesně typům formálních parametrů žádné z funkcí, vybere překladač tu, pro kterou je konverze nejsnazší. Výsledek rozhodování však musí být jednoznačný, jinak překladač oznámí chybu. Jazyk C a C++
3.5 Objektové typy – deklarace, složky a jejich přístupová práva, konstruktory a destruktory, použití Objektové typy v C++: třída, struktura, unie Třídy a struktury jsou v C++ téměř totéž, liší se jen implicitními přístupovými právy. Tělo třídy obsahuje seznam deklarací složek třídy, kterými mohou být: • atributy = datové složky • metody = funkční složky • typy – tzv. vnořené typy • šablony První způsob deklarace představuje informativní deklaraci, která se může vyskytnou i vícekrát. Další způsoby představují definiční deklaraci. Deklarace objektového typu může být: • globální • lokální v deklaraci jiné třídy – vnořená třída • lokální ve funkci Pokud se v deklaraci vynechá jmenovka, jedná se o nepojmenovanou třídu. V deklaraci nepojmenované třídy se nesmí vynechat seznam deklarátorů. Atributy Deklarace atributů je analogická deklaraci obyčejných proměnných. Inicializace bez konstruktoru Instance objektového typu lze inicializovat stejným způsobem jako složky struktury nebo unie v jazyku C, pokud tento objektový typ: nemá konstruktor, všechny atributy jsou veřejné a nekonstantní, ani jeden z jeho nestatických atributů není referencí, nemá předka, nemá virtuální funkci Metody Deklarace metody je buď prototyp a nebo definiční deklarace. Pokud se uvede pouze prototyp, musí se metoda později definovat za deklarací třídy. Definuje-li se metoda mimo tělo třídy, musí se její jméno kvalifikovat jmenovkou třídy s použitím rozlišovacího operátoru. Přístupová práva k omezení přístupu ke složkám třídy slouží specifikátory private, protected a public a deklarace přátel. public – veřejně přístupné složky – jsou přístupné pro kteroukoliv část programu bez omezení private – soukromé složky – jsou přístupné pouze pro metody této třídy a její přátelé protected – chráněné složky – jsou přístupné pouze pro metody této třídy a jejich potomky a pro jejich přátele Složky, jejichž deklaraci nepředchází specifikace přístupu jsou implicitně • soukromé ve třídách • veřejné ve strukturách Lokální proměnné a atributy Identifikátor lokální proměnné definované v metodě včetně parametru této metody může být shodný 19
s identifikátorem atributy třídy. V takovém případě lokální proměnná metody zastiňuje atribut třídy. Pokud je potřebné v takovéto metodě přistoupit k atributu třídy, musí se atribut třídy kvalifikovat jmenovky třídy a rozlišovacího operátoru nebo pomocí ukazatele this. Jazyk C a C++ Statické atributy a metody Mohou se volat v době, kdy neexistuje žádná instance patřičné třídy. Mimo metody dané třídy se musí kvalifikovat a to jednou možností • jmenovkou třídy a rozlišovacím operátorem • identifikátorem instance třídy a operátorem kvalifikace nebo operátorem nepřímé kvalifikace Přátelé Přítelem dané třídy může být funkce nebo třída, která není členem dané třídy, které je povoleno přistupovat ke všem složkám dané třídy. friend prototyp_funkce; • Přátelství není tranzitivní – pokud je třída B přítelem třídy A a třída C je přítelem B, není pravda že třída C je přítelem třídy A. • Přátelství není ani dědičné. • Přátelství se nevztahuje ani na vnořené třídy. Konstruktory a Destruktory Konstruktory se volají při vytváření instance v rámci její definiční deklarace nebo alokace pomocí operátoru new, při konverzích, při předávání parametrů objektových typů hodnot apod. Specifické vlastnosti konstruktorů a destruktorů: • jméno konstruktoru je tvořeno identifikátorem třídy • deklarace konstruktoru nesmí obsahovat specifikaci typu vrácené hodnoty a to ani void • nedědí se – odvozená třída ovšem použije ke své konstrukci konstruktory předků • nesmí být virtuální, statické konstantní a nestále • nelze získat jejich adresu • mohou být volány pro instance deklarované s cv-modifikátory inicializační část konstruktoru Slouží pro inicializaci nestatických atributů instancí a k předání parametrů konstruktorům předků. Zapisuje se mezi hlavičkou a tělo konstruktoru. Statické atributy se v inicializační části nesmí uvádět. TA() : x(0), y(0) {} Definiční deklarace instance Definice instance třídy znamená vždy volání konstruktoru. parametry konstruktoru se zapisují za identifikátor instance do kulatých závorek podobně jako skutečné parametry. Pokud se má volat implicitní konstruktor, definuje se instance bez prázdných závorek. Implicitní konstruktor konstruktor, který může být volán bez parametrů. Může mít parametry, ale musejí mít předepsány implicitní hodnoty. Pokud třída nemá uživatelem deklarovaný konstruktor, překladač vytvoří implicitně deklarovaný implicitní konstruktor. Jestliže třída obsahuje alespoň jeden, žádný se nevytváří a pokud je potřeba, generuje se chyba.
20
Kopírovací konstruktor Jazyk C a C++ Kopírovací konstruktor je konstruktor, který lze volat s jedním parametrem typu reference na danou třídu. Při nenadefinování vlastního kopírovacího konstruktoru a zároveň je atribut pole, přiřazení B=T nastane fakt, že pole z instance B bude ukazovat na stejné pole jako A. Konverzní konstruktory konstruktor třídy TA bez modifikátoru explicit, který lze volat s jedním parametrem, může překladač použít k implicitním nebo explicitním konverzím typu prvního parametru na typ třídy TA. Explicitní konstruktory Explicitní konstruktor je deklarován s modifikátorem explicit. Explicitní konstruktor na rozdíl od konverzního konstruktoru nelze použít k implicitním konverzím, ale pouze k explicitním. Destruktory Destruktory jsou metody, které se volají automaticky při zániku: • lokální instance –ve chvíli kdy program opouští období platnosti • globální instance a lokální statické instance – při ukončení programu • dynamické instance - při volání delete Destruktory jsou metody třídy s těmito specifiky: • jméno destruktoru je tvořeno identifikátorem, před kterým je ~ • nemá žádný parametr • deklarace konstruktoru nesmí obsahovat specifikaci typu vrácené hodnoty a to ani void • nedědí se – odvozená třída ovšem použije ke své destrukci destruktory svých předků • nesmí být statické, konstantní nebo nestálé • nelze získat jejich adresu Pokud není deklarovaný, překladač vytvoří implicitně deklarovaný destruktor. Po provedení těla destruktoru dané třídy se volají destruktory atributů objektových typů dané třídy a destruktory předků. Skončí-li program voláním funkce exit(), nezavolají se destruktory lokálních nestatických instancí. Globální a lokální statické instance budou zrušeny obvyklým způsobem. Skončí-li program voláním funkce abort(), nezavolají se žádné destruktory. V případě dynamických instancí se musí volat operátor delete.
3.6 Odvozené třídy – význam, druhy dědění, polymorfní a abstraktní třídy Dědičnost slouží k rozšiřování vlastností tříd. Jazyk C++ podporuje vícenásobnou dědičnost, takže jedna třída může mít několik předků. Má-li daná třída předky, v deklaraci odvozené třídy se za její jmenovkou uvede dvojtečka a seznam jmenovka předků oddělených čárkou. Před každou jmenovkou předka může být uveden jeden ze specifikátorů public,protecte nebo private a případně klíčové slovo virtual. V seznamu předků nesmí být uvedena jmenovka právě deklarované třídy nebo vícekrát stejná jmenovka předka. Přístupová práva: • public – zděděné složky budou mít stejná přístupová práva jako má předek • protected –veřejně přístupné a chráněné složky budou chráněné a soukromé zůstanou 21
soukromé • private – všechny zděděné složky budou v odvozené třídě soukromé Jazyk C a C++ Pokud se neuvede specifikace přístupu, jsou defaultně: • private – u class • public- u struct Přístupová práva na složku jdou v potomkovi změnit, pokud u předka nejsou soukromé. Nevirtuální a virtuální dědění jedna třída nemůže být vícekrát přímým předkem jiné třídy. Může se ale stát, že od jedné třídy např. TA budou odvozeny dvě třídy TB a TC a ty budou přímými předky třídy TD. Podobjekt třídy TA bude obsažen ve třídě TD jednou nebo dvakrát v závislosti na typu dědění. Statické složky třídy jsou v paměti uloženy pouze jednou bez ohledu na typ dědění, počtu instancí dané třídy a jejich potomků. Obdobně identifikátory vnořených typů a výčtových konstant dané třídy existují v jejích potomcích pouze jednou bez ohledu na typ dědění. Potomek může zastoupit předka. Překladač může automaticky konvertovat instanci potomka na předka, jestliže: • toto přetypování je jednoznačné • předek je v místě operace přístupný Pořadí konstrukce a destrukce Při vytváření instance odvozené třídy se nejprve zkonstruují zděděné podobjekty. Přitom se nejprve volají konstruktory virtuálních předků a potom nevirtuálních. V obou případech se postupuje podle pořadí zapsání v deklaraci odvozené třídy. destruktory jsou volané v opačném pořadí. Při TD D bude výpis u nevirtuálního dědění TATBTATCTD TDTCTATBTA Polymorfismus - POLYMORFNÍ TŘÍDY S instancemi se pracuje často pomocí ukazatelů, přitom zpravidla vznikají situace, kdy není známý přesný typ instance, na kterou daný ukazatel ukazuje a je potřebné vyvolat metodu skutečné instance. Třídy obsahující virtuální metody, se nazývají polymorfní. Jestliže je v určité třídě TA deklarována metoda jako virtuální, bude virtuální i ve všech potomcích třídy TA. Při nové definici metody v potomkovi se metoda nemusí (ale může) deklarovat se specifikátorem virtual. Virtuální metoda, která je v odvozené třídě nově definována, se nazývá předefinovaná virtuální metoda. Virtuální metodou mohou být i destruktory, když nemají v předkovi a v potomkovi stejné jméno. Virtuální metody nemohou být konstruktory, statické metody ani spřátelené funkce. Virtuální metody musí být v předkovi a potomkovi deklarovány se stejným jménem, počtem a typem parametrů. Typ vrácené hodnoty virtuální metody by měl být identický v předkovi i v potomkovi. Abstraktní třída Je třída, která může být použita jen jako předek jiné třídy. Nelze deklarovat instanci abstraktní třídy, ale lze deklarovat ukazatel nebo referenci na abstraktní třídu. Třída je abstraktní, jestliže má alespoň jednu čistou virtuální metodu. Čistá virtuální metoda nemá definici a její prototyp má tvar virtual 22
prototyp =0; kde prototyp je vlastní prototyp nevirtuální metody. Jazyk C a C++
3.7 Přetěžování operátorů – význam, základní pravidla, kategorizace, použití jazyk C++ umožňuje rozšířit definice většiny operátorů na objektové a výčtové typy. Operátory se dělí do čtyř skupin • operátor podmíněného výrazu ?:, rozlišovací operátor ::, operátor přímé kvalifikace .. • operátor indexování [], volání funkce(), přiřazení =, nepřímé kvalifikace -> a přetypování (typ) lze přetěžovat pouze jako nestatické metody objektových typů. • operátory new a delete lze přetěžovat jako obyčejné funkce nebo jako statické metody objektových typů • všechny ostatní operátory můžeme přetěžovat jako nestatické metody objektových typů nebo jako obyčejné funkce, které mají alespoň jeden parametr objektového nebo výčtového typu. Přetížený operátor může změnit svůj význam, který má pro vestavěné typy, např. operátor + lze definovat jako násobení apod., ale zpravidla je snahou neměnit smysl přetíženého operátoru, aby se dal odhadnout jeho výsledek. Přetížený operátor se deklaruje jako operátorová funkce. Pro parametry operátorové funkce nelze předepisovat implicitní hodnoty. Unární operátor se definuje jako obyčejná funkce s jedním parametrem nebo jako metoda bez parametru. Binární operátor se definuje jako obyčejná funkce se dvěma parametry nebo jako metoda s jedním parametrem. lze volat TKomplexCislo z=a+b; TKomplexCislo z=a.operator + (b); Operátor ++ -Lze přetížit prefixovou i postfixovou verzi. Prefixový operátor se deklaruje jako obyčejná funkce s jedním parametrem nebo jako metoda bez parametrů. Postfixový operátor se deklaruje jako obyčejná funkce se dvěma parametry, z nichž druhý je typu int, nebo jako metoda s jedním parametrem typu int. Parametr int slouží pouze k rozlišení prefixové a postfixové verze a nelze jej v operátorové funkci použít. unární operátor bitový posun - ~ binární operátor +, Přetížení binárních operátorů + a – automaticky neznamená přetížení složených přiřazovacích operátorů += -=. Tyto operátory se musí přetížit samostatně. operátory přetěžované jen jako metody operátor přiřazení = Operátor se nedědí. implicitní operátor přiřazení TA& TA::operator = (const TA&) Aby bylo možné přetížený operátor přiřazení zřetězit, musí vracet referenci na jeho levý operand podobně jako implicitně deklarovaný operátor přiřazení. Jazyk C a C++ 23
Kopírovací operátor přiřazení má smysl definovat, pokud se jedná o třídu, pro níž nemohl překladač vytvořit implicitní kopírovací operátor přiřazení nebo pokud obsahuje dynamicky alokovaný atribut. operátor indexování [] Operátor indexování je binární operátor. Levým operandem je instance objektového typu, pravým operandem je index zapsaný mezi závorky. Přetížený operátor indexování je nestatická Metoda má tvar: operator [] (parametr) Aby mohl být operátor indexování použit na levé straně, musí operátorová funkce vracet referenci na typ prvku int &operator [] (int i) Pokud má fce vracet pouze int, lze operátor použít jen na pravé straně. Operátor volání funkce() Přetížený operátor volání funkce je nestatická metoda mající tvar operator () (seznam parametrů) Operátor volání funkce vrací referenci, aby mohl být použit na levé straně přiřazovacího příkazu. operátor nepřímé kvalifikace -> Považuje se za unární. Operátor musí vracet buď ukazatel na nějakou třídu nebo instanci jiné třídy, v níž je operátor také přetížen. operátory new a delete
3.8
Šablony – význam, deklarace, použití
Šablony umožňují popsat najednou celou množinu funkcí, které se liší jen například typem jejich parametru, nebo množinou objektových typů, které se liší nejen například typem jejich atributu. Mají podobný význam jako makra, ale poskytují více možností. Na rozdíl od maker jsou šablony zpracovávány překladačem. Šablona představuje vzor, podle kterého překladač vytvoří funkci nebo objektový typ. Takto vytvořená funkce nebo objektový typ se nazývá instance šablony. Deklarace šablony se v programu může objevit na úrovni souboru, uvnitř objektového typu nebo uvnitř šablony objektového typu. Šablona se nemůže deklarovat jako lokální v bloku. template <seznam parametru> deklarace Seznam parametrů představuje jednotlivé formální parametry oddělené čárkami, podobně jako v deklaraci funkce. Formální parametry šablony mohou být hodnotové typy, formální typy nebo šablony objektových typů. Deklarace je • deklarace nebo definice obyčejné funkce • deklarace nebo definice třídy • definice metody třídy • definice vnořené třídy • definice statického atributu šablony třídy nebo definice statického atributu třídy vnořené uvnitř šablony třídy • definice vnořené šablony Jazyk C a C++
24
Parametry šablony • class • typename • template Typové parametry Předepisují se pomocí klíčového slova typename nebo class. template
class TA; Pro parametr V je předepsána implicitní hodnota typu int. Když je uvedeno class, může se dosadit i neobjektový typ. hodnotové parametry hodnotové typy se deklarují podobně jako formální parametry funkcí, musí však být jednoho z následujících typů • celočíselný typ template class TA {…}; TA <double, 10*5> A; • výčtový typ • ukazatel na objekt • reference na objekt • ukazatel na funkci • třídní ukazatel Šablonové parametry parametrem šablony může být i jiná šablona třídy. Skutečným parametrem v tomto případě musí být jméno existující šablony třídy. template class W> class TA; Třídy šablona objektového typu může obsahovat stejné druhy složek, jako objektový typ. Metody Metody, které nejsou definovány přímo v těle šablony, se musí definovat jako šablony. Jméno metody se musí kvalifikovat jmenovkou třídy, za níž následují v lomených závorkách jména formálních parametrů v témže pořadí. template void TA ::f1(){…} Funkce Šablona funkce umožňuje popsat najednou celou množinu funkcí, které se liší jen například typem jejich parametrů. template T Max(T a, T b){return a>b?a:b;} Max (1,2); Přetěžování V jednom oboru viditelnosti lze deklarovat několik šablon funkcí se stejným jménem. Lze také deklarovat šablonu funkce a obyčejnou funkci se stejným jménem. Pravidla pro rozlišování mezi Jazyk C a C++ šablonami jsou podobná jako pravidla pro rozlišování přetížených funkcí. Má-li překladač volbu mezi funkcí a šablonou, dá přednost funkci, pokud parametry přesně odpovídají. 25
Explicitní specializace šablony umožňuje deklarovat specifickou verzi šablony pro její určité skutečné parametry. Explicitní specializace může být deklarována pro: • šablonu obyčejné funkce • metodu šablony třídy • statický atribut třídy • třídu vnořenou do šablony třídy • šablonu třídy vnořenou do jiné šablony třídy • šablonu metody vnořenou do šablony třídy Parciální specializace šablon třídy poskytuje alternativní definici k primární definici šablony pro určité druhy parametrů. Primární šablona musí mít alespoň informativní deklaraci před deklaraci parciálních specializací šablony. Parciální specializované deklarace se od primární deklarace liší tím, že za jménem šablony následují v lomených závorkách formální parametry, které určují způsob specializace. Každá parciální specializace šablony představuje odlišnou šablonu, a proto musí být kompletně definována. Může obsahovat jiné složky než primární šablona.
3.9
Výjímky – význam, deklarace a použití výjimek dle normy C++
Výjimka představuje situaci, která nastane v průběhu normálního chodu programu a způsobí, že program nemůže obvyklým způsobem dále pokračovat. Jinými slovy, výjimka je chyba v běhu programu. Pokud vznikne výjimka, je třeba ji programově ošetřit. V normě jazyce C++ lze pracovat pouze s tzv. synchronními (softwarovými) výjimkami, které vzniknou uvnitř programu a nejsou závislé na operačním systému. Pomocí výjimek v C++ tedy nelze zpracovávat výjimky jako např. dělení nulou, aritmetického přetečení, přístup na neplatnou adresu apod.. Tyto výjimky se nazývají asynchronní (hardwarové) a lze je ošetřovat pomocí mechanismu strukturovaných výjimek nebo výjimek nadstavbové knihovny. Všechny operace, které by mohly vyvolat výjimky, se musí provádět v tzv. pokusném bloku (angl. try block). Pokusný blok se skládá ze složeného příkazu (angl. compound statement) a z jednoho či několika handlerů (angl. exception handler).1 Pokud při provádění operací ve složeném příkazu pokusného bloku nevznikne výjimka, proběhnou řádně všechny příkazy tohoto bloku a po jeho ukončení bude program pokračovat za hlídaným blokem – handlery se přeskočí. Jestliže v průběhu některé z operací ve složeném příkazu pokusného bloku nastane výjimka, provádění příkazů tohoto bloku se předčasně skončí v místě, kde výjimka vznikla a řízení se přesune do některého z handlerů. Pokud handler neukončí běh programu, může program po provedení tohoto handleru pokračovat za pokusným blokem, v němž se handler nachází. Výjimka může vzniknout přímo ve složeném příkazu pokusného bloku nebo v některém z vnořených bloků či v některé z funkcí volaných ve složeném příkazu pokusného bloku. Pokusný Jazyk C a C++ blok může být vnořen do jiného pokusného bloku a výjimku, která vznikne ve vnořeném pokusném bloku, může ošetřit handler v nadřízeném pokusném bloku. Když vznikne výjimka, začne systém hledat vhodný handler, který by ji ošetřil. Přitom postupuje podle posloupnosti vnořených pokusných bloků a volání funkcí od místa vzniku výjimky k funkci main. Dochází k tzv. šíření výjimky do nadřízeného bloku resp. do volající funkce. 26
Při vyvolání výjimky se vytváří datový objekt, který ponese informaci o povaze výjimky a okolnostech jejího vzniku. Často jde o instanci určitého objektového typu. Typ hodnoty, která je posílána handleru při vyvolání výjimky, se nazývá typ výjimky. Vyvolání výjimky se provádí pomocí výrazu throw. Hodnota výrazu přiřazovací_výraz ponese informaci o výjimce. Typ výjimky je určen typem hodnoty tohoto výrazu. hodnotu tohoto výrazu lze použít v handlenu a podle ní se rozhodnout, jak se výjimka ošetří. Z pokusného bloku lze vyskočit příkazem return, break, continue nebo goto. Handler Handler začíná klíčovým slovem catch, za kterým je v závorkách specifikován typ výjimky. Specifikace typu výjimky se podobá specifikaci jednoho formálního parametru funkce. Při hledání odpovídajícího handleru se prochází handlery v pořadí jejích uvedení za složeným příkazem pokusného bloku. Parametr handleru lze předávat i jako konstantu nebo referenci. Předávání odkazem (referencí) se používá zejména u parametru objektového typu, protože umožňuje používat virtuální metody a nedochází ke zbytečnému kopírování objektu. Specifikaci typu výjimky v deklaraci handleru lze nahradit výpustkou. Takový handler se nazývá univerzální. Zachytí totiž všechny výjimky jakéhokoliv typu. Musí být proto uveden jako poslední v pokusném bloku. Specifikace výjimek void f(); může se vyvolat jakákoliv výjimka a rozšířit se z ní void g() throw(); může vzniknout jakákoliv, ale žádná se nemůže rozšířit void h() throw(TVyjimka, int); - může vzniknout jakákoliv, ale rozšířit se může pouze TVyjimka a int typedef void (*tuf)() throw (int); // chyba - nelze použít typedef int (TA::*ug)() const throw (); deklarace třídního ukazatele, ze kterého se nesmí rozšířit žádná vyjímka Všechny deklarace včetně definice určité funkce nebo metody musí mít specifikovaný stejný seznam výjimek. Konstruktory a destruktory Pokud vznikne výjimka v konstruktoru instance třídy, nebude se pro ni volat destruktor. Budou se ale volat destruktory jejich nestatických složek a předků, které již byly zcela zkonstruovány a nebyla započata jejich destrukce voláním jejich destruktorů. Neošetřené a neočekávané výjimky Neošetřená výjimka vznikne pokud: • výjimku nezachytí žádný handler • se rozšíří výjimka z destruktoru během úklidu zásobníku • se rozšíří výjimka z konstruktoru nebo destruktoru globální instance třídy V takových případech program zavolá funkci terminate (), která zavolá funkci abort(). Pokud se z nějaké funkce rozšíří výjimka, která není uvedena ve specifikaci Výjimek této funkce, jedná se o neočekávanou výjimku. V případě vzniku se volá void unexpected() Jazyk C a C++
27
3.10 Vstupy a výstupy v jazyce C a C++ - kategorizace, základní charakteristiky Jazyk C++ obsahuje všechny nástroje pro vstupní a výstupní operace, které jsou dostupné v jazyku C, a navíc jeho součástí jsou prostředky založené na objektových datových typech. Pro vstup a výstup se v jazyku C++, ale i v jazyku C používají tzv. datové proudy. Datový proud se stará o přenos dat od zdroje ke spotřebiči. Zdrojem může být program a spotřebičem soubor, obrazovka apod. Součástí proudu bývá zpravidla vyrovnávací paměť. Při přenosu může docházet k transformaci dat, např. k převodu z binární do znakové podoby apod. Standardní datové proudy V jazyce C a C++ existují tři standardní datové proudy: • stdin – slouží pro vstup ze standardního vstupního souboru. Tím je zpravidla konzola počítače, tedy klávesnice. Může být ale přesměrován prostředky operačního systému (z příkazového řádku při spuštění programu) • stdout – je určen pro výstup do standardního výstupu souboru. Tím je zpravidla konzole, tedy obrazovka monitoru. Může být ale přesměrován prostředky operačního systému. • stdder – je určen pro výstup do standardního souboru chyb. Tím je zpravidla opět konzole. Tento proud však nelze pod operačním systémem DOS/Windows přesměrovat. Všechny tyto proudy se automaticky otevírají při spuštění programu a zavírají při jeho ukončení. Objektové datové proudy Objektová koncepce datových proudů přináší řadu výhod, mezi něž patří možnost definovat vlastní vstupní operátor >> a výstupní operátor << pro své vlastní datové typy, definovat vlastní manipulátor apod. Datové proudy jazyka C++ jsou založeny na dvou hierarchiích objektových typů – ios_base. ios_base Třída je definovaná v hlavičkové souboru . Ve třídě ios_base jsou definovány vlastnosti, které jsou společné všem objektovým datovým proudům. Obsahuje definici těchto vnořených typů: • třída failure – odvozená ze třídy exception • tři typy bitových masek – fmtflags, iostate, openmode • výčtový typ seekdir • třida Init iostate obsahuje stavové příznaky goodbit stav bez chyby - hodnota 0 badbit indikuje, že nějaká operace, jiná než vstupní a výstupní, byla neúspěšná eofbit operace dosáhla konce vstupní sekvence failbit vstupní nebo výstupní operace byla neúspěšná seekdir Příznaky pro přesun ukazatele v proudu: beg přesun ukazatele a pozici relativní vzhledem k začátku cut přesun ukazatele a pozici relativní vzhledem k aktuální pozici end přesun ukazatele a pozici relativní vzhledem ke konci Jazyk C a C++ Init 28
Slouží ke konstrukci a destrukci tříd cout, cin, clog, cerr. Manipulátory manipulátory jsou funkce, které lze volat s použitím operátoru >> nebo <<. Např. příkaz cout<<setw(10)<> a <<. Pro vestavěné typy jsou definovány jako metody šablon tříd basic_istream a basic_ostream. Pro uživatelské typy se musí definovat jako obyčejné funkce nebo jako metody třídy odvozené od šablony basic_istream resp. basic_ostream. Má-li operátor vstupu >> pro typ X fungovat podobně jako vestavěné operátory >>, musí se definovat buď jako šablona obyčejné operátorové funkce nebo jako obyčejná operátorová funkce
3.11 Generické programování v C++ - principy, koncepty, modely, všeobecné koncepty, iterátory Mezi programovací styly patří: strukturované programování – programování pomocí funkcí, které operují nad daty – neobjektový přístup, objektově orientované programování, generické programování – je založeno na vytváření abstraktních vzorů funkcí a tříd pomocí generických konstrukcí (šablon). Koncepty a modely Jazyk C++ umožňuje definováním šablony funkce popsat velkou množinu funkcí lišících se typem parametrů. Neumožňuje však rozhodování, zda daný typ je vhodný pro příslušnou šablonu. Koncept je tedy množina požadavků na typové parametry generických konstrukcí. Jazyk C a C++ Model konceptu je typ, který vyhovuje danému konceptu. Zjemnění konceptu – koncept X je zjemněním konceptu Y, pokud množina požadavků konceptu Y je podmnožinou požadavků 29
konceptu X. Koncept X tedy vyhovuje konceptu Y a obsahuje navíc další požadavky. Určitý koncept může být zjemněním i několika jiných konceptů. Zjemnění konceptu je podobné dědičnosti tříd. minimalizovatelné typy (zkr. MT), minimalizovatelné kopírovatelné typy (zkr. MKT) V knihovně STLport jsou definovány koncepty kontejnerů, iterátorů a dalších objektů. Všeobecné koncepty Norma jazyka C++ popisuje všeobecné požadavky na typové parametry šablon. Knihovna STLport pro tyto požadavky zavádí koncepty. Koncept Assignable Typ je modelem konceptu Assignable, pokud je možné kopírovat objekty tohoto typu a přiřadit hodnotu do objektu tohoto typu. Model konceptu musí vyhovovat výrazům uvedeným v následující tabulce. Výraz X(x) x(y); = y; x= y
Návratový typ X X&
Po provedení výrazu X(x) je kopií x x je kopií y x je kopií y
Norma jazyka C++ definuje pro koncept Assignable pouze poslední z uvedených požadavků, tj. x = y. Koncept DefaultConstructible Typ je modelem konceptu DefaultConstructible, jestliže má implicitní konstruktor, který, jeli to možné, provede konstrukci objektu bez inicializace jeho složek. Model konceptu musí vyhovovat výrazům uvedeným v následující tabulce. ýraz Návratový () typ x; Koncept EqualityComparable Typ je modelem konceptu EqualityComparable, jestliže objekty tohoto typu lze porovnávat pomocí operátoru ==, který musí splňovat vlastnosti relace rovnosti. Model konceptu musí vyhovovat výrazům uvedeným v následující tabulce. Výraz x == y x != y
Návratový typ lze implicitně konvertovat na typ bool lze implicitně konvertovat na typ bool
Význam ekvivalent výrazu !(x == y).
Operátor != nemusí být v modelu konceptu definován, ale je-li definován, musí být uvedeným ekvivalentem operátoru ==. Relace == má vlastnosti uvedené v následující tabulce. Vlastnost relace == identita reflexivita symetrie tranzitivita
Platí jestliže &x == &y, potom x == y x == x jestliže x == y, potom y == x jestliže x == y a zároveň y == z, potom x == z
ITERÁTORY Iterátor je zevšeobecněním pojmu ukazatel: je to nějaký objekt, který ukazuje na jiný objekt. Slouží zejména k procházení nějakého rozsahu objektů. 30
Jazyk C a C++ Iterátory jsou centrální součástí generického programování, protože představují rozhraní mezi kontejnery (např. vector) a generickými algoritmy. Tyto algoritmy mají zpravidla jako své parametry iterátory a ne samotné kontejnery, takže kontejnery musí poskytovat přístup ke svým prvkům pomocí iterátorů. Většina algoritmů pracuje s dvojicí iterátorů, které se zpravidla označují first a last. Ty představují rozsah (angl. range) všech iterátorů od first do last vyjma last. Rozsah se označuje intervalem [first, last). Rozsah je prázdný, pokud first == last. Rozsah je platný, pokud iterátor last je dosažitelný z iterátoru first. Triviální iterátor Triviální iterátor může být dereferencován, aby se zpřístupnila reference objektu, na který iterátor „ukazuje“. Může být měnitelný nebo konstantní. Není přímo využit žádným algoritmem. Je základním konceptem jiných iterátorů. Je zjemněním konceptů DefaultConstructible, Assignable, EqualityComparable. Všechny operace mají konstantní časovou složitost. Koncept musí splňovat následující vlastnost: Vlastnost identita
Platí x == y jen v tom případě, pokud platí &*x == &*y
Modelem triviálního konceptu je např. ukazatel na objekt, který není součástí pole objektů. Vstupní iterátor Vstupní iterátor slouží k procházení prvků kontejneru za účelem čtení objektů obsažených v kontejneru (nemodifikuje objekty kontejneru). Může být: • dereferencován, aby se zpřístupnila reference objektu, na který iterátor ukazuje, • inkrementován, aby se přesunul na následující iterátor nějaké posloupnosti. Je zjemněním triviálního iterátoru. Je konstantní. Po provedení výrazu ++i nelze použít kopii staré hodnoty i. Pokud platí i == j, nemusí platit ++i == ++j. Algoritmy nesmí dvakrát procházet přes stejný iterátor. Musí se jednat o tzv. jednoprůchodové (angl. single-pass) algoritmy. Iterátor totiž může při inkrementaci vyjmout prvek z kontejneru, např. ze vstupního datového proudu. Modelem vstupního iterátoru je např. šablona třídy istream_iterator. Vstupní iterátor používá např. algoritmus find, který provádí sekvenční hledání hodnoty value v rozsahu [first, last). Vrací iterátor, který ukazuje na hodnotu value. Jestliže hodnotu value nenajde, vrací last. Algoritmus find jakož i další generické algoritmy jsou definovány v hlavičkovém souboru . Vstupním iterátorům vyhovují např. obyčejné ukazatele (jsou modelem iterátoru s náhodným přístupem). Příklad V následujícím příkladu se hledá hodnota 7 v poli 10 celých čísel: int pole[10]; // naplnění pole int* i = find(pole, pole+10, 7); if (i == pole+10) cout << "Hodnota 7 v poli neexistuje"; else cout << "Hodnota 7 se poli nachazi na indexu " << i-pole; Výrazy pole a 31
pole+10 představují měnitelné iterátory. Konstantní iterátory jsou typu ukazatel na konstantní int, např.: Jazyk C a C++ const int *first = pole; const int *last = pole+10; const int *i = find(first, last, 7); Iterátory různých kontejnerů knihovny C++ také vyhovují vstupním iterátorům (vyhovují iterátorům, které jsou zjemněním vstupního iterátoru). Kontejnery obsahují dvě metody begin() a end(). Metoda begin() vrací iterátor, který ukazuje na první prvek kontejneru, metoda end() vrací koncový iterátor. Výstupní, Dopředný, Dvousměrný, S náhodným přístupem, Třídy iterátorů Inverzní iterátor Inverzní iterátor (angl. reverse iterator) je tzv. adaptér iterátoru, který prochází prvky kontejneru v opačném pořadí než normální iterátor. Adaptér (angl. adaptor) je třída nebo funkce, která konvertuje jedno rozhraní na jiné rozhraní. Adaptér iterátoru konvertuje určité rozhraní na rozhraní používané iterátory. Inverzní iterátor lze použít pro dvousměrný iterátor nebo iterátor s náhodným přístupem. Operátor inkrementace aplikovaný na objekt inverzního iterátoru provede totéž co operátor dekrementace aplikovaný na objekt korespondujícího normálního iterátoru. Základní vztah mezi inverzním iterátorem a jeho korespondujícím normálním iterátorem i je dán následující rovností: &*(reverse_iterator(i)) == &*(i - 1) Tento vztah je dán faktem, že koncový normální iterátor ukazuje za poslední platný prvek normální posloupnosti, přičemž k němu odpovídající inverzní iterátor musí ukazovat na první platný prvek opačné posloupnosti, tedy ukazuje na poslední platný prvek normální posloupnosti. Naopak k normálnímu iterátoru, který ukazuje na první platný prvek normální posloupnosti, odpovídá inverzní iterátor, který ukazuje za poslední platný prvek opačné posloupnosti, tedy ukazuje před první platný prvek normální posloupnosti. Vstupní iterátor datového proudu Vstupní iterátor datového proudu je šablona třídy istream_iterator, která čte objekty typu T pomocí operátoru >> ze vstupního datového proudu basic_istream resp. z jeho potomka. Šablona je modelem konceptu vstupního iterátoru. Při každé inkrementaci přečte jeden objekt typu T z datového proudu a uloží jej. Přečtený objekt je přístupný pomocí dereference iterátoru. Jestliže se dosáhne konce datového proudu, iterátor obsahuje speciální hodnotu, která indikuje koncový iterátor. Výstupní iterátor datového proudu Výstupní iterátor datového proudu je šablona třídy ostream_iterator, která zapisuje objekty typu T pomocí operátoru << do výstupního datového proudu basic_ostream resp. do jeho potomka. Šablona je modelem konceptu výstupního iterátoru. Za každý zapsaný objekt typu T může být zapsán ještě řetězec znaků, který je parametrem konstruktoru. copy(IntList.begin(),IntList.end(),ostream_iterator(cout,",")); 32
Jazyk C a C++
3.12 Generické programování v C++ - funktory, adaptabilní funktory, adaptéry funktorů, koncepty a modely kontejnerů Funktor (angl. functor nebo function object) je jakýkoli objekt, který lze použít po vzoru funkce s kulatými závorkami. Funktorem je tedy ukazatel nebo reference na obyčejnou funkci (včetně operátorové funkce) nebo instance třídy, která má přetížený operátor volání funkce. Řada generických algoritmů má jako svůj parametr funktor. template UnaryFunction for_each(InputIterator first, InputIterator last,UnaryFunction f){ for (; first != last; ++first) f(*first); return f;} Algoritmus for_each pro každý prvek rozsahu [first, last) volá funktor f, který nesmí modifikovat prvek rozsahu. V normě C++ je druhý typový parametr této šablony pojmenován Function, ale přesnější je pojmenování UnaryFunction uvedené v knihovně STLport, protože funktor je volán s jedním parametrem. Adaptabilní funktory a adaptéry funktorů Adaptabilní funktory jsou funktory, které obsahují deklaraci vnořených typů pro návratový typ a parametry funktoru. Musí obsahovat pouze deklaraci vnořeného typu result_type, který představuje návratový typ generátoru. Adaptabilní unární funkce a adaptabilní predikát musí obsahovat deklaraci dvou vnořených typů: • result_type – návratový typ funktoru, • argument_type – typ parametru funktoru. Adaptabilní binární funkce a adaptabilní binární predikát musí obsahovat deklaraci tří vnořených typů: • result_type – návratový typ funktoru, • first_argument_type – typ prvního parametru funktoru, • second_argument_type – typ druhého parametru funktoru. Význam adaptabilních funktorů spočívá v tom, že je mohou využít adaptéry funktorů. Adaptér funktoru (angl. function object adapter) je adaptabilní funktor, který transformuje rozhraní jiného adaptabilního funktoru. Z toho vyplývá, že lze adaptéry řetězit a určitému algoritmu lze předat jako parametr místo funktoru např. adaptér adaptéru funktoru. Standardní funktory pro operátory vestavěných datových typů nelze získat adresu, která by se mohla použít jako ukazatel na funkci při volání nějakého generického algoritmu. Pro tento účel se musejí volat pomocí funktorů. V hlavičkovém souboru je definováno velké množství adaptabilních funktorů, které implementují velké množství aritmetických, relačních nebo logických operátorů. jsou založeny na binárních a unárních funkcích. Negátory adaptér funktoru který neguje výsledek volání adaptabilního predikátu. unární neguje unární predikát a je modelem adaptabilního predikátu, Binární je model adaptabilního binárního predikátu a neguje binární predikát (not1,not2) Jazyk C a C++ Vazače jsou adaptéry funktorů, které transformují binární funkci na unární tak, že jeden z parametrů binární fce je fixní. jsou modelem adaptabilní unární funkce (binder1st,binder2nd)
33
Adaptéry obyčejných funkcí Aby mohla být obyčejná funkce modelem adaptabilního funktoru, musí obsahovat deklarace vnořených typů. To se provede vytvořením adaptéru, který požadované vnořené typy deklaruje. pointer_to_unary_function pointer_to_binary_function Adaptéry metod objektových typů adaptery metod umožňují použít na místě volání funktoru volání metody určité třídy. Obsahují třídní ukazatel na určitou metodu, který je inicializován konstruktorem. Operátor volání funkce volá prostřednictvím třídního ukazatele příslušnou metodu, a to pro instanci, která je prvním parametrem operátoru volání funkce. Existuje osm typů těchto adaptérů. Liší se typem prvního parametru operátoru volání funkce. KONCEPTY KONTEJNERŮ Kontejner (angl. container) je objekt, který obsahuje jiné objekty, tzv. prvky (angl. elements) a obsahuje metody pro zpřístupnění jeho prvků. V normě jazyka C++ jsou definovány společné požadavky na všechny kontejnery, které odpovídají konceptu dopředného kontejneru a konceptu DefaultConstructible. Dále jsou v normě definovány požadavky na sekvenci (přibližně odpovídají konceptu Sekvence) a asociativní kontejner. Všeobecné koncepty kontejnerů Koncept Kontejner Základním konceptem kontejnerů je Kontejner (angl. Container). Ostatní koncepty kontejnerů jsou přímo nebo nepřímo jeho zjemněním. Kontejner musí mít mj. sdružený typ iterator, který slouží k procházení prvků kontejneru. Není zaručena neměnnost pořadí prvků kontejneru při jeho iteraci. Není garantováno, že v určitém okamžiku bude aktivní pouze jeden iterátor daného kontejneru. Kontejner vlastní své prvky. Prvky zániku kontejneru zaniknou ukazatele, ale objekty, na které ukazatele ukazují, zaniknout nemusí. Velikost (angl. size) kontejneru je počet prvků kontejneru. Koncept kontejneru je zjemněním konceptu Assignable. Dopředný kontejner Dopředný kontejner je kontejner, u kterého se pořadí prvků při iteraci nemění. Tím pádem mohou být dva dopředné kontejnery porovnávány pomocí relačních operátorů ==, !=, <, <=, > a >=. Dopředný kontejner je tedy zjemněním nejen konceptu Kontejner, ale i konceptů LessThanComparable a EqualityComparable. Při porovnávání dvou kontejnerů se porovnávají jejich prvky, a proto prvky kontejneru musí být modelem nejen konceptu Assignable, ale i konceptu LessThanComparable a EqualityComparable. Iterátor dopředného kontejneru musí být modelem dopředného iterátoru nebo jeho zjemnění. Tím pádem může být kontejner používán víceprůchodovými algoritmy. V jednom okamžiku může být aktivních více iterátorů stejného kontejneru. Jazyk C a C++ Reverzibilní kontejner Reverzibilní kontejner je dopředný kontejner, jehož iterátor je dvousměrný. Modelem tohoto konceptu je kontejner list . Kontejner list je navíc modelem konceptů sekvence s vkládáním na začátek a sekvence s vkládáním na konec. Kontejner s náhodným přístupem 34
Kontejner s náhodným přístupem je reverzibilní kontejner, jehož iterátor je iterátor s náhodným přístupem. Modelem tohoto konceptu jsou kontejnery vector a deque. Kontejner vector je navíc modelem konceptu sekvence s vkládáním na konec a kontejner deque je navíc modelem konceptů sekvence s vkládáním na začátek a sekvence s vkládáním na konec. KONCEPTY KONTEJNERŮ – SEKVENCE Sekvence Sekvence je kontejner, jehož velikost se může měnit a jehož prvky jsou uchovávány v lineárním pořadí. Sekvence je tedy koncept nějaké lineární datové struktury. Je zjemněním konceptu dopředného kontejneru a konceptu DefaultConstructible. Typ prvků sekvence musí být modelem konceptů Assignable, LessThanComparable, EqualityComparable a DefaultConstructible. Sekvence s vkládáním na začátek Sekvence s vkládáním na začátek je sekvence, která umožňuje vkládání prvku na začátek kontejneru a odstranění prvního prvku z kontejneru s konstantní časovou složitostí. Modelem tohoto konceptu jsou kontejnery list a deque. Tyto kontejnery jsou navíc modelem dalších konceptů. Sekvence s vkládáním na konec Sekvence s vkládáním na konec je sekvence, která umožňuje přidání prvku na konec kontejneru, odstranění posledního prvku z kontejneru a získání hodnoty posledního prvku kontejneru s konstantní časovou složitostí. Modelem tohoto konceptu jsou kontejnery vector, deque a list. Tyto kontejnery jsou modelem i dalších konceptů. Šablona třídy vector Šablona třídy vector je sekvence, která má iterátor s náhodným přístupem. I když norma jazyka C+ + nespecifikuje vnitřní strukturu kontejneru, jedná se o šablonu abstraktní datové struktury jednorozměrného pole neboli vektoru. Vektor je dynamicky alokovaný a po jeho vytvoření lze do něj prvky přidávat nebo z něj odstraňovat. Vložení a odstranění prvku na konci vektoru má konstantní časovou složitost, zatímco vložení a odstranění prvku v jiném místě vektoru má lineární časovou složitost. Vektor může být alokován na více prvků, než kolik jich právě obsahuje. Celkový počet prvků, které vektor může obsahovat bez potřeby realokace, se nazývá kapacita vektoru. Kapacitu vektoru lze jen zvýšit. Kapacita se nesníží ani při odstranění všech prvků z vektoru. Pokud je kapacita vektoru rovna velikosti vektoru a má se do něj vložit další prvek, kapacita vektoru se určitým způsobem zvýší. Při realokaci vektoru (při změně jeho kapacity) se zneplatní všechny iterátory a ukazatele na prvky vektoru. Šablona je definována v hlavičkovém souboru . Šablona třídy vector Šablona třídy vector je parciální specializací šablony třídy vector pro prvky typu bool. Každý prvek tohoto vektoru zabírá jeden bit. Jazyk C a C++ Šablona obsahuje vnořenou třídu reference, která představuje referenci na prvek vektoru. Konstantní reference je deklarována jako synonymum pro typ bool. Reference má tyto složky: • neveřejný konstruktor – nelze tedy vytvořit instanci tohoto typu mimo třídu reference (kromě šablony vector, která je přítelem reference), • operátor přetypování na typ bool, • operátor přiřazení z hodnoty typu bool, • kopírovací operátor přiřazení, 35
• metoda flip() – neguje (překlopí) bit, který je s referencí spjat, tj. z hodnoty 0 vytvoří hodnotu 1 a naopak. Oproti primární definici šablony vector obsahuje šablona vector dvě další metody. static void swap(reference x, reference y); Vymění hodnoty (bity) dvou referencí void flip(); Neguje (překlopí) všechny bity (hodnoty prvků) vektoru. Šablona třídy deque Šablona třídy deque představuje obousměrnou frontu. Jméno deque (vyslovuje se stejně jako anglické slovo „deck“) je zkratkou textu „double-ended queue“. Je podobná šabloně třídy vector. Oproti vektoru je navíc modelem sekvence s vkládáním na začátek, tj. lze s konstantní časovou složitostí vložit nebo odstranit prvek na začátku fronty. S konstantní časovou složitostí lze tedy provést i operace vložení a odstranění prvku na konci fronty a operaci náhodného přístupu k prvku. Operace vložení a odstranění prvku uvnitř fronty má lineární časovou složitost. Ačkoli šablona deque provádí s konstantní časovou složitostí stejné operace jako šablona vector, šablona vector danou operaci provede zpravidla rychleji, protože její implementace je jednodušší než šablony deque. Interní reprezentace obousměrné fronty závisí na typu použité knihovny. Může se jednat o jednorozměrné pole s platnými prvky od určitého po určitý index pole. Nebo se může jednat o pole ukazatelů na pole prvků. Všechny iterátory fronty se zneplatní při vložení prvku na jakoukoli pozici do fronty (včetně na začátek a konec) a při odstranění prvku ze středu fronty. Pokud se odstraní prvek ze začátku nebo konce fronty, zneplatní se jen iterátor, který ukazuje na odstraněný prvek. Šablona je definována v hlavičkovém souboru <deque>. Deklarace šablony je následující: template > class deque; Význam typových parametrů je stejný jako u šablony vector. Narozdíl od vektoru nemá metody capacity a resize, ale jako vektor obsahuje dvě metody assign – jejich význam je stejný jako u vektoru. Šablona třídy list Šablona třídy list je sekvence, která má dvousměrný iterátor. Představuje abstraktní datovou strukturu obousměrného zřetězeného seznamu. Konkrétní typ seznamu záleží na implementaci v dané knihovně. Je modelem konceptu reverzibilního kontejneru, sekvence s vkládáním na začátek a na konec. Vložení a odstranění prvků z kterékoli pozice v seznamu má konstantní časovou složitost. Zpřístupnění prvku uvnitř seznamu má lineární časovou složitost. Iterátory seznamu zůstanou platné při vložení prvku na jakoukoli pozici do seznamu. Při odstranění prvku ze seznamu se zneplatní pouze iterátor, který ukazuje na odstraněný prvek. Šablona třídy list je definována v hlavičkovém souboru <list> a její deklarace je následující: template > class list; Jazyk C a C++ Šablona třídy slist Šablona třídy slist je sekvence, která má dopředný iterátor. Představuje abstraktní datovou strukturu jednosměrného zřetězeného seznamu. Šablona není součástí normy jazyka C++, je uvedena pouze v knihovně STLport. Je modelem konceptu sekvence s vkládáním na začátek. Bližší informace viz nápověda ke knihovně STLport. Šablona třídy basic_string Šablona třídy basic_string je sekvence znaků neboli řetězec znaků. Je modelem stejných konceptů jako šablona třídy vector, tj. konceptu kontejneru s náhodným přístupem a sekvence s vkládáním na 36
konec. Šablona je definována v hlavičkovém souboru <string>. Asociativní kontejner Asociativní kontejner je kontejner s proměnlivou velikostí, který umožňuje rychlé hledání prvků podle klíče. Umožňuje vložení a odstranění prvku, ale na rozdíl od sekvence není možné zadat pozici, na kterou se má prvek vložit. Prvky asociativního kontejneru jako u ostatních kontejnerů jsou typu value_type. Prvky jsou svázány s klíčem typu key_type. U jednoduchých asociativních kontejnerů (koncept Jednoduchý asociativní kontejner a jeho zjemnění) je typ value_type totožný s typem key_type, tj. hodnota prvku je jeho klíčem. U ostatních asociativních kontejnerů klíč tvoří určitou část hodnoty prvku. Prvky jsou do kontejneru ukládány podle jejich klíče. Klíče prvků nelze modifikovat. U jednoduchých asociativních kontejnerů jsou tudíž hodnoty prvků konstantní. U ostatních asociativních kontejnerů lze modifikovat tu část hodnoty prvku, která netvoří klíč. Z toho vyplývá, že asociativní kontejnery nemohou mít měnitelné iterátory. Měnitelný iterátor umožňuje přiřazení hodnoty do prvku výrazem *i = t, kde i je iterátor a t objekt typu hodnoty prvku. U jednoduchých asociativních kontejnerů jsou vnořené typy iterator a const_interator totožné. U ostatních asociativních kontejnerů není sice typ iterator měnitelným iterátorem (nelze napsat *i = t), ale poskytuje mechanismus modifikace části hodnoty prvku, která netvoří klíč, např. výrazem (*i).second = d. Některé asociativní kontejnery mají klíč jedinečný, u jiných kontejnerů může existovat více prvků se stejným klíčem. Norma jazyka C++ obsahuje pouze koncept Asociativní kontejner, který popisuje vlastnosti všech konceptů asociativních kontejnerů kromě hašovacích. Modely hašovacích kontejnerů nejsou v normě jazyka C++ obsaženy. Koncept Asociativní kontejner je zjemněním konceptů Dopředný kontejner a DefaultConstructible. Prvky se stejným klíčem jsou při procházení kontejneru pomocí iterátorů za sebou. To znamená, že jestliže iterátory p a q ukazují na prvky se stejným klíčem a jestliže iterátor p předchází iterátoru q, potom každý prvek rozsahu [p, q) má stejný klíč. Jednoduchý asociativní kontejner Jednoduchý asociativní kontejner je kontejner s prvky, jejichž hodnota tvoří jejich klíč. Je zjemněním konceptu asociativního kontejneru. Vnořený typ key_type je totožný s typem value_type. Kontejner nemá měnitelný iterátor, má jen konstantní iterátor, tudíž typy iterator a const_iterator jsou stejné. Hodnoty prvků kontejneru jsou konstantní, nelze je modifikovat. Lze je pouze vkládat a odstraňovat. Důvodem je skutečnost, že hodnota prvku je zároveň jeho klíč. Modelem konceptu jednoduchého asociativního kontejneru jsou kontejnery set, multiset, hash_set a hash_multiset, které jsou modelem i jiných konceptů. Jazyk C a C++ Párový asociativní kontejner Párový asociativní kontejner je kontejner s prvky, jejichž hodnota se skládá ze dvou částí: datové složky a klíče. Je zjemněním asociativního kontejneru. Kromě vnořených typů požadovaných v konceptech, kterého je zjemněním, musí mít deklarován vnořený typ mapped_type a specifikuje další požadavky na typy key_type a value_type Modelem konceptu párového asociativního kontejneru jsou kontejnery map, multimap, hash_map a hash_multimap, které jsou modelem i jiných konceptů. Tříděný asociativní kontejner Tříděný asociativní kontejner má klíče prvků utříděné vzestupně. Je zjemněním konceptů reverzibilní kontejner a asociativní kontejner. 37
Většina operací v tříděném asociativním kontejneru má maximálně logaritmickou časovou složitost. Jednoznačný asociativní kontejner Jednoznačný asociativní kontejner je kontejner s prvky, jejichž klíče jsou jedinečné. Nemůže v něm existovat více prvků se stejným klíčem. Je zjemněním konceptu asociativního kontejneru. Víceznačný asociativní kontejner Víceznačný asociativní kontejner je kontejner, ve kterém se může vyskytovat více prvků se stejným klíčem. Je zjemněním konceptu asociativního kontejneru. Jednoznačný tříděný asociativní kontejner Jednoznačný tříděný asociativní kontejner je tříděný kontejner s prvky, jejichž klíče jsou jedinečné. Nemůže v něm existovat více prvků s ekvivalentním klíčem. Je zjemněním konceptu jednoznačného asociativního kontejneru a tříděného asociativního kontejneru. Prvky v jednoznačném tříděném asociativním kontejneru jsou uspořádány podle svých klíčů vzestupně. To znamená, že jestliže iterátor i předchází iterátoru j, potom výraz a.value_comp()(*i, *j) je vždy pravdivý Modelem konceptu jednoznačného tříděného asociativního kontejneru jsou kontejnery set a map, které jsou modelem i jiných konceptů. Víceznačný tříděný asociativní kontejner Víceznačný tříděný asociativní kontejner je tříděný kontejner, v němž může existovat více prvků s ekvivalentním klíčem. Je zjemněním konceptu víceznačného asociativního kontejneru a tříděného asociativního kontejneru. Modelem konceptu víceznačného tříděného asociativního kontejneru jsou kontejnery multiset a multimap, které jsou modelem i jiných konceptů. Šablona třídy set Šablona třídy set je asociativní kontejner, který má dvousměrný iterátor. Je modelem konceptů jednoduchého asociativního kontejneru a jednoznačného tříděného asociativního kontejneru. To znamená, že objekty ukládané do kontejneru jsou zároveň klíčem, klíče prvků jsou utříděné vzestupně a v kontejneru neexistují dva prvky s ekvivalentním klíčem. Při vložení prvku do šablony set zůstanou iterátory této šablony platné. Při odstranění prvku ze šablony se zneplatní pouze iterátor, který ukazuje na odstraněný prvek. Anglické slovo „set“ lze přeložit do češtiny jako „množina“. Jedná se tedy o kontejner obsahující množinu rozdílných prvků. Interně je implementována jako určitý typ binárního stromu. Šablona je definována v hlavičkovém souboru <set>. Šablona třídy multiset Šablona třídy multiset je asociativní kontejner, který má dvousměrný iterátor. Je modelem konceptů jednoduchého asociativního kontejneru a víceznačného tříděného asociativního kontejneru. To znamená, že objekty ukládané do kontejneru jsou zároveň klíčem, klíče prvků jsou utříděné vzestupně a v kontejneru může existovat více prvků s ekvivalentním klíčem. Při vložení prvku do šablony multiset zůstanou iterátory této šablony platné. Při odstranění prvku ze šablony se zneplatní pouze iterátor, který ukazuje na odstraněný prvek. Interně je implementována jako určitý typ binárního stromu. Šablona je definována v hlavičkovém souboru <set>. Šablona třídy map Šablona třídy map je asociativní kontejner, který má dvousměrný iterátor. Je modelem konceptů párového asociativního kontejneru a jednoznačného tříděného asociativního kontejneru. To znamená, že objekty ukládané do kontejneru se skládají z datové složky a klíče. Prvky jsou utříděné 38
podle svých klíčů vzestupně a v kontejneru neexistují dva prvky s ekvivalentním klíčem. Při vložení prvku do šablony map zůstanou iterátory této šablony platné. Při odstranění prvku ze šablony se zneplatní pouze iterátor, který ukazuje na odstraněný prvek. Interně je implementována jako určitý typ binárního stromu. Šablona je definována v hlavičkovém souboru <map>. Šablona třídy multimap Šablona třídy multimap je asociativní kontejner, který má dvousměrný iterátor. Je modelem konceptů párového asociativního kontejneru a víceznačného tříděného asociativního kontejneru. To znamená, že objekty ukládané do kontejneru se skládají z datové složky a klíče. Prvky jsou utříděné podle svých klíčů vzestupně a v kontejneru může existovat více prvků s ekvivalentním klíčem. Při vložení prvku do šablony multimap zůstanou iterátory této šablony platné. Při odstranění prvku ze šablony se zneplatní pouze iterátor, který ukazuje na odstraněný prvek. Interně je implementována jako určitý typ binárního stromu.Šablona je definována v hlavičkovém souboru <map>.
39
