====== Podstawy programowania 2 ======

===== Wykłady =====

Wykłady odbywają się w środy o 19:00 na platformie MS Teams.

[[https://teams.microsoft.com/l/team/19%3AVB_hmfafz560jilREju7ucJGcBPFfGcOUJcotJ6lNKQ1%40thread.tacv2/conversations?groupId=feffb47e-61c4-4e7f-a59c-8e7da40d7929&tenantId=80b1033f-21e0-4a82-bbc0-f05fdccd3bc8|Link do zespołu]]

Kod do zespołu zostanie przekazany staroście


  -{{ ::01-isi-cpp-intro-wsk.pdf | Wprowadzenie. Wskaźniki - przypomnienie}} [>>28.02.2024]
  -{{ ::02-isi-cpp-ref-skladow-klas.pdf | Referencje, składowe klas. Wprowadzenie do standardowej biblioteki}} [06.03.2024, 13.03.2024]
  -{{ :03-isi-cpp-kompozycja-dziedziczenie.pdf |Kompozycja i dziedziczenie}} [>>20.03.2024]
  -{{ ::04-isi-cpp-funkcje-wirtualne.pdf |Funkcje wirtualne (polimorfizm)}} []
  -{{ ::05-isi-cpp-konstruktory-destruktory.pdf |Konstruktory, destruktory}} [05.04.2023]
  -{{ ::06-isi-cpp-przeciazanie-fun-op.pdf |Przeciążanie funkcji i operatorów}} [12.04.2023, 26.04.2023]
  -{{ ::07-isi-cpp-cast-rtti.pdf |Operatory rzutowania w C++}} [26.04.2023]
  -{{ ::08-isi-cpp-exceptions.pdf| Wyjątki}} [10.05.2023]
  -{{ ::09-isi-cpp-kontenery.pdf  | Kontenery i iteratory}} [10.05.2023(wektor) + ]
  -{{ ::10-isi-cpp-przenoszenie.pdf | Semantyka przenoszenia}} [%30.05.2022]
  -{{ ::11-isi-cpp-szablony.pdf | Wielokrotne użycie, szablony}} [%06.06.2022]
  -{{ ::12-isi-cpp-stl.pdf | Standardowa biblioteka. Kontenery, algorytmy, wyrażenia lambda}} [>> 07.06.2021,14.06.2021]


===== Egzamin =====

  * I termin   10.07.2023 15:30-17:30 sala H24 w B1
  * II termin  16.07.2023 14:00-16:00 sala C2 224
  * III termin 05.09.2023,  12:00-14:00 C2 431

Podczas egzaminu:
* można korzystać z dowolnych materiałów w formie fizycznej (podręczników, notatek, itp.)
* nie można wymieniać się materiałami, podawać notatek sąsiadom, itp.
* nie można korzystać z telefonów

Proszę przynieść własne kartki formatu A4, np. 3 na odpowiedzi oraz 3 na brudnopis i 2 długopisy.   
==== Uwagi 2023 ====

  *Nie trzeba pisać 
<code>
trg.a=towary[i].a;
trg.b=towary[i].b;
trg.c=towary[i].c;
trg.d=towary[i].d;
</code>

Wystarczy ''trg=towary[i]''
==== Uwagi ====

=== Uwaga 1 ===
Jeżeli tematem było napisanie szablonów klas typu ''Set<T>'' lub ''Wielozbiór<T>'' z zastrzeżeniami dotyczącymi dostępnych operatorów dla klasy będącej parameterem szablonu, to zapewne nie można było użyć ''std::set<T>'' lub ''std::map<T>''.

=== Uwaga 2 ===

Szablony ''unordered_set'' lub ''unordered_map'' działają na klasach "haszowalnych", tzn. takich dla których da się obliczyć wartość indeksu w tablicy na podstawie zawartości. 

Proszę spróbować skompilować:

<code cpp>

class A{
public:
    A(int _v):v(_v){}
    int v;
    bool operator==(const A&a)const{
        return v==a.v;
    }
};

int main(){
    std::unordered_set<A> set;
    set.insert(A(1));
    std::cout<<(set.find(A(1))!=set.end())<<std::endl;
}

</code>

Dla nietypowej własnej klasy należy dostarczyć własny obiekt funkcyjny do obliczania "hasza" (czyli położenia w tablicy)...

<code cpp>
class A{
public:
    A(int _v):v(_v){}
    int v;
    bool operator==(const A&a)const{
        return v==a.v;
    }
};

class MyHashForA{
public:
    size_t operator()(const A&a)const{
        return std::hash<int>{}(a.v);
    }
};
int main(){
    std::unordered_set<A,MyHashForA> set;
    set.insert(A(1));
    std::cout<<(set.find(A(1))!=set.end())<<std::endl;
}

</code>



=== Uwaga 3 ===
Funkcja nie może zwracać wskaźnika po dereferencji do obiektu, dla którego pamięć przydzielono na stercie. 
Jak zwolnić tę pamięć? Memory leak...
 
<code cpp>

class A{
public:
    int v;
};

A bardzo_zle_napisana_funkcja(){
    A*ptr = new A();
    ptr->v=10;
    printf("ptr=%p\n",ptr);
    return *ptr;
}

int main(){
    A a1 = bardzo_zle_napisana_funkcja();
    printf("&a1=%p\n",&a1);
    A a2;
    a2=bardzo_zle_napisana_funkcja();
    printf("&a2=%p\n",&a2);
    // jak zwolnić ptr?
}

// Wynik
ptr=0x80004add0
&a1=0xffffcc3c
ptr=0x80004ae40
&a2=0xffffcc38
</code>
==== Planowane zadania ====

  * **Bez STL** Podana zostanie nazwa klasy, ogólny typ implementacji i metody/funkcje do zaimplementowania. Należy zadeklarować klasę wraz z metodami oraz podać implementacje metod. Nie używamy biblioteki standardowej. Student podejmuje decyzje o tym:
     * jak nazywają się atrybuty
     * jakie atrybuty będą potrzebne
     * czy implementować dodatkowe metody (prywatne, chronione) takie jak free(), copy() lub move()
  * **Użyj STL** Podana zostanie nazwa klasy , ogólny typ implementacji i metody/funkcje. Z reguły do składowania danych będzie użyty kontener standardowej biblioteki. Analogicznie, student podejmuje decyzję o szczegółach implementacji, w tym nazwach i typach atrybutów oraz metodach pomocniczych.
  * **Co się wypisze i dlaczego** Podany zostanie kod zawierajacy deklaracje klas, obiektów (globalnych) i lokalnych w funkcji main. Podczas wykonania poszczególne instrukcje będą odpowiadały za wypisywanie tekstów na ekranie. Odpowiadając na pytanie zdalnie można wprowadzić kod do edytora i zaobserwować wynik - chociaż nie wiadomo, czy to się czasowo opłaca. Dlatego szczególny nacisk będzie położony na **dlaczego**. Typowe elementy do rozważenia:
    * wywołanie funkcji wirtualnych w konstruktorach i destruktorach
    * obecność wirtualnych/niewirtualnych destruktorów
    * wyjątki w konstruktorach oraz zwalnianie stosu podczas obsługi wyjątków
  * **Zadanie praktyczne** Niewielki program typu odczyt ze standardowego wejścia i pisanie na standardowe wyjście. Można użyć standardowej biblioteki. Szacowany na 15 minut.  
==== Zasady oceny ====
  *Kod w komentarzu nie będzie sprawdzany
  *W przypadku wpisania dwóch wersji (np. tej samej metody) będzie brana pod uwagę pierwsza z nich

==== Za co będą odliczane punkty ====

** Bez STL **
  * Za użycie kontenerów STL
  * Za własne implementacje funkcji z <string.h> (strlen, strcpy, strcat, itp.)
  * Za nadmiarowe alokacje pamięci, np. aby przedłużyć tablicę wskazywana przez start:
     * tworzona jest tablica tmp o rozmiarze takim, jak start
     * zawartość start jest kopiowana do tmp
     * zawartość start jest usuwana
     * następuje alokacja pamięci start = new T[nowa długość]
     * zawartość tmp kopiowana jest do start
     * tmp jest usuwana
  * Za użycie VLA
  * Za przedłużanie wektora o jedno miejsce przy dodawaniu elementów zamiast przedłużania go o większą liczbę elementów
  * Za szukanie końca listy, zamiast użycia wskaźnika na koniec listy -- dodanie elementu ma złożoność O(n) zamiast O(1)
  * Za użycie/implementację funkcji typu: 'zwróć i-ty element listy' -- iteracja ma złożoność O(n^2) zamiast O(n)
    
 ** Użyj STL **
  * Za umieszczanie w zbiorze ''set<T>'' elementów, które nie mogą być w nim umieszczone z powodu braku możliwości ich porównywania
  * Za iterację po zbiorze ''set<T>'', aby sprawdzić czy zawiera element - O(n) zamiast O(log n)
  * Za niezwalnianie pamięci, jeżeli kontener zawiera wskaźniki do obiektów, dla których zaalokowano pamięć na stercie
===== Laboratoria, grupy 2a i 2b =====

:!: Proszę zatwierdzać test. Jest na to 10 minut po upływie czasu


==== Laboratorium 11 ====

sizeof(text) ma wartość 8 (na platformie 64-bitowej). Długość tekstu obliczamy za pomocą strlen()

<code cpp>
TextListElement::TextListElement(const char *txt) {
    value = new char[sizeof(txt)];
    strcpy(value, txt);
    next = 0;
    prev = 0;
}

</code>
==== Lab 10 Dirent ====

  * get_path() to sklejenie parent->get_path separatora i name. Używając parent->name przeskanujemy ''c:/'', ''c:/user'' ale nie zjedziemy do ''c:/user/kasia'' bo nasza ściezka będzie miała postać ''user/kasia''
  * Pamiętamy o zabezpieczeniu operatora przypisania za pomocą &other != this

<code cpp>
Directory&Directory::operator=(const Directory&other){
    if(&other!=this){
        free();
        copy(other);
    }
    return *this;
}
</code>

  * musimy opróżnić wektor, bo zostaną //duchy// ;-) usuniętych obiektów
<code cpp>
void Directory::free(){
    
     for (auto e:entries)delete e;
     entries.clear();
}
</code>

  * Wskaźniki do parent kopiownaych obiektów muszą należeć do nowej hierarchii. To jest niuans, ale ważny ze względu na spójność. 

<code cpp>
void Directory::copy(const Directory&other){
    this->name = other.name;
    // NIE: this->parent = other.parent;
    this->parent = nullptr; // Obiekt nardrzędny ustawi wskaźnik w instrukcji (2) 
    
    //(1) kopiowanie
    for(auto e:other.entries){
       // entries.push_back( kopia e)
    }
    // (2) 
    for(auto e:entries){
        e->parent=this;
    }
}
</code>

=== Downcasting? ===

Poniższe rozwiązanie jest poprawne, ale dyskusyjne... Nieporzebnie stosowane jest rzutowanie w dół hierarchii. Klasa u szczytu hierarchii musiałaby znać wszystkie klasy potomne.

<code cpp>
Dirent *Dirent::find(const char *name) {
    if (is_dir()) {
        for (auto element : dynamic_cast<Directory *>(this)->entries) {
            if (element->name == name) {
                return element;
            } else if (element->is_dir()) {
                if (element->find(name)) {
                    return element->find(name);
                }
            }


        }


    }
}
</code>

Zamiast tego (jeżeli decydujemy się na wprowadzenie do interfejsu klasy bazowej):

<code cpp>

// zadeklarowane jako virtual 
Dirent *Dirent::find(const char *_name){
  if (name==_name ) return this;
  return nullptr;
}


Dirent *Directory::find(const char *_name) {
  if (name==_name ) return this;
  // lub:
  //auto e = Dirent::find(_name);
  //if(e) return e;
  
  for (auto element : entries) {
       auto e = e->find(_name);
       if(e)return e;     
  }
  return nullptr;//0
}


</code>

Po co downcasting w przypadku funkcji wirtualnych?

<code cpp>
    for (auto& e:entries) {
        if(e->is_dir()) dynamic_cast<Directory*>(e)->list(os, indent);
        if(e->is_file()) dynamic_cast<File*>(e)->list(os, indent);
    }
</code>


==== Lab 9 - String ====
  * Zawsze zadaj sobie następujące pytania:
    * Czy jest miejsce na 0 na końcu?
    * Czy dopisano 0 na końcu
    * Czy przy sklejaniu dwóch tekstów a i b jest pojemność jest wystarczająca, czyli >= strlen(a)+strlen(b)+1. Jeżeli dopuszczamy zerowe wskaźniki to: ''capacity > size()+strlen(_txt)'' lub  ''capacity > size()+other.size()''
  * Funkcje biblioteczne, np.: ''strlen()'', nie działają dla zerowych wskaźników. [[https://stackoverflow.com/questions/5796103/strlen-not-checking-for-null|Dyskusja]]  
  * Używamy ''strcat()'' i ''strcpy()''. Te funkcje przynajmniej nie zapomną o zerze na końcu!
  * Nie powtarzamy kodu funkcji bibliotecznych, bo szkoda na to czasu - zwłaszcza podczas egzaminu
  * Porównujemy zawartość, a nie adresy (które na ogół są zawsze różne).

<code cpp>
bool String::operator==(const char*_txt)const{
    if(_txt == this->txt) return true; // BŁĄD
    return false;
}

</code>

  * Nie mieszamy malloc i free [[http://home.agh.edu.pl/~pszwed/wiki/lib/exe/fetch.php?media=08-imperatywne-jezyk-c-dynamiczna-alokacja-pamieci.pdf|strona 10]]
  * Implementując ''operator='' pamiętamy o ''if(&other!=this)'' - za to są odliczane punkty na egzaminie
  * VLA nie należą do standardu C++, patrz: [[http://home.agh.edu.pl/~pszwed/wiki/lib/exe/fetch.php?media=05-imperatywne-jezyk-c-deklaracje-typy.pdf|VLA]] oraz [[http://home.agh.edu.pl/~pszwed/wiki/lib/exe/fetch.php?media=08-imperatywne-jezyk-c-dynamiczna-alokacja-pamieci.pdf|dynamiczna alokacja  pamięci, strona 18]]. Zajrzyj na [[https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard|Stack overflow]]. Nie stosujemy VLA zamiast alokacji pamięci, po to aby finalnie zaalokować pamięć.
  * Jeżeli mamy operator inplace, np. +=, to nie powtarzamy jego kodu, szybciej (a także poprawnie, jeżeli += jest dobrze zaimplementowany) będzie:
<code cpp>
String operator+(Arg arg){
  String ret(*this);
  ret += arg;
  return ret;
}
</code>

==== Lab 7 Relacja ===

  * iteracja po domain nie wystarcza. Czy ta relacja jest rzeczywiście zwrotna $\{(1,2),(1,1)\}$ 
  * przy tego typu implementacjach należało skleic domain i range, nawet w najprostszy spsób (oczywiście można uzyć ''set_union'' lub ''insert(other.begin(),other.end())''):

<code cpp>
    auto domain  = get_domain();
    auto range = get_range();
    set<int> all(domain);
    for(auto e:range)all.insert(e);
</code>

  *iteracja jak poniżej jest bez sensu... Naprawdę musimy sprawdzać, czy i-ty element tablicy jest w tablicy? 
<code cpp>
for(int i=0;i<pairs.size();i++){
   if(has_pair(pairs[i].x,pairs[i].y)...
} 
</code>

  *preferowane są rozwiązania proste i czytelne, na przykład

<code cpp>
bool relation::is_antisymmetric()const{
    for(auto&e:pairs){
        if(e.x!=e.y && has_pair(e.y,e.x))return false;
    }
    return true;
}

</code>

  * one ułatwiają ewentualną zmianę struktur danych. Proszę wypróbować
<code cpp>
class relation{
public:
    class pair{
    public:
        int x;
        int y;
        bool operator<(const pair&other)const;
        pair(int _x, int _y):x(_x),y(_y){}
    };
public:
#if defined USE_VECTOR
    vector<pair> pairs;
#endif
#if defined USE_SET
    set<pair> pairs;
#endif
    ... itd
</code> 

dwie zmiany:

<code cpp>
bool relation::has_pair(int x,int y)const{
#if defined USE_VECTOR
    for(int i=0;i<pairs.size();i++){
        if(pairs[i].x==x && pairs[i].y==y)return true;
    }
    return false;
#endif
#if defined USE_SET
    auto it = pairs.find(pair(x,y));
    return it!=pairs.end();
#endif

void relation::add(int x,int y){
#if defined USE_VECTOR
    if(!has_pair(x,y))pairs.emplace_back(x,y);
#endif
#if defined USE_SET
    pairs.insert(pair(x,y));
#endif
}

</code>

** Przy zmianie struktur danych żadna inna funkcja nie wymagała modyfikacji **

==== Lab 5/6 Kretowisko ===

- [[lab_kretowisko_ii|Kretowisko II]]
==== Lab 4 ====
Po to napisaliśmy metodę Student::write, aby jej użyć, a nie pisać jak poniżej:

<code cpp>
void StudentList::write(ostream&os)const{
    for(int i=0;i<count;i++){
        os<<tablica[i].indeks<<'\t'<<tablica[i].imie<<'\t'<<tablica[i].nazwisko<<'\t';
        os<<tablica[i].skreslony<<'\t'<<tablica[i].grupa<<'\t';
    }
}

</code>


==== Lab 2,3 ====

=== Styl ===

  * Proszę nie pisać w stylu:
<code cpp>
if(ok1){
   if(ok2){
      if(ok3){
          // Tu dobry ciąg instrukcji...
      }else{
         
      }
   }else{
   
   }
}else {

}
</code>

... nikt nie sprawdzi tych warunków else

  * ** Metoda nie powinna wypisywać wiadomości na cout (chyba, że taka jest jej specyfikacja) ** Podczas testów możemy wypisywać informacje na cout 

=== Algorytmy ===

U prawie wszystkich ''linspace()'' wygeneruje wyjątek dla n=1

=== Funkcje ===

  * do liczb zmiennoprzecinkowych używamy:  fabs()
  * liczb double nie porównujemy obliczając ich różnicę


==== Lab 1 ====

**Logika zabezpieczeń**

<code cpp>
void Fibo1::init(int _n)
{
    if(_n<=0)tab=0;
    n = _n;
    tab = new int[n];
}

void Fibo1::destroy()
{
    delete [] tab; 
}

    ArithmeticSequence(int _n, double _r, double _first)
    {
        
        if(_n<=0)return; // USTAW n=0, tab=0 
        n=_n;
        r=_r;
        first=_first;
        tab = new double[n];
    }

void Fibo1::init(int n) {
    if(n <= 0) {
        tab = 0;
    }
    tab = new int[n];
}

void Fibo1::init(int _n)
{
    n = _n; 
    int* tab = new int[_n]; 
    if(n <= 0){ tab = NULL; }
}



Fibo::~Fibo(){
    if(n>0) delete []tab; // TO JEST POPRAWNE, ale proponuję raczej idiom if(tab) delete []tab;
}


</code>

**Class::member służy do czegoś innego...**

<code cpp>
    for (int _i = 0; _i < ArithmeticSequence::n; _i++)
    {
        cout << ArithmeticSequence::arr[_i] << endl;
    }

void Fibo1::fill()
{
    tab[0]=1,tab[1]=1; // a jak tab==0 lub n=1?
    for(int i=2;i<n;i++) tab[i]=tab[i-1]+tab[i-2];
}

</code>

[[https://stackoverflow.com/questions/34614869/using-scope-operator-to-access-non-static-member-variables]]


**Bez średnika!** 

''#define N  10;''

**To nie jest stała, to jest VLA** 

Variable Length Arrays nie należą do standardu C++. Zamiast tego należy używać ''vector<int>''

<code cpp>
void fibo1(){
int n;
int tab[n];

</code>