Podstawy programowania 2

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

Link do zespołu

Kod do zespołu zostanie przekazany staroście

1. Wprowadzenie. Wskaźniki - przypomnienie [»28.02.2024]
2. Referencje, składowe klas. Wprowadzenie do standardowej biblioteki [06.03.2024, 13.03.2024]
3. Kompozycja i dziedziczenie [»20.03.2024]
4. Funkcje wirtualne (polimorfizm) []
5. Konstruktory, destruktory [05.04.2023]
6. Przeciążanie funkcji i operatorów [12.04.2023, 26.04.2023]
7. Operatory rzutowania w C++ [26.04.2023]
8. Wyjątki [10.05.2023]
9. Kontenery i iteratory [10.05.2023(wektor) + ]
10. Semantyka przenoszenia [%30.05.2022]
11. Wielokrotne użycie, szablony [%06.06.2022]
12. Standardowa biblioteka. Kontenery, algorytmy, wyrażenia lambda [» 07.06.2021,14.06.2021]

• I termin 26.06.2024 B1 H24 16:30 – 18:30
• II termin 03.07.2024 B1 H24 16:30 – 18:30
• III termin 05.09.2024 C2 224 13:00 – 15:00

Podczas egzaminu:

• można korzystać z dowolnych materiałów w formie fizycznej (podręczników, notatek, wydruków, 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.

• Bez STL 30pkt 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 30pkt 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.

• Zadanie praktyczne 15pkt Niewielki program typu odczyt ze standardowego wejścia i pisanie na standardowe wyjście. Można użyć standardowej biblioteki. Szacowany na 15 minut.

• 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

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

• Nie trzeba pisać

trg.a=towary[i].a;
trg.b=towary[i].b;
trg.c=towary[i].c;
trg.d=towary[i].d;

Wystarczy trg=towary[i]

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>.

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ć:

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;
}

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

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;
}

Funkcja nie może zwracać wskaźnika po dereferencji do obiektu, dla którego pamięć przydzielono na stercie. Jak zwolnić tę pamięć? Memory leak…

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

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

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

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

• 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

Directory&Directory::operator=(const Directory&other){
    if(&other!=this){
        free();
        copy(other);
    }
    return *this;
}

• musimy opróżnić wektor, bo zostaną duchy usuniętych obiektów

void Directory::free(){
 
     for (auto e:entries)delete e;
     entries.clear();
}

• 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ść.

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;
    }
}

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.

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);
                }
            }
 
 
        }
 
 
    }
}

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

// 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
}

Po co downcasting w przypadku funkcji wirtualnych?

    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);
    }

• 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. 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).

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

• Nie mieszamy malloc i free 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: VLA oraz dynamiczna alokacja pamięci, strona 18. Zajrzyj na 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:

String operator+(Arg arg){
  String ret(*this);
  ret += arg;
  return ret;
}

• 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())):

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

• iteracja jak poniżej jest bez sensu… Naprawdę musimy sprawdzać, czy i-ty element tablicy jest w tablicy?

for(int i=0;i<pairs.size();i++){
   if(has_pair(pairs[i].x,pairs[i].y)...
} 

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

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

• one ułatwiają ewentualną zmianę struktur danych. Proszę wypróbować

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

dwie zmiany:

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
}

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

- Kretowisko II

Po to napisaliśmy metodę Student::write, aby jej użyć, a nie pisać jak poniżej:

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';
    }
}

• Proszę nie pisać w stylu:

if(ok1){
   if(ok2){
      if(ok3){
          // Tu dobry ciąg instrukcji...
      }else{
 
      }
   }else{
 
   }
}else {
 
}

… 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

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

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

Logika zabezpieczeń

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;
}

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

    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];
}

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>

void fibo1(){
int n;
int tab[n];