Table of Contents
Podstawy programowania 2
Wykłady
Wykłady odbywają się w środy o 18:30 na platformie MS Teams.
Kod do zespołu został przekazany drogą mailową
- Wprowadzenie. Wskaźniki - przypomnienie [»28.02.2024]
- Referencje, składowe klas. Wprowadzenie do standardowej biblioteki [06.03.2024, 13.03.2024]
- Kompozycja i dziedziczenie [»20.03.2024]
- Konstruktory, destruktory [05.04.2023]
- Przeciążanie funkcji i operatorów [12.04.2023, 26.04.2023]
- Operatory rzutowania w C++ [23.04.2025/07.05.2025]
- Wyjątki [07.05.2025]
- Kontenery i iteratory [10.05.2023(wektor) + ]
- Semantyka przenoszenia [%30.05.2022]
- Wielokrotne użycie, szablony [%06.06.2022]
- Standardowa biblioteka. Kontenery, algorytmy, wyrażenia lambda [» 07.06.2021,14.06.2021]
Laboratoria (grupa 1)
Kurs na platformie UPEL: https://upel.agh.edu.pl/course/view.php?id=8307
Sprawdź działanie kodu
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)
Linux/Cygwin - CLion, CodeBlocks
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; }
Linux/Cygwin/Mingw - inna wersja
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(); }
Windows - VisualStudio
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; }
Egzamin
- 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.
Planowane zadania
- 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.
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
Uwagi 2023
- 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]
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ć:
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; }
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…
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
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()
TextListElement::TextListElement(const char *txt) { value = new char[sizeof(txt)]; strcpy(value, txt); next = 0; prev = 0; }
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 doc:/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; } }
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.
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); }
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)
lubcapacity > size()+other.size()
- Funkcje biblioteczne, np.:
strlen()
, nie działają dla zerowych wskaźników. Dyskusja - Używamy
strcat()
istrcpy()
. 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 oif(&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; }
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
lubinsert(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
Lab 5/6 Kretowisko
Lab 4
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'; } }
Lab 2,3
Styl
- 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
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ń
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]; }
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];