Table of Contents

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

Wykłady

Egzamin

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

Omówienie pytań z egzaminu

2018

Grupa A

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 <

Grupa B

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()

Grupa C

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
 
 
}

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

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 :)

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

Grupa C, zadanie 1

Grupa C, zadanie 2

Grupa C, zadanie 3

Uwagi ogólne 

  vector <A> aaa;
  aaa.push_back(*(new A()));  //źle!!!  
A foo(){
  A*a = new A();
  ...
  return *a;  //źle!!!
}
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

class A{
   char tab[256];
};
 
...
 
A a;
a.tab="Ala ma kota"; // strcpy()
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];
}

2013

zapis i odczyt listy czegoś

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

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

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

ElementListy*nowy = &ElementListy(txt);

Implementacja listy zawsze wymaga alokacji pamięci za pomoca malloc() w C lub operatora new w C++ 

class Lista{
public:
  ElementListy*pierwszy;
  ElementListy*aktualny;
};

wektor (grupa A)

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: 

  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

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

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.