Podstawy programowania 2

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

Link do zespołu

Kod do zespołu został przekazany drogą mailową

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++ [23.04.2025/07.05.2025]
8. Wyjątki [07.05.2025]
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 czerwca B1 H24 17:30-19:30 (konsultacje wtorek 1 lipca, 15:00)
• II termin 5 lipca C2 224 14:00-16:00
• III termin 4 września C2 224 14:00 - 16:00

Kurs na platformie UPEL: https://upel.agh.edu.pl/course/view.php?id=8307

Lab xx Dirent

Będziemy odczytywać pliki z dysku i ładować informacje o nich do pamięci. Funkcje służące do iteracji po katalogu nie są przenośne (zależą od platformy i kompilatora)

Poniższy kod odczytuje zawartość katalogu

#include <dirent.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <sys/stat.h>
//#include <iomanip>
using namespace std;
 
string mode_to_string(mode_t mode) {
    const char* chrmode = "xwr";
    string result;
    for (int i = 8; i >= 0; i--) {
        result += mode & (1<< i)?chrmode[i%3]:'-';
    }
    return result;
}
 
void print_file_info(const char*path){
    struct stat fstat;
    stat(path, &fstat);
    cout << "size:" << fstat.st_size << " ";
    char buf[20];
    strftime(buf, 20, "%d-%m-%Y %H:%M:%S", localtime(&fstat.st_mtime));
    cout << "Modified at:" << buf<<" ";
    cout<< "mode: "<<mode_to_string(fstat.st_mode)<<" "<<oct<<fstat.st_mode;
 
}
 
static void test_dir1(){
    DIR *dir;
    struct dirent *entry;
    map<int,string> ftypes{
            {DT_UNKNOWN,"unknown"},
            {DT_REG,"file"},
            {DT_DIR,"dir"},
            {DT_FIFO,"pipe"},
            {DT_SOCK,"socket"},
            {DT_CHR,"chardev"},
            {DT_BLK,"blkdev"},
            {DT_LNK,"symlink"}
    };
    string dir_name="c:/";
    dir = opendir(dir_name.c_str());
 
    if(!dir)return;
    while ((entry = readdir(dir)) != NULL) {
        cout << entry->d_name << " [";
        cout<<ftypes[entry->d_type]<< " ";
        auto fpath = dir_name+"/"+entry->d_name;
        print_file_info(fpath.c_str());
        cout<<"]"<<endl;
 
    }
    closedir(dir);
}
 
 
int main(){
    test_dir1();
//    cout<<mode_to_string(0751)<<endl;
}

Czasem entry→dt_type nie jest zdefiniowane w bibliotece. Wtedy należy odczytać typ pliku ze struktury struct stat. Jest to inna wersja wcześniejszego kodu z blokami przełączanymi przez testowanie stałej preprocesora

_DIRENT_HAVE_D_TYPE
 
#include <dirent.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
 
#include <map>
#include <vector>
#include <sys/stat.h>
#include <sstream>
#include <fstream>
#include <time.h>
//#include <iomanip>
using namespace std;
 
string mode_to_string(mode_t mode) {
    const char* chrmode = "xwr";
    string result;
    for (int i = 8; i >= 0; i--) {
        result += mode & (1<< i)?chrmode[i%3]:'-';
    }
    return result;
}
 
void print_file_info(const char*path){
    struct stat fstat;
    stat(path, &fstat);
#if 1//!defined _DIRENT_HAVE_D_TYPE
    if(fstat.st_mode & S_IFREG){ // if  S_ISREG(m)
        cout<<"<file> ";
    }
    if(fstat.st_mode & S_IFDIR){  // if S_ISDIR(m)
        cout<<"<dir> ";
    }
 
#endif
    cout << "size:" << fstat.st_size << " ";
    char buf[20];
    strftime(buf, 20, "%d-%m-%Y %H:%M:%S", localtime(&fstat.st_mtime));
    cout << "Modified at:" << buf<<" ";
    cout<< "mode: "<<mode_to_string(fstat.st_mode)<<" "<<oct<<fstat.st_mode;
 
}
 
static void test_dir1(){
    DIR *dir;
    struct dirent *entry;
#if defined _DIRENT_HAVE_D_TYPE
    map<int,string> ftypes{
            {DT_UNKNOWN,"unknown"},
            {DT_REG,"file"},
            {DT_DIR,"dir"},
            {DT_FIFO,"pipe"},
            {DT_SOCK,"socket"},
            {DT_CHR,"chardev"},
            {DT_BLK,"blkdev"},
            {DT_LNK,"symlink"}
    };
#endif
    string dir_name="c:/";
    dir = opendir(dir_name.c_str());
 
    if(!dir)return;
    while ((entry = readdir(dir)) != NULL) {
        cout << entry->d_name << " [";
#if defined _DIRENT_HAVE_D_TYPE
        cout<<ftypes[entry->d_type]<< " ";
#else
    {
        auto fpath = dir_name+"/"+entry->d_name;
        struct stat fstat;
        stat(fpath.c_str(), &fstat);
        if(fstat.st_mode & S_IFREG){ // if  S_ISREG(m)
            cout<<"FILE";
        }
        if(fstat.st_mode & S_IFDIR){  // if S_ISDIR(m)
            cout<<"DIR  ";
        }
 
    }
#endif
        auto fpath = dir_name+"/"+entry->d_name;
        print_file_info(fpath.c_str());
        cout<<"]"<<endl;
 
    }
    closedir(dir);
}
 
int main(){
    test_dir1();
}

Poniższy kod odczytuje zawartość katalogu

#include <stdio.h>
#include <iostream>
#include <string>
#include <sys/stat.h>
#include <time.h>
#include <io.h>
using namespace std;
 
string mode_to_string(unsigned int mode) {
    const char* chrmode = "xwr";
    string result;
    for (int i = 8; i >= 0; i--) {
        result += mode & (1 << i) ? chrmode[i % 3] : '-';
    }
    return result;
}
 
void print_file_info(const char* path) {
    struct stat fstat;
    stat(path, &fstat);
    cout << "size:" << fstat.st_size << " ";
    char buf[20];
    struct tm newtime;
    localtime_s(&newtime, &fstat.st_mtime);
    strftime(buf, 20, "%d-%m-%Y %H:%M:%S",&newtime );
    cout << "Modified at:" << buf << " ";
    cout << "mode: " << mode_to_string(fstat.st_mode) << " " << oct << fstat.st_mode;
 
}
 
 
 
static void test_dir1() {
    string dir_name = "c:/";
    string find_dir_name = dir_name+"*";
 
    struct _finddata_t fileinfo;
    long handle;
 
    handle = _findfirst(find_dir_name.c_str(), &fileinfo);
    if (handle < 0)return;
    printf((fileinfo.attrib & _A_SUBDIR ? "%s <DIR> " : "%s "),
           fileinfo.name);
    auto fpath = dir_name + "/" + fileinfo.name;
    print_file_info(fpath.c_str());
    cout << endl;
 
    while (_findnext(handle, &fileinfo) == 0) {
        printf((fileinfo.attrib & _A_SUBDIR ? "%s <DIR> " : "%s "),
               fileinfo.name);
        auto fpath = dir_name + "/" + fileinfo.name;
        print_file_info(fpath.c_str());
        cout << endl;
    }
    _findclose(handle);
}
 
 
int main() {
    test_dir1();
    //    cout<<mode_to_string(0751)<<endl;
}

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