⚙️ BI-PA2 – Programování a Algoritmizace 2

🏗️ Třídy, objekty a základní pojmy OOP

OOP styl vychází z analýzy problému: identifikujeme entity reálného světa, jejich vlastnosti (stav) a interakce (interface). Každá třída tak zastupuje jednu entitu.

Tři programovací styly

• Naivní: vše v main, žádná struktura, copy-paste, nevhodný pro větší projekty.
• Procedurální: data v strukturách (struct), operace jsou separátní funkce s explicitním parametrem struktury (např. a_push(Array& a, int x)). Snazší testování, ale názvy funkcí musejí nést prefix pro odlišení typů.
• OOP: data a funkce sloučeny v objektu. Stav objektu je soukromý, public interface diktuje, co lze s objektem dělat.

Syntaxe třídy

struct Array {
    Array();            // konstruktor
    ~Array();           // destruktor
    size_t size() const;
    void push(int x);
private:
    size_t size_, cap_;
    int *data_;
};

Klíčové slovo this

Uvnitř metody je this ukazatel na aktuální instanci. Slouží k rozlišení lokálních proměnných a atributů třídy (zejm. při kolizích jmen). Dobrou praxí je dávat atributům prefix m_ nebo suffix _.

🔒 Zapouzdření (Encapsulation)

• public – přístupné komukoli.
• protected – přístupné ve třídě a jejích podtřídách.
• private – přístupné pouze ve třídě samé.

Proč ne "getter pro každou proměnnou"?

Pokud má proměnná veřejný getter i setter, lze ji rovnou zveřejnit. Getter+setter navíc zavazují třídu k určité implementaci. Lepší je nabídnout smysluplné operace (např. push(x), sort()) místo surového přístupu k datům.

Konstantní objekty a metody

Metoda označená const zaručuje, že nemodifikuje atributy. Na konstantním objektu lze volat pouze konstantní metody. Typický vzor – dvě přetížené varianty přístupu k prvku:

int& at(size_t i);        // nekonstantní – vrací referenci pro zápis
int  at(size_t i) const;  // konstantní   – vrací hodnotu

🔧 Konstruktory, destruktory, statické členy

Konstruktor a destruktor

• Konstruktor je volán automaticky při vytvoření objektu (T x(a,b) nebo new T(a,b)).
• Destruktor je volán při zániku objektu – automaticky pro lokální proměnné, explicitně přes delete pro dynamicky alokované.
• Atributy jsou inicializovány v initializer listu (za :), před vstupem do těla konstruktoru. Pořadí inicializace odpovídá pořadí deklarace atributů ve třídě.

Array::Array() : size_(0), cap_(0), data_(nullptr) {}
// Delegující konstruktor:
Array(int v) : Array() { push(v); }

Statické (třídní) atributy a metody

Statické atributy jsou sdíleny všemi instancemi třídy – existuje jen jedna kopie v paměti, bez ohledu na počet objektů. Statické metody nemají přístup k this ani k instančním atributům.

class T {
    static inline int cnt = 0;   // od C++17: inline v hlavičce
public:
    T() { cnt++; }
    ~T() { cnt--; }
    static int getCount() { return cnt; }
};
// Volání statické metody:
cout << T::getCount();

📋 Mělká a hluboká kopie

Proč je mělká kopie problém s pointery?

Generovaný kopírovací operátor = kopíruje pointer, nikoli data. Oba objekty pak sdílejí jeden blok paměti – modifikace jednoho změní druhý a při destrukci dojde k double free.

Pravidlo tří (Rule of Three)

// Hluboká kopie – kopírovací konstruktor:
Array::Array(const Array& o)
    : size_(o.size_), cap_(o.cap_),
      data_(cap_ ? new int[cap_] : nullptr) {
    for (size_t i = 0; i < size_; i++)
        data_[i] = o.data_[i];
}

// Kopírovací operator= s kontrolou samopřiřazení:
Array& Array::operator=(const Array& o) {
    if (&o == this) return *this;  // ochrana před a = a
    delete[] data_;
    size_ = o.size_; cap_ = o.cap_;
    data_ = cap_ ? new int[cap_] : nullptr;
    for (size_t i = 0; i < size_; i++)
        data_[i] = o.data_[i];
    return *this;
}

Idiom copy-and-swap

Elegantní implementace operátoru přiřazení: parametr se přebírá hodnotou (volá se kopírovací konstruktor), pak se prohodí vnitřní data. Tím se automaticky ohlídá bezpečnost a samopřiřazení.

Array& Array::operator=(Array o) {  // o je kopie
    using std::swap;
    swap(size_, o.size_);
    swap(cap_, o.cap_);
    swap(data_, o.data_);
    return *this;
}  // destruktor o uvolní starou paměť

