PA2 Flashcards
Programovací styly
- Naivní – veškerý kód ve funkci main
- Procedurální – rozložení problému na podproblémy, které jsou realizovány funkcemi a procedurami
- Objektově orientovaný – při rozkladu na podproblémy specifikujeme nové datové typy
Objektově orientovaného programování v C++
• Realizace datový abstrakcí (typů) použitím tříd a objektů
• Objekt se může nacházet v různých stavech daných hodnotami atributů
objektu
• Chování objektu je dáno metodami, které jsou pro něj definovány
• Datové položky a metody objektu jsou dány typem objektu (třídou)
Zapouzdření (Encapsulation)
• Ukrytí implementačních detailů rozhraním třídy (metodami třídy)
• Řízení přístupu pomocí klíčových slov
o public,
o protected
o private
• Privátní metody a atributy jsou zapouzdřeny, přístupné jen v metodách dané třídy
• Chráněné metody a atributy jsou částečně zapouzdřeny, jsou přístupné v metodách dané třídy a jejích potomků
Dědičnost (Inheritance)
- Existence vztahu rodič – potomek mezi třídami (datovými typy)
- Může deklarovat nové atributy a metody
- Metodu je možné předefinovat, atribut nikoli
- Potomek má přístup ke všem veřejným a neprivátním atributům a metodám
- Potomek může být přiřazen předkovi, nikoli však předek potomkovi
Atributy a metody
Atribúty
- zachytávajú vlastnosti objektu pomocou dátových typov
Metody
- chovanie objektu
- procedura/funkce spojená s triedou
- špeciálne - konštruktor, deštruktor
Statické atributy a metody
Statické atribúty
- nie sú súčasťou objektu, ale triedy
Statické metódy
- nejde aplikovať na objekty, ale len na triedu (triedne metódy)
- statické metódy nemôžu používať nestatické položky
Virtuální metody
- Dynamicky viazaná metóda
- Kľúčové slovo virtual
- Je volaná podľa typu objektu - zavolá sa vždy správná metoda, aj keď ju voláme na premennú typu predka
- virtual table method
Polymorfismus (Mnohotvarovost)
- Operace s prvkem v závislosti na jeho presnom type
- v kolekcií môžu byť prvky typu abstraktného predka, ale každá položka je konkrétneho typu a podľa toho sa volá pri volaní metódy - polymorfne
Příklad:
• Použití například pro kolekci prvků (např.: třída Element), které chceme vypsat.
• Procházíme kolekci a každou položku pošleme do streamu, protože víme, že má přetížený operátor pro uložení
do streamu.
• V každém potomkovi třídy Element může být tento výpis různý.
• Polymorfismus se postará o to, aby se každý prvek vypsal podle svého typu a nikoli obecným způsobem
definovaným ve třídě Element.
Abstraktní třída
• Je třída, která definuje nebo dědí alespoň 1 čistě virtuální funkci.
o Virtuální funkce se značí funkce() = 0; (+ na začátku může být nepovinné klíčové slovo „virtual“)
• Definuje abstraktní typ z kterého nemůže být vytvořena instance.
• Slouží jako základní třída v třídním uspořádání.
• Například čítač může být číselný, znakový a pro datum, ale předek může být stejný pro všechny a deklarovat jim
rozhraní (například jako šablona).
• Operace definovány až pro potomky.
Výjimky
- Ošetřování chyb při běhu programu.
- Zachycovány ovladači výjimek (exception handlers) – try catch bloky.
- Vyvolání výjimky příkazem throw.
- Výjimka se šíří vzhůru k nejbližšímu ovladači, který ji ošetří, v průběhu je čištěn zásobník a volány destruktory lokálních objektů (implementačně závislé).
Šablona - Funkce
- Parametrizozvaná deklarace funkce, z kt. prekladač môže dosadením za parametre vytvoriť instanciu šablóny
- Parametrom šablóny môže byť typ parametru alebo návratového typu funkcie
- Typ je možné určit explicitně umístěním do špičatých závorek
Šablona - Triedy
- Parametrizovaná deklarace třídy, ze které překladač může dosazením za parametry vytvořit instanci šablony, tj. deklaraci konkrétní třídy.
- Principy podobné jako pro šablony funkcí.
- Metody třídy jsou definovány šablonami funkcí.
Přetěžování operátorů
• Použití běžných operátorů jazyka pro vlastní datové typy (třídy)
o Např třída Zlomek může implementovat operátor + a umožnit tak sčítání dvou zlomků.
• Operátory pro práci s proudy (streamy), operátor přiřazení, sčítací znaménko, přístup k položce pole, volání metody, atd.
• Možné přetížit běžnou funkcí nebo metodou – nepřirozená syntax
• Pro použití běžným zápisem (c = a + b) použijeme friend metody, případně lze :
Mělká a hluboká kopie
Mělká kopie
• Přiřazení mezi objekty stejného typu → reference ukazuje na stejná data.
• Nevadí, pokud o ní víme.
• Problém s destruktorem – můžeme už uvolnit paměť nebo na data vede ještě nějaká reference?
• Možno řešit počítáním referencí.
Hluboká kopie
• Dealokace paměti, na kterou ukazuje první reference.
• Následně dynamické kopírování dat z jednoho objektu do druhého.
• Ideální přetížit operátor přiřazení.
Kopírovací konstruktor
• Implicitní vytvořen kompilátorem, vytváří mělkou kopii.
• Pro hlubokou kopii musíme sami implementovat (třeba pomocí přetíženého operátoru přiřazení)
Abstraktní datový typ (ADT)
• Množina operací nezávislá na konkrétní implementaci
• Hlavním cílem je zjednodušit a zpřehlednit program, který provádí operace s daným datovým typem.
• Při programování je ADT reprezentováno rozhraním, které skrývá vlastní implementaci. Klientského
programátora, který ADT používá, zajímá jak objekt používat (jeho rozhraní), ale ne už vlastní implementace.
signatura operace:
_ + _ : int, int → int celočíselné plus (infixový zápis)
_ – : int → int postdekrementace
Datová struktura
Konkrétní implementace ADT v daném programovacím jazyce. Zahrnuje reprezentaci dat a algoritmy, které
implementují danou množinu operací.
Možné implementační datové struktury:
a) pole (statické/dynamické a uspořádané/neuspořádané),
b) rozptylovací (hash) tabulka,
c) lineární spojové struktury (jednosměrný/obousměrný spojový seznam),
d) nelineární spojové struktury (stromy, grafy).
Zásobník (Stack)
● Kontejner, kde data vložená naposledy jsou nejdříve
odebrána (last in, first out – LIFO).
● Interface: Push, Pop, Top, isEmpty
● Implementace
○ Spojová struktura
■ Jednosměrný spojový seznam
○ Pole
■ Statické pole (velikost dána konstantou)
■ Dynamicky alokované pole (velikost daná parametrem konstruktoru)
■ Dynamicky alokované pole s možností rozšiřování
● Složitost: O(1) tedy konstantní, kromě implementace pomocí rozšiřitelného pole
Fronta (Queue)
● Kontejner, kde data vkládáme na konec a odebíráme ze začátku (first in, first out – FIFO).
● Interface: Enqueue (Push), Dequeue (Pop), Front, isEmpty
● Implementace stejná jako u zásobníku (pole/spojový seznam)
○ Při spojovém seznamu potřebujeme odkaz i na konec (ne jen na začátek)
○ Cyklické pole pro posuny – pozor na přetečení do nového kolečka
● Složitost: O(1), kromě jednoduchého pole – tam dequeue celé pole posouvá -> O(n)
Pole (Array)
● Kontejner, kde jsou prvky v n-dimenzích.
● Umožnuje náhodný přístup k prvkům s konstantní časovou složitostí.
● Popis pole
○ Datový typ prvků
○ Počet dimenzí
○ Horní a dolní meze jednotlivých dimenzí
● Příklad: array[l1..h1, l2..h2, · · · , ln..hn] of T
○ T je typ prvku pole
○ n je počet dimenzí
○ li a hi jsou meze indexu v dimenzi i
Seznam (List)
● Kontejner, kde data vkládáme, odebíráme a čteme
přímo z dané pozice
● Interface: Insert, Delete, Next, Prev, Read, toEnd, toStart,…
● Implementace:
○ Nejefektivnější je obousměrný spojový seznam s ukazatelem na začátek i konec
● Složitost: O(1), pokud chceme hledat – O(n) – nutno projet celý seznam.
Tabulka (Map, Table)
● Kontejner s dvojicí Key-Val
● Prvek je tedy identifikován klíčem typu Key skrz který se dostaneme na hodnotu Val
● Interface: Insert, Delete, isSet, Read
● Implementace:
○ Pole, kde klíče jsou indexy v poli
■ přímý přístup
■ Jsou-li klíči celá čísla od 0..max, použijeme pro uložení hodnot pole, jehož indexy
jsou přímo klíče. Prvek tabulky s klíčem k tedy bude mít hodnotu uloženou v
prvku pole tab[k].
○ Pole (seřazené/neseřazené)
○ Jednosměrný spojový seznam (seřazený/neseřazený )
○ Binární vyhledávací strom
○ Rozptylovací tabulka (hash table)
Množina (Set)
● Kontejner, který obsahuje prvky typu T bez duplikátů
● Interface
○ minimálně: Insert, Delete, isSet (příslušnost prvku k množině)
○ Další: sjednocení, porovnání, průnik, výpis prvků
● Implementace:
○ Pole (seřazené/neseřazené)
○ Jednosměrný spojový seznam (seřazený/neseřazený)
○ Binární vyhledávací strom
○ Rozptylovací tabulka (hash table)
○ Indikátorový (charakteristický) vektor - funkce, která má hodnotu 0 pro prvky, které do
množiny nepatří a 1 pro ty, které do ní patří
