Wyniki będą publikowane na tej stronie.
Egzamin ma formę pisemną (piszemy kod na kartce). Czas trwania: 90 min.
Pytania
Najczęściej jest to 4-5 zadań podzielonych na podpunkty. Typowe zadanie, to zaimplementuj klasę, która…. A podpunkty to, na przykład: zadeklaruj, napisz konstruktor kopiujący, operator przypisania, metodę, która…, itd. W sumie należy napisać kilkanaście niewielkich funkcji w ciągu 90 min.
Co można?
Podczas egzaminu można korzystać z własnych materiałów (notatki, wydruki, książki)
Natomiast nie można: - korzystać z laptopów, tabletów i telefonów - wypożyczać materiały sąsiadom
Uwagai
Zadanie 1. Zera z zdania pierwszego oznaczają, że użyto nieodpowiednich struktur danych - wektora zamiast listy. Analogiczne zadanie z wektorem było na egzaminie z roku 2016. W tym roku zostało przerobione na listę i właśnie lista była oczekiwana.
Zadanie 2.
V nie może być umieszczone w map bo nie ma operatora <
Zadanie 2.
Relacja nie jest mapą (bo mapa to zależność funkcjonalna). A ma tylko operator ==
więc nie może być umieszczone w zbiorze lub mapie. Ale pair<A,A> może być porównywane za pomocą ==
W punktach d,e,f, najlepiej było skorzystać z hasPair()
Zadanie 1. Należy rozróżnić 3 klasy:
Animal
i potomne - dane składowane w kontenerze. W hierarchii powinn być zadeklarowana wirtualna funkcja Animal*clone()
, np:Animal*Dog::clone()const{ return new Dog(*this); }
AnimalList
kontener będący listąListElement
– element listy, często ukryty typ, w tym przypadku powinien np. być zadeklarowany tak class ListElement{ public: Animal*data; ListElement*next; };
Wtedy kopiowanie w konstruktorze kopiujący i operatorze przypisania powinno wyglądać następująco:
void copy(const AnimalList&o){ for(ListElement* i=o.head;i!=0;i=i->next){ add(i->data->clone()); } }
Zadanie 2.
Jak na razie nie da się zaalokować pamięci w stylu int*ptr=new int[row][col];
Zazwyczaj funkcje zapisu i odczytu są komplementarne
zapisz(os){ os<<rows<<" "<<cols<<endl; os<< wszystkie elementy } wczytaj(is){ //zwolnij pamięć obiektu, np. delete []tab, rows=0, cols=0 //wczytaj rows, cols is>>rows>>cols; //zaalokuj pamięć tab=new V[rows*cols] wczytaj elementy is>>wszystkie elementy }
Jeżeli można/należy używać STL zawsze należy preferować string
w stosunku do char*
. Bo przekazany wskaźnik może wskazywać coś, co się zmieni poza kontenerem.
Dla klasy string do porównania należy użyć operatora ==
, a strcmp()
stosować do tablic znaków.
Podobnie, zawsze można bezpośrednio podstawić:
const char*ptr="Ala ma kota"; string s; s=ptr;
Nie trzeba konwertować wcześniej ptr
na string
.
Aby utworzyć map<X,Y>
lub set<X>
klasa X
musi implementować operatory <
oraz ==
. Dlatego czegoś takiego, jak Word
w grupie A nie da się umieścić w takich kontenerach bez zdefiniowania tych operatorów.
Jeżeli graf jest nieskierowany (zad 1 w grupie A) to najlepiej było zastosować coś w rodzaju
vector<Word> words; vector<Meaning> menaings;
Jeżeli pole jednoznacznie identyfikuje obiekt, jak email
w Person
(zdanie 1 grupa B), to użycie mapy przyspiesza wyszukiwanie obiektów: map<string,Person> osoby
.
Ale deklaracja typu
map<Person,list<Person>> followers;
jest niewłaściwa, bo
Person
nie może być kluczem, obiekty nieporównywalne, brak operatora <
i ==
Znacznie lepiej (przypisanie email
→ zbiór emaili
:
map<string,set<string>> followers;
Składnia:
PointGPS gps = PointGPS(x,y,t); auto gps = PointGPS(x,y,t);
jest dziwna… To jest wywołanie konstruktora i konstruktora kopiującego. Chyba zaczerpnięta z Pythona? Bardziej konwencjonalnie:
PointGPS gps(x,y,t);
Kojarzy się to z modnym w tym roku emplace_back
vector<PointGPS> trace; //zamiast PointGPS r(1.1,2.2,12.5); trace.push_back(r); // można użyć trace.emplace_back(1.1,2.2,12.5); // ... i głównie do tego ma służyć (zamiast konstrukcji i przypisania, konstrukcja w miejscu
Pętle for-range (foreach) bardzo często zwierały błędy, które starałem się ignorować. Proszę uruchomić poniższy fragment kodu
vector<int> k; k.resize(10,1); for(int i=0;i<k.size();i++){ printf("k[%d]=%d (%p)\n",i,k[i],&k[i]); } for(auto i:k){ printf("i=%d (%p)\n",i,&i); }
Wynik
k[0]=1 (00842490) k[1]=1 (00842494) k[2]=1 (00842498) k[3]=1 (0084249c) k[4]=1 (008424a0) k[5]=1 (008424a4) k[6]=1 (008424a8) k[7]=1 (008424ac) k[8]=1 (008424b0) k[9]=1 (008424b4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4) i=1 (0028fee4)
Czy dostrzegacie Państwo różnicę? Zmienna i
jest zmienną lokalną:
Sprawdźmy:
vector<int> k; k.resize(10,1); // zmieniamy wartość i for(auto i:k){ i=2; } // co jest w kontenerze? for(auto i:k){ cout<<i<<endl; }
Wynik
1 1 1 1 1 1 1 1 1 1
Dla pocieszenia dodam, że w języku Java analogiczny kod zadziała zgodnie z Państwa oczekiwaniami :)
Grupa B, zadanie 1
Macierz, która ma r wierszy i c kolumn przechowuje elementy wewnątrz tablicy (dla której pamięć jest przydzielona na stercie) o rozmiarze r*c.
W odróżnieniu od zadania z poprzednich lat, dane miały być przechowywane wewnątrz tablicy, a nie zbioru tablic odpowiadających wierszom.
Grupa B, zadanie 3
Grupa C, zadanie 1
Grupa C, zadanie 2
map<string,string>
nie nada terminowi wielu znaczeńGrupa C, zadanie 3
new
) i je usuwać (operator delete
). Także w destruktorzeUwagi ogólne
vector <A> aaa; aaa.push_back(*(new A())); //źle!!!
A foo(){ A*a = new A(); ... return *a; //źle!!! }
static
zadeklarowanego wewnątrz funkcji, bo:A& foo(){ static A a; //źle!!! a.~A(); ... // zrób coś z a return a; }
Grupa C, zadanie 3
Przy implementacji operatora=
i operatora+
należało sprawdzić typ obiektu, np. if(typeid(*tab[i])==typeid(C)))
i utworzyć jego kopię na podstawie typu A*a = new C(*(C*)tab[i])
Nikt tego nie zrobił, ale w grupie A zad 3 było to zrealizowane.
Operator + vs. +=
Proszę porównać x = y + z
i x+=z
dla zmiennych typu int
. Operator + nie modyfikuje argumentów, powinien więc zwrócić obiekt, a nie referencję. Także nie *this
strlen()
, strcpy()
lub strcat()
. W szczególności poniższy kod nie zadziała…class A{ char tab[256]; }; ... A a; a.tab="Ala ma kota"; // strcpy()
sizeof
stosunkowo rzadko zwraca długość tekstuvoid foo(const char*t){ // tablica badtab będzie miała długość 4 lub 8 char*badtab=new char[sizeof(t)]; // zapewne chodziło o char*goodtab=new char[strlen(t)+1]; }
operator=()
zwalnia pamięć obiektuoperator=()
zakłada, że obiekt jest w spójnym stanie, np. pole head
wskazuje pierwszy element listy (do usunięcia) lub ma wartość 0 (NULL)
. Natomiast konstruktor kopiujący musi założyć, że head
ma wartość nieokreśloną.Praktycznie - mało kto zrobił to w pełni poprawnie…
Przykład
#include <iostream> #include <sstream> #include <string> #include <list> using namespace std; class X{ public: X(const string&_a,const string&_b):a(_a),b(_b){} string a; string b; }; // lista czegoś class LX : public list<X>{ }; ostream&operator<<(ostream&os,const LX&lx){ os<<"#begin"<<endl; // wybieramy symbol oznaczający początek for(list<X>::const_iterator it=lx.begin();it!=lx.end();++it){ os<<"\t"<<it->a<<"\t"<<it->b<<endl; } os<<"#end"<<endl; // wybieramy symbol oznaczający koniec return os; } istream&operator>>(istream&is,LX&lx){ string a,b; is>>a; if(a!="#begin"){return is;} // opcjonalnie is.setstate(ios::failbit) lub wyjątek for(;;){ is>>a; if(!is)break; // bo plik mógł się skończyć if(a=="#end")break; is>>b; lx.push_back(X(a,b)); } return is; } int main(){ string input = "#begin Jan Kowalski Anna Dymna #end"; istringstream is(input); LX x; is>>x; cout<<x; return 0; }
Wynik:
#begin Jan Kowalski Anna Dymna #end
Realizacje operatora przypisania w stylu
T& T::operator=( const T& other ) { if( this != &other) { this->~T(); // evil new (this) T( other ); // evil } return *this; }
były uznawane, chociaż na wykładzie była zalecana inna implementacja. To nie jest dobra praktyka programowania, ale ilustracja działania nowego (niezbyt potrzebnego) mechanizmu.
Proszę zajerzeć do:
Nawiasem mówiąc, zamieszczony tam przykład poprawnego kodu też jest zły…
T::T( const T& other ) { do_copy( other ); } T& T::operator=( const T& other ) { // brakuje &other !=this // brakuje free() do_copy( other ); return *this; }
map
bo wierzchołki są nieporównywalne (brak operatora <
).unordered_map
ze standardu C++11template <class V, class W> class Graph { public: class Edge{public: V v1; V v2; W weight;}; list< Edge > edges; void addEdge(V v1,V v2, W w){ for(typename list<Edge>::iterator it = edges.begin();it!=edges.end();++it){ if(it->v1==v1 && it->v2==v2){ it->weight=w; return; } } Edge e; e.v1=v1; e.v2=v2; e.weight=w; edges.push_back(e); } };
test…
int main(){ Graph<int,double> g; g.addEdge(1,2,10.5); g.addEdge(2,3,12.37); g.addEdge(3,4,0.28); for(list<Graph<int,double>::Edge >::iterator it = g.edges.begin();it!=g.edges.end();++it){ cout<<it->v1<<"--"<<it->weight<<"-->"<<it->v2<<endl; } //system("pause"); }
lub
int main(){ Graph<string,double> g; g.addEdge("Krakow","Myslenice",28.7); g.addEdge("Myslenice","Nowy Targ",30.4); g.addEdge("Nowy Targ","Zakopane",32.5); for(list<Graph<string,double>::Edge >::iterator it = g.edges.begin();it!=g.edges.end();++it){ cout<<it->v1<<"--"<<it->weight<<"-->"<<it->v2<<endl; } //system("pause"); }
typename
ze względu na wersję g++
ElementListy*nowy = &ElementListy(txt);
Implementacja listy zawsze wymaga alokacji pamięci za pomoca malloc() w C lub operatora new w C++
const
(bo aktualny element jest np. modyfikowany w trakcie iteracji)class Lista{ public: ElementListy*pierwszy; ElementListy*aktualny; };
Chciałbym zwrócić uwagę, że jeśli mamy wskaźnik char*txt
to długość tekstu stosunkowo rzadko jest równa sizeof(txt)/sizeof(char)
. Po co zresztą obliczać wartość, która na platformie 32 bitowej wynosi 4, a 64 bitowej 8?
Powtórzę treści z wykładu:
V
implementuje wyłącznie operator ==
, to nie może być parametrem szablonów typu map<V, X>
, set<V>
, itp. Proszę sprawdzić dlaczego.Kontener k; k.add(new A()); k.add(new B()) Kontener k2=k; // tu należy sporządzić kopie wszystkich obiektów - A i B
Kontenery k
, k2
jako właściciele obiektów - usuwają je i sporządzają kopie tak, aby modyfikacja obiektu w kontenerze k2
nie wpływała na obiekt w kontenerze k
!
Kontener k; for(int i=0;i<100;i++){ char buf[256]; sprintf(buf,"Element numer %d",i); k.add(buf); } // tu kontener k powienien zawierać RÓŻNE tekst Kontener 2=k; // k2 powinien zawierać KOPIE tekstów w k // wydrukuj zawartość k2 i k
W zdaniach 2 należało w kontenerze umieszczać wskaźniki do do obiektów należących do hierarchii, a później kopiować określając typ obiektu (typeid, dynamic_cast
, własna implementacja RTTI) Każde rozwiązanie typu:
class Bazowa{ Potomna1 m1; Potomna2 m2; Potomna3 m3; }; List<Bazowa> kontener;
Jest w opozycji do filozofii języków obiektowych, polimorfizmu, itd… Tak byłoby w języku C:
struct Bazowa{ union { struct Potomna1 m1; struct Potomna2 m2; struct Potomna3 m3; }object; int object_type; };
for(Iterator i(...);i.good();i.next()){ zrób coś z i.get(); }
Uwaga: jeżeli tylko good()
zwraca true
, to możemy get()
wywołać nieskończenie wiele razy i za każdym razem funkcja powinna zwrócić tę samą wartość! I oczywiście nie powinna przesuwać kursora.
List
i ListElement
. Pusta lista, to zerowa wartość wskaźnika (wskaźników). W konstruktorze nie tworzymy niepotrzebnego elementu.