Pravidlo pěti (C++11) – rvalue reference a přesouvání

• rvalue reference (&&) označuje dočasný objekt, jehož obsah lze "ukrást".
• std::move převede lvalue na rvalue – upozorní překladač, že zdroj lze přesunout.
• Přesouvací konstruktor převezme data ze zdroje a nastaví zdroj do validního prázdného stavu.

Array::Array(Array&& o)
    : size_(o.size_), cap_(o.cap_), data_(o.data_) {
    o.size_ = o.cap_ = 0;
    o.data_ = nullptr;
}

🌲 Dědičnost (Inheritance)

class CCounter {           // základní třída
protected:
    int m_Val, m_InitVal;
public:
    virtual void increment() { m_Val++; }
    virtual void decrement() { m_Val--; }
    void reset()  { m_Val = m_InitVal; }
    int get() const { return m_Val; }
    CCounter(int val) { m_InitVal = val; reset(); }
};

class CCounterMod : public CCounter {
    int m_Modulus;
public:
    void increment() override {
        CCounter::increment();
        m_Val %= m_Modulus;
    }
    CCounterMod(int val, int mod)
        : CCounter(val % mod), m_Modulus(mod) {}
};

Paměťová reprezentace

Objekt potomka obsahuje v paměti celý objekt předka jako svoji první část, za ním následují atributy potomka. Proto lze ukazatel na potomka přiřadit ukazateli na předka.

Klíčová slova dědičnosti

Klíčové slovo override (C++11)

Označení override u metody říká překladači: "tato metoda přepisuje virtuální metodu předka." Překladač pak hlásí chybu, pokud předek žádnou takovou virtuální metodu nemá – chrání před překlepovými chybami (jiná signatura, chybějící const apod.).

🎭 Virtuální metody a polymorfismus

Statická vs. dynamická vazba

CCounter* p = new CCounterMod(0, 5);
p->increment();  // bez virtual: CCounter::increment
                 //  s virtual: CCounterMod::increment ✓

Virtuální tabulka metod (VMT / vtable)

Každá třída s virtuálními metodami má VMT – pole ukazatelů na implementace metod. Každý objekt nese ukazatel na VMT své třídy (inicializovaný konstruktorem). Volání virtuální metody = přečtení adresy z VMT + nepřímé volání → O(1), ale 2 dereference paměti navíc.

class Base {
public:
    virtual ~Base() {}  // ← POVINNÉ!
    virtual void foo();
};

📐 Abstraktní třídy a čisté virtuální metody

Abstraktní třídy definují interface: zavazují všechny potomky, aby implementovaly dané metody, ale samy o tom, jak to udělají, nerozhodují.

struct CCounter {
    virtual ~CCounter() {}
    virtual void increment() = 0;
    virtual void decrement() = 0;
    virtual void reset()     = 0;
    virtual std::string get() const = 0;
};

// Potomek musí implementovat všechny čisté virtuální metody:
class CCounterInt : public CCounter {
    int m_Val, m_InitVal;
public:
    void increment() override { m_Val++; }
    // ...
};

Heterogenní (polymorfní) datové struktury

Pomocí ukazatelů na abstraktní bázovou třídu lze do jednoho kontejneru ukládat objekty různých typů (potomci), s nimiž pracujeme jednotným rozhraním:

vector<CCounter*> counters;
counters.push_back(new CCounterInt(0));
counters.push_back(new CCounterChar('A'));
for (auto* c : counters) c->increment(); // polymorfní volání

RTTI a dynamic_cast

Pokud potřebujeme zjistit skutečný typ objektu za běhu, použijeme dynamic_cast (vrátí nullptr při neshodě) nebo typeid. Dobré použití RTTI je vzácné – přílišné spoléhání na dynamic_cast signalizuje špatný návrh (mělo by stačit polymorfní volání).

⚡ Výjimky (Exceptions)

Mechanismus výjimek

• throw výraz – vygeneruje výjimku. Typ výrazu odlišuje druhy chyb.
• try { … } catch(Type id) { … } – blok try hlídá výjimky, catch je zpracovává.
• Výjimka se šíří přes všechna volání, dokud nenarazí na odpovídající catch. Přitom se volají destruktory lokálních objektů (RAII!) – proto jsou výjimky bezpečné.

int bar(int x) {
    if (x == 0) throw std::invalid_argument("x nesmí být 0");
    return 100 / x;
}

int main() {
    try {
        cout << bar(0) << endl;
    } catch (const std::invalid_argument& e) {
        cout << "Chyba: " << e.what() << endl;
    } catch (...) {
        cout << "Neznámá výjimka" << endl;
    }
}

Standardní výjimky (#include <stdexcept>)

noexcept

Metoda označená noexcept nesmí vyhazovat výjimky. Překladač může díky tomu generovat efektivnější kód. Zejména destruktory a přesouvací konstruktory by měly být noexcept.

➕ Přetěžování operátorů

Kdy přetěžovat?

• Matematické typy (zlomky, komplexní čísla, vektory, matice).
• Kontejnery – [] pro přístup k prvkům.
• I/O proudy – << a >>.
• Porovnávání – ==, < atd.

Operátor jako metoda vs. funkce

// Operátor << pro výstup (musí být funkce, ne metoda):
std::ostream& operator<<(std::ostream& out, const CRat& r) {
    return out << '(' << r.num_ << '/' << r.den_ << ')';
}

// Binární + jako friend (přístup k privátním členům):
friend CRat operator+(CRat x, CRat y) {
    return { x.num_*y.den_ + y.num_*x.den_,
             x.den_*y.den_ };
}

Spřátelené funkce (friend)

Funkce označená friend uvnitř třídy má přístup k privátním členům. De facto se stává součástí implementace třídy. Používat střídmě – narušuje zapouzdření, ale je nepostradatelná pro operátory streamů.

Uživatelské konverze

Konstruktor s jedním parametrem slouží jako konverzní konstruktor – umožňuje implicitní konverzi jiného typu na danou třídu. Slovo explicit zabraňuje implicitní konverzi (vyžaduje explicitní přetypování).

explicit CRat(int num = 0, int den = 1);
// Bez explicit: CRat r = 5; // OK
// S explicit:   CRat r = 5; // chyba, musí být CRat r(5);

Spaceship operátor <=> (C++20)

Trojcestné porovnání: vrací negativní, nulovou nebo pozitivní hodnotu. Lze ho nechat vygenerovat (= default), což automaticky generuje i ==. Dříve bylo nutné ručně implementovat všech 6 relačních operátorů.

🧩 Šablony (Templates)

Šablony funkcí

template <typename T>
T max(const T& a, const T& b) {
    return a < b ? b : a;
}
// Instanciace je automatická:
max(1, 15);      // T = int
max(1.5, 2.3);   // T = double

Šablony tříd

template <typename T>
struct Array {
    void push(T x);
    T& operator[](size_t i);
private:
    std::unique_ptr<T[]> data_;
    size_t size_ = 0, cap_ = 0;
};

Array<int>    intArr;    // pole celých čísel
Array<string> strArr;   // pole řetězců

constexpr – vyhodnocování při překladu

constexpr unsigned factorial(unsigned n) {
    return n > 1 ? n * factorial(n-1) : 1;
}
char buf[factorial(5)];  // velikost pole vypočtena při překladu

Specializace šablon

Pro konkrétní typ parametru lze poskytnout odlišnou implementaci šablony. Příklad: std::vector<bool> má specializaci ukládající bity paměťově efektivně.

📦 Abstraktní datový typ (ADT) – definice a specifikace

Formální specifikace ADT

ADT lze formálně popsat pomocí signatur (syntaxe operací) a axiomů (sémantika – ekvivalence výrazů). Příklad pro zásobník:

Signatury:
  init:          → stack
  push(_,_):     stack, elem → stack
  pop(_):        stack → stack
  top(_):        stack → elem
  empty(_):      stack → bool

Axiomy:
  empty(init)         = true
  empty(push(s,x))    = false
  top(push(s,x))      = x
  pop(push(s,x))      = s

📚 Zásobník (Stack)

Operace zásobníku

• push(x) – vloží prvek na vrchol.
• pop() – odebere a vrátí prvek z vrcholu.
• top() / peek() – přečte vrchol bez odebrání.
• empty() – test prázdnosti.

Implementace 1: Spojový seznam (jednosměrný)

Každý uzel drží hodnotu a ukazatel na následníka. Vrchol zásobníku = hlava seznamu. Push i pop jsou O(1), žádné realokace.

template <typename T>
struct Stack {
    void push(T t) {
        head_ = make_unique<Node>(move(t), move(head_));
    }
    T pop() {
        auto tmp = move(head_);
        head_ = move(tmp->next);
        return move(tmp->value);
    }
private:
    struct Node {
        unique_ptr<Node> next;
        T value;
    };
    unique_ptr<Node> head_;
};

Implementace 2: Nafukovací pole

Pole s dynamicky rostoucí kapacitou. Push na konec pole = O(1) amortizovaně (při plném poli alokujeme dvojnásobek). Pop = O(1). Výhoda: lepší cache lokalita než spojový seznam.

Použití v praxi

Zásobník volání funkcí, undo/redo, vyhodnocování výrazů, DFS průchod grafem, validace závorek.

🚃 Fronta (Queue)

Operace fronty

• enqueue(x) – vloží prvek na konec.
• dequeue() – odebere prvek ze začátku.
• empty() – test prázdnosti.

Implementace 1: Spojový seznam (obousměrný ukazatel)

Hlava = začátek fronty (odebíráme), konec = přidáváme. Potřebujeme ukazatel na konec pro O(1) enqueue.

Implementace 2: Kruhové pole (circular buffer)

Pole pevné nebo dynamické velikosti, indexované modulo. Enqueue i dequeue jsou O(1) worst-case. Při plném poli se alokuje nové (lineární čas, amortizovaně konstantní).

// Klíčový vzorec pro kruhový buffer:
at(i) = data_[(i + first_) % cap_]
// Enqueue: at(size_++) = t
// Dequeue: first_ = (first_ + 1) % cap_; size_--

Implementace 3: Lineární pole s posunem

Nevybíráme fyzicky, jen zvyšujeme offset začátku. Pokud je volný prostor před prvky větší než počet prvků, posuneme je na začátek. Amortizovaně O(1) pro obě operace.

Použití v praxi

BFS průchod grafem, plánování procesů (OS scheduler), buffery pro I/O, tiskové fronty.

📊 Pole (Array ADT)

Mapovací funkce (přístupová funkce)

Mapuje indexy na offset v paměti. Pro 1D pole: map(i) = i - l1 (pro l1 = 0 jednoduše i). Pro 2D pole (n×m, row-major uložení):

map(i, j) = i * m + j   // řádkové uložení (C/C++)
map(i, j) = j * n + i   // sloupcové uložení (Fortran)

Reprezentace multidimenzionálního pole

Operace s polem – složitosti

• Přístup k prvku: O(1) – výpočet offsetu.
• Přidání/odebrání na konci: O(1) amortizovaně (nafukovací pole).
• Přidání/odebrání uprostřed: O(n) – nutno posouvat prvky.
• Mazání bez zachování pořadí: O(1) – zaměnit mazaný prvek posledním.

Nafukovací pole (dynamic array)

Při naplnění kapacity alokujeme nové pole o dvojnásobné velikosti a zkopírujeme prvky. Amortizovaná složitost push_back je O(1) – geometrický růst zajistí, že celkové kopírování pro n vložení je O(n).

🔗 Spojový seznam (Linked List)

Typy spojových seznamů

Operace s obousměrným seznamem

• Vložení/odebrání na začátek/konec: O(1).
• Vložení/odebrání na zadané pozici (máme iterátor): O(1).
• Hledání prvku: O(n) – lineární průchod.
• Přístup k i-tému prvku: O(n) – nelze indexovat jako pole.

struct Node {
    unique_ptr<Node> next;
    T value;
    Node(T v, unique_ptr<Node>&& n)
        : value(move(v)), next(move(n)) {}
};

Srovnání s polem

🗂️ Množina (Set) a Tabulka / Slovník (Map)

Operace množiny

• insert(x), erase(x), contains(x)
• Množinové operace: sjednocení (∪), průnik (∩), podmnožina, rovnost

Přehled implementací s časovými složitostmi

V STL: std::set / std::map – vyvážený BST (červeno-černý strom). std::unordered_set / std::unordered_map – hašovací tabulka.

🌳 Binární vyhledávací strom (BST)

Základní operace BST

Vyhledávání: od kořene, porovnáváme x s hodnotou uzlu, jdeme doleva nebo doprava. O(h) kde h = hloubka stromu.

Vkládání: vyhledáme místo, kde by x byl, a přidáme nový uzel jako list. O(h).

Mazání: tři případy podle počtu synů mazaného uzlu:

• Žádný syn: uzel prostě smažeme.
• Jeden syn: nahradíme uzel jeho synem.
• Dva synové: nahradíme hodnotu uzlu maximem z levého podstromu (nebo minimem z pravého), a pak smažeme tento uzel rekurzivně.

// Implementace mazání (schematicky):
void erase_(Node::Ptr& n, T x) {
    if (!n) return;
    if (n->value != x) return erase_(n->son(x > n->value), x);
    if (!n->left || !n->right)
        n = move(n->left ? n->left : n->right);
    else  // dva synové: najdi max levého podstromu
        n->value = erase_max_(n->left);
}

In-order průchod

Levý podstrom → uzel → pravý podstrom. Prvky jsou navštíveny v seřazeném pořadí od nejmenšího. Časová složitost: O(n).

Vyváženost BST

Řešení: vyvažování – po vložení/mazání se kontroluje hloubka a stromem se provádějí rotace:

• AVL strom: rozdíl výšek levého a pravého podstromu každého uzlu je max. 1. Garantuje O(log n).
• Červeno-černý strom: barvy uzlů + invarianty zajišťují log n hloubku. Implementace v STL (std::set, std::map).
• Líné vyvažování (scapegoat): pokud syn > 70 % otce, celý podstrom přebudujeme na dokonale vyvážený. O(log n) amortizovaně.

🔑 Hašovací tabulky (Hash Tables)

Hašovací funkce

Funkce h(k, m) přiřadí klíči k číslo z intervalu 0..m-1, kde m je velikost pole. Požadavky: deterministická, rychlá, rovnoměrné rozložení hodnot.

// Celá čísla:
unsigned int hash(int k, int m) {
    return ((unsigned int)k) % m;
}

// Řetězce (DJB2 – Bernstein):
unsigned int hash(const char* s, int m) {
    unsigned int h = 5381;
    while (*s) h += (h << 5) + *s++;  // 33*h + c
    return h % m;
}

Kolize a jejich řešení

Kolize nastane, když h(k1, m) = h(k2, m) pro k1 ≠ k2. Vždy existuje, pokud počet klíčů > m (holubníkový princip).

Otevřené hašování (řetězení / separate chaining):

• Každá pozice tabulky odkazuje na spojový seznam klíčů se stejným hašem.
• Průměrná délka seznamu = n/m (load factor).
• Pro load factor ≤ 1 jsou operace O(1) průměrně.

// Struktura hašovací tabulky:
template <class Key>
class HashSet {
    int m;                    // počet slotů
    LinkList<Key>* keys;     // pole spojových seznamů
public:
    void ins(const Key& k) { keys[hash(k,m)].add(k); }
    bool incl(const Key& k) const {
        return keys[hash(k,m)].incl(k);
    }
};

Uzavřené hašování (open addressing): při kolizi hledáme jiný slot v tabulce (lineární probingem, kvadratickým, double hashing). Všechny prvky jsou v samotné tabulce.

Vztah map a set implementovaných hašováním

Mapa je množina párů (klíč, hodnota) kde porovnání ignoruje hodnotu. Implementace je identická, jen uzly nesou navíc asociovanou hodnotu.

⬆️ Prioritní fronta a binární halda

Vlastnosti binární haldy (min-heap)

• Úplný binární strom (vyplněn po hladinách zleva).
• Haldové uspořádání: každý uzel má prioritu ≤ priorita synů → minimum je vždy v kořeni.
• Hloubka = O(log n).

Uložení v poli (indexování od 1)

// Synové uzlu i jsou na indexech 2i a 2i+1
// Otec uzlu i je na indexu i/2
// Přidáváme/odebíráme vždy na konci pole

Operace haldy

• insert(x): přidej na konec, bubble_up – porovnej s otcem, pokud je menší, prohoď; opakuj. O(log n).
• extract_min(): odeber kořen, přesuň poslední prvek do kořene, bubble_down – porovnej se syny, prohoď s menším; opakuj. O(log n).
• decrease_key: sniž prioritu, pak bubble_up. O(log n).

void bubble_up(size_t i) {
    if (i == 0 || data_[i] >= data_[(i-1)/2]) return;
    swap(data_[i], data_[(i-1)/2]);
    bubble_up((i-1)/2);
}
void bubble_down(size_t i) {
    size_t l = 2*i+1;
    if (l >= size) return;
    size_t s = (l+1 < size && data_[l+1] < data_[l]) ? l+1 : l;
    if (data_[i] <= data_[s]) return;
    swap(data_[i], data_[s]);
    bubble_down(s);
}

STL implementace: std::priority_queue (max-heap), funkce std::make_heap, std::push_heap, std::pop_heap.

📚 STL kontejnery a jejich volba

C++ standardní knihovna nabízí hotové implementace všech základních ADT jako generické třídy (šablony).

Iterátory

Iterátory jsou obecné ukazatele na prvky kontejnerů – umožňují jednotné procházení bez znalosti vnitřní struktury. Typy iterátorů (od nejslabšího):

• InputIterator: čtení, posun vpřed (istream_iterator)
• OutputIterator: zápis, posun vpřed (ostream_iterator, back_inserter)
• ForwardIterator: čtení i zápis, více průchodů (forward_list)
• BidirectionalIterator: + posun vzad (list, set, map)
• RandomAccessIterator: + skok o n pozic, indexace (vector, deque)