Języki i Metody Programowania 2 (język C++)

• Wykład C++
• Strumienie C++
• STL

Wyniki będą publikowane na tej stronie.

• I termin 14.06.2019 B1 H24 14.15-16.15
  • Wyniki egzaminu I termin.
  • Możliwość oglądania prac i zgłaszania uwag podczas konsultacji

• II termin 26.06.2019 C2 429 11.00-13.00
  • Wyniki egzaminu II termin.

• III termin 6.09.2019 C2 429 16.00-18.00
  • Wyniki egzaminu III termin.
  • 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

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:

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

1. AnimalList kontener będący listą
2. 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 ==
• 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 :)

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ć (operator delete). 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;  
}

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

• Warto w pewnym momencie poznać funkcje typu 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()

• 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. 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ą.
  • Zobacz: http://courses.washington.edu/css342/zander/css332/copyeq.html

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

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:

• http://stackoverflow.com/questions/15932333/is-such-assignment-a-good-idea-in-c oraz
• http://www.gotw.ca/gotw/023.htm.

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

• 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++

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

• 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…

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:

• Jeżeli klasa V implementuje wyłącznie operator ==, to nie może być parametrem szablonów typu map<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

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

• 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 i ListElement. Pusta lista, to zerowa wartość wskaźnika (wskaźników). W konstruktorze nie tworzymy niepotrzebnego elementu.