This is an old revision of the document!
Table of Contents
Języki i Metody Programowania 2 (język C++)
Wykłady
Egzamin
Wyniki będą publikowane na stronie.
- I termin 26.06.2017 (poniedziałek ) B1 H24 12:30-14:30
- Uwaga - możliwość oglądania prac i zgłaszania uwag w piątek 30.06.2017 od 12.30-14.30.
- II termin 30.06.2017 (piątek) B2 H24 15.00-17.00
- Możliwość oglądania prac i zgłaszania uwag podczas konsultacji
- III termin 11.09.2016 (?), C2 429, 12.00-14.00
- Możliwość oglądania prac i zgłaszania uwag podczas konsultacji
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
- Proszę starać się pisać czytelnie
- Proszę przygotować sobie odpowiednią liczbę kartek (najlepiej A4) i wziąć 2 długopisy
- Poprawne odpowiedzi na zadania zazwyczaj są krótkie, nie należy zużywać całej strony na funkcję, która dodaje element do listy
- Zadania można wpisywać w dowolnej kolejności
- Tematy prac oddajemy z zadaniami, stanowią rodzaj okładki dla Państwa prac
Omówienie pytań z egzaminu
2017
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==
- po co składować tyle danych? Person możne zawierać dużow więcej atrybutów (np. zdjęcie).
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ą:
- jej modyfikacja nie będzie miała wpływu na zawartość kontenera
- nie wolno zwracać jej adresu!
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 :)
2016
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
- Jeśli współczynniki przechowywane są w wektorze, to wektor sam się nie powiększa. Trzeba dodać zera pomiędzy elementami, wykonać resize, itp.
- Jeśli coś zapisujemy i czytamy, to w tym samym formacie. Wynik zapisu powinien być możliwy do odczytania
Grupa C, zadanie 1
- Nie należy mylić elementu składowego struktur danych (elementu listy, węzła grafu, itp) z przechowywanymi danymi.
- Kontener usuwa dane, a więc usuwa obiekty, do których ma wskaźniki
- Należało skopiować żaby, koty, itp. a nie kopiować wskaźniki (ani też tworzyć obiekty abstrakcyjnej klasy Animal)
- Operator przypisania i konstruktor kopiujący to nie to samo. Jeśli nabraliście Państwo takiego przekonania, to jest błędne.
Grupa C, zadanie 2
map<string,string>
nie nada terminowi wielu znaczeń
Grupa C, zadanie 3
- Należało tworzyć wiersze (operator
new
) i je usuwać (operatordelete
). Także w destruktorze
Uwagi ogólne
- Dodawanie do kontenera obiektów w taki sposób jest błędne, bo prowadzi do wycieku pamięci (kontener sporządza kopię, a argument funkcji pozostaje nieusunięty)
vector <A> aaa; aaa.push_back(*(new A())); //źle!!!
- Podobnie zwracanie wartości (zwracana wartość jest kopiowana do obiektu na zewnątrz, pamięci na stercie nikt nie zwolni)
A foo(){ A*a = new A(); ... return *a; //źle!!! }
- Nie zwracamy referencji do obiektu
static
zadeklarowanego wewnątrz funkcji, bo:- może być wywołana równocześnie przez inny wątek
- w innym fragmencie kodu przechowamy referencję lub wskaźnik i zdziwimy się, że się zmienił wskazywany obiekt
A& foo(){ static A a; //źle!!! a.~A(); ... // zrób coś z a return a; }
2015
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
2014
- Warto w pewnym momencie poznać funkcje typu
strlen()
,strcpy()
lubstrcat()
. W szczególności poniższy kod nie zadziała…
class A{ char tab[256]; }; ... A a; a.tab="Ala ma kota"; // strcpy()
- Operator
sizeof
stosunkowo rzadko zwraca długość tekstu
void 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]; }
- Iterator dziedziczący po kontenerze jest zaprzeczeniem idei iteratora.
- Nie jest akceptowana implementacja konstruktora kopiującego polegająca na wywołaniu operatora przypisania, bo na przykład:
- dla klas zarządzających pamięcią – poprawnie zaimplementowany
operator=()
zwalnia pamięć obiektu operator=()
zakłada, że obiekt jest w spójnym stanie, np. polehead
wskazuje pierwszy element listy (do usunięcia) lub ma wartość0 (NULL)
. Natomiast konstruktor kopiujący musi założyć, żehead
ma wartość nieokreśloną.
2013
zapis i odczyt listy czegoś
Praktycznie - mało kto zrobił to w pełni poprawnie…
- wypisywane atrybuty powinny być oddzielane separatorami, np. białymi znakami, średnikami
- w jakiś sposób trzeba oznaczyć koniec listy lub liczbę elementów (dla wektora z grupy B najlepiej liczbę elementów)
- Wektor: jeśli używamy liczby elementów - wpierw wypisujemy ile ich jest, potem dane. Czytając:
- czytamy liczbę elementów (size)
- alokujemy tablicę
- czytamy dane i dodajemy do tablicy (kontenera)
- czytając listę - zazwyczaj nie czytamy jednego elementu !!!
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
placement new
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; }
graf
- Wystarczy przechowywać trójki opisujące krawędzie (pierwszy wierzchołek,waga,drugi wierzchołek).
- Nie można używać
map
bo wierzchołki są nieporównywalne (brak operatora<
). - Można użyć
unordered_map
ze standardu C++11 - Odwzorowanie typu wierzchołek → lista następników jest bardziej kłopotliwe w utrzymaniu spójności.
template <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++
Lista
- Zastanawiam się w jakim praktycznym zadaniu wykorzystaliście Państwo kod postaci:
ElementListy*nowy = &ElementListy(txt);
Implementacja listy zawsze wymaga alokacji pamięci za pomoca malloc() w C lub operatora new w C++
- Deklaracja aktualnego elementu jest to antywzorzec deklaracji klasy. Jeżeli kontener przechowuje “aktualny” element to:
- na ogół nie da się zaimplementować metod
const
(bo aktualny element jest np. modyfikowany w trakcie iteracji) - funkcje mogą wywoływać niezamierzone efekty uboczne
- Własnie ze względu na takie naiwne implementacje wprowadzono iteratory
class Lista{ public: ElementListy*pierwszy; ElementListy*aktualny; };
wektor (grupa A)
- Zazwyczaj wektor powiększa się o pewną liczbę elementów na raz. Prawie wszyscy przy dodawaniu nowego elementu powiększali tablicę o jedno miejsce. Jest to antywzorzec implementacji wektora. Odpowiedzi zostały zaliczone (mimo niespójności z konstruktorem ustalającym wstępny rozmiar zostawiającym puste miejsca), ponieważ funkcje realizowały założony interfejs…
strlen
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?
2012
Powtórzę treści z wykładu:
- Jeżeli klasa
V
implementuje wyłącznieoperator ==
, to nie może być parametrem szablonów typumap<V, X>
,set<V>
, itp. Proszę sprawdzić dlaczego.
- Konstruktora kopującego nie implementujemy poprzez wywołanie operatora przypisania bo…
- Jeśli kontener jest właścicielem obiektów to prawdopodobnie jest on używany następująco:
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
!
- Jeżeli kontener zawiera teksty i zarządza nimi, to powinien zadziałać następujący fragment kodu:
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
2011
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; };
2008
- Zbiór, relacja, funkcja z wykorzystaniem kontenera STL. Zbiór zawiera unikalne elementy - nie mogą się powtarzać, relacja pary elementów (key, value), pary nie powinny się powtarzać, funkcja - w kontenerze nie mogą wystąpić niejednoznaczne odwzorowania, czyli (key,value1) i (key, value2), value1!=value2.
- Iterator. Iterator służy najczęściej do iteracji po zawartości kontenera. Ale bardziej ogólnie – jest klasą o pewnym interfejsie pasującym do pętli for, która pozwala na sekwencyjny dostęp do ciągu wartości.
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.
- Kontener STL i wskaźniki do obiektów, dla których pamięć jest przydzielona na stercie. Konstruktor kopiujący, operator przypisania, destruktor itp. Oprócz manipulacji za pomocą funkcji STL konieczne jest zarządzanie pamięcią.
- Hierarchia klas i dostęp do RTTI lub polimorfizm (wypisz nazwę klasy mając wskaźnik do klasy bazowej, utwórz kopię obiektu na stercie)
- Operatory. Mają typową postać (const, referencje) oraz semantykę - np.: operator + nie modyfikuje zawartości argumentów, natomiast += modyfikuje pierwszy argument.
- Operator [] zwykle zwraca referencję i testuje zakresy indeksu, często wyrzuca wyjątek.
- Użycie referencji. Nie zwracamy referencji do obiektu lokalnego. Dlaczego? Nie zwracamy referencji do obiektu zadeklarowanego jako static, bo powtórne wykonanie funkcji modyfikuje obiekt dając nieprzewidziane efekty uboczne.
- Obsługa wyjątków, wyjątki w konstruktorach
- Co się wypisze (czas życia obiektów i ich składowych, kiedy wołane są konstruktory, destruktory i funkcje wirtualne w konstruktorach i destruktorach, także wyjątki). Testując tego typu programy należy pamiętać, że uruchomienie przykładu w IDE czasem może nie wypisać wszystkiego, bo czasem środowisko zintegrowane zamknie konsolę zanim pojawią się wszystkie teksty wypisywane w destruktorach obiektów globalnych. Ale uruchomienie test.exe > plik daje już właściwe rezultaty.
- Proste szablony kontenerów i funkcji. Jeśli szablon jest parametryzowany typem T, to niekoniecznie wartość 0 znaczy cokolwiek dla typu T.
- Rozszerzanie tablicy elementów (jak w kontenerze string, vector). Rozszerzając tablicę wystarczy wykonać tylko jedną alokację pamięci!
- Lista. Ten kontener wymaga implementacji dwóch klas/struktur danych:
List
iListElement
. Pusta lista, to zerowa wartość wskaźnika (wskaźników). W konstruktorze nie tworzymy niepotrzebnego elementu.