• Chcemy mieć ATD,

• W C czy Pascalu nie jest to możliwe,

• Dziedziczenie zdaje się oferować rozwiązanie,

• Przykład - stos elementów dowolnego typu.

Projektując abstrakcyjny typ danych chcemy to zrobić tak, by można było do niego wstawiać obiekty dowolnego innego typu. W Pascalu ani w C nie było to możliwe. Spójrzmy jak można by osiągnąć taki efekt korzystając z dziedziczenia.

Załóżmy, że chcemy zdefiniować abstrakcyjny stos. Elementami tego stosu będą mogły być obiekty klas pochodnych po klasie EltStosu.

class EltStosu{
 // Podklasy tej klasy będą elementami stosu.
 virtual ~EltStosu(){};
};

// ------------
//   Klasa Stos
// ------------

class Stos{
 // Możliwie najprostsza implementacja stosu
 private:			// Nie przewiduje dziedziczenia
  EltStosu** tab;    // Tablica wskaźników do elementów stosu
  unsigned size;  // Rozmiar tablicy *tab
  unsigned top;    // Indeks pierwszego wolnego miejsca na stosie

 public:
  Stos(unsigned = 1024);
  ~Stos();

  void push(EltStosu);
  EltStosu pop();
  int empty();
};

// --------------------------
//   Implementacja klasy Stos
// --------------------------

Stos::Stos(unsigned s){
 size = s;
 top = 0;
 tab = new EltStosu*[size];
}

Stos::~Stos(){
 for (unsigned i=0; i<top; i++)
     delete tab[i];
 delete[] tab;
}

void Stos::push(EltStosu elt){
 if (top < size){
  tab[top] = new EltStosu(elt);
  top++;
 }
 else
   blad("przepełnienie stosu");
}

EltStosu Stos::pop(){
 if (!top)
  blad("brak elementów na stosie");

// Ze względu na konieczność usuwania wykonuje się tu
// dwukrotne kopiowanie elementu stosu
  EltStosu res(*tab[--top]);
  delete tab[top];
  return res;
}

int Stos::empty(){
  return top == 0;
}

Muszę zdefiniować podklasę reprezentującą wkładane elementy:

class Liczba: public EltStosu{
 private:
  int i;
 public:
  Liczba(int);
};

Liczba::Liczba(int k): i(k) {}

A oto przykładowy program główny:

int main(){
  Stos s;
  int i;

  s.push(Liczba(3)); // Nie przejdzie bez jawnej konwersji
  s.push(Liczba(5));
  cout << "\nStan stosu: " << s.empty();
  while (!s.empty()){
   i = s.pop();
   cout << "\n:" << i;
  }
  return 0;
}

Niestety tak zapisany program zawiera sporo błędów:

• Nagłówek push wymaga zmiany na

       void Stos::push(EltStosu& elt)
     
  

• Uniknięcie kopiowania w implementacji push wymaga zmian także w klasach EltStosu i Liczba na

      class EltStosu{
       public:
        virtual EltStosu* kopia() = 0;
        virtual ~EltStosu(){};
      };
  
      EltStosu* Liczba::kopia(){
       return new Liczba(i);
      }
  
      void Stos::push(EltStosu& elt){
       if (top < size){
        tab[top] = elt.kopia();
        top++;
       }
       else
        blad("przepełnienie stosu");
      }
     
  

• Operacja push ma argument przekazywany przez wartość - jest to wprawdzie poprawne językowo, ale spowoduje że na stosie będą kopie jedynie fragmentów obiektów Liczba i w dodatku tych nieciekawych fragmentów, bo pochodzących z klasy EltStosu. Można temu prosto zaradzić deklarując nagłówek push następująco:

  void Stos::push(EltStosu& elt)
  		
  

• Zyskujemy przy okazji jedno kopiowanie mniej.

• Nadal operacja push jest zła, bo w niej wywołujemy konstruktor kopiujący z klasy EltStosu (który skopiuje tylko tę nieciekawą część wkładanego obiektu). Żeby temu zapobiec definiujemy w klasie EltStosu metodę czysto wirtualną kopia, dającą wskaźnik do kopii oryginalnego obiektu:

  class EltStosu{
   public:
    virtual EltStosu* kopia() = 0;
    virtual ~EltStosu(){};
  };
          
  

  Trzeba jeszcze tę metodę przedefiniować w klasie Liczba:

  EltStosu* Liczba::kopia(){
   return new Liczba(i);
  }
          
  

• Treść push jest teraz taka:

  void Stos::push(EltStosu& elt){
   if (top < size){
    tab[top] = elt.kopia();
    top++;
   }
   else
    blad("przepełnienie stosu");
  }
    
  

• Metoda pop też jest zła: wynik jest typu EltStosu, więc skopiuje się tylko ten nieciekawy fragment. Zmieńmy więc typ jej wyniku na wskaźnik do EltStosu, wymaga to też zmian w treści:

  EltStosu* Stos::pop(){
   if (!top)
    blad("brak elementów na stosie");
  
   return tab[--top];
  }
           
  

• Musimy jeszcze zmienić treść programu głównego.

  int main(){
   Stos s;
   int i;
   s.push(Liczba(3)); // Nie przejdzie bez jawnej konwersji
   s.push(Liczba(5));
   cout << "\nStan stosu: " << s.empty();
   while (!s.empty()){
    i = ((Liczba*)s.pop())->i;
    cout << "\n:" << i;
   }
  }
     
  

Podsumujmy wady tego rozwiązania:

• Wady:

  • wkładając muszę używać konwersji to_co_chcę_włożyć -> podklasa_EltStosu,

  • muszę zdefiniować podklasę EltStosu,

  • muszę w niej zdefiniować konstruktor i operację kopia.

• Poważne wady:

  • użytkownik musi pamiętać o usuwaniu pamięci po pobranych obiektach,

  • użytkownik musi dokonywać rzutowań typu przy pobieraniu (a to jest nie tylko niewygodne, ale przede wszystkim niebezpieczne).

• Zalety:

  • można naraz trzymać na stosie elementy różnych typów, byleby były podtypami EltStosu. Trzeba tylko umieć potem je z tego stosu zdjąć (tzn. wiedzieć co się zdjęło).

Można też zdefiniować wyspecjalizowaną podklasę stosu, ale lepsze efekty da zdefiniowanie wyspecjalizowanego stosu zawierającego powyższy stos ogólny jako element. Wymaga to jednak definiowania nowej klasy. Potrzebujemy zatem innego narzędzia umożliwiającego parametryzowanie struktur danych. Tym narzędziem są szablony.

• Szablon klasy - matryca klas

• Składnia (template, typename, class)

• Parametry (typy, wartości proste)

Szablon klasy specyfikuje jak można konstruować poszczególne klasy (podobnie jak klasa specyfikuje jak można konstruować poszczególne obiekty). Deklarację szablonu poprzedzamy słowem template, po którym w nawiasach kątowych podajemy parametry szablonu. Parametry szablonu zwykle są typami. Parametr szablonu będący typem deklarujemy używając słowa class (typename) a potem nazwy parametru (to nie oznacza, że ten typ musi być klasą). W deklaracji klasy możemy używać tak zadeklarowanych parametrów (tam gdzie potrzebujemy typów).

Oto przykład deklaracji szablonu:

template <class T>
class Stos{
 // Możliwie najprostsza implementacja stosu
 protected:
    T** tab;       // Tablica wskaźników do elementów stosu
    unsigned size; // Rozmiar tablicy *tab
    unsigned top;  // Indeks pierwszego wolnego miejsca na stosie

 public:
    Stos(unsigned = 10);
    ~Stos();

    void push(T&);
    T pop();
    int empty();
};
 

Deklarując metody dla tego szablonu musimy je poprzedzać informacją, że są szablonami metod:

template <class T>
Stos<T>::Stos(unsigned s){
 size = s;
 top = 0;
 tab = new T*[size];
}

template <class T>
Stos<T>::~Stos(){
 for (unsigned i=0; i<top; i++)
  delete tab[i];
 delete[] tab;
}

template <class T>
void Stos<T>::push(T& elt){
 if (top < size){
  tab[top] = new T(elt);
  top++;
 }
 else
  blad("przepełnienie stosu");
}

template <class T>
T Stos<T>::pop(){
 if (!top)
  blad("brak elementów na stosie");

 T res(*tab[--top]);    // Ze względu na konieczność usuwania są
 delete tab[top];    // dwie operacje kopiowania w pop().
 return res;
}

template <class T>
int Stos<T>::empty(){
  return top == 0;
}

• Składnia użycia szablonu klasy

• Przykład

  int main(){
   Stos<int> s;
   int i;
   s.push(3);
   s.push(5);
   cout << "\nStan stosu: " << s.empty();
   while (!s.empty()){
    i = s.pop();
    cout << "\n:" << i;
   }
  }
     
  

Użycie szablonu polega na zapisaniu jego nazwy wraz z odpowiednimi parametrami (ujętymi w nawiasy kątowe). Takie użycie szablonu może wystąpić wszędzie tam gdzie może wystąpić typ. Parametrami aktualnymi szablonu odpowiadającymi parametrom formalnym określającym typ mogą być dowolne typy (niekoniecznie klasy).

• Można zadeklarować nowy typ będący ukonkretnionym szablonem:

      typedef Stos<int> StosInt;
      
  

• Można użyć szablonu jako klasy bazowej:

      class Stos_specjalny: public Stos<int> { /* ... */ }
      
  

  (podklasa może być zwykłą klasą bądź znów szablonem).

• Parametr szablonu może także być zwykłym parametrem typu całkowitego, wyliczeniowego lub wskaźnikowego

        template<class T, int i> class A {};
      
  

• Może też być szablonem.

       template<template<class T> class U> class A { };
      
  

Uwaga: Mechanizm szablonów jest realizowany w podobny sposób do rozwijania makropoleceń, to znaczy, że kompilator przy każdym użyciu szablonu z nowym para metrem generuje dla tego nowego parametru nową klasę. Wynika stąd, że kompilator nie musi przeprowadzać (i nie przeprowadza) pełnej analizy poprawności szablonu w momencie napotkania jego deklaracji, robi to dopiero podczas generowania konkretnych klas. Dzięki temu mechanizm szablonów jest dużo bardziej elastyczny, można zdefiniować szablon sparametryzowany typem T, wymagający by dla typu T był zdefiniowany operator +. Ponieważ nie wszystkie typy mają operator +, taki szablon w ogólności nie jest poprawny. Nic nie stoi jednak na przeszkodzie, by używać tego szablonu dla tych typów, dla których operator + jest zdefiniowany. Szablon można sparametryzować kilkoma parametrami. Jak już wspominaliśmy, parametry nie muszą być typami. Oto przykład deklaracji szablonu stosu o zadanej podczas kompilacji liczbie elementów, przykład definicji metody i przykład użycia:

int main(){
 Stos<int,100> s;
 Stos< float, 10> s2;
 // ...
 s.push(3);
 // ...
}

• Oprócz szablonów klas można także tworzyć szablony funkcji.

• Oto deklaracja uniwersalnej funkcji sortującej:

  template<class T>
  void sortuj(T tab[], unsigned n)
  {  /* Treść tej funkcji */  }
  

W ten sposób zdefiniowaliśmy nieskończoną rodzinę funkcji sortujących (oczywiście kompilator będzie generował elementy tej rodziny tylko w miarę potrzeby). Teraz można sortować dowolne tablice.

• Przy wywoływaniu funkcji zdefiniowanej przez szablon nie podaje się jawnie argumentów szablonu, generuje je kompilator,

• Oto przykład:

  // ...
  int t1[100];
  Zespolone t2[20];
  sortuj(t1, 100);   // wywołanie z T równym int
  sortuj(t2, 20);     // wywołanie z T równym Zespolona
  

• Każdy argument szablonu funkcji musi wystąpić jako typ argumentu w szablonie funkcji.

• W bibliotece standardowej jest uniwersalna funkcja sortująca sort.

• Pełne jej omówienie wymaga znajomości STLa (nasze końcowe wykłady).

• Uproszczona wersja opisu: argumenty są parą wskaźników.

• Uwaga: zakres sortowany nie obejmuje elementu zadanego drugim wskaźnikiem.

• Jako trzeci parametr można podać funkcję porównującą elementy, wpp. użyty będzie operator <.

• To sortowanie nie jest stabilne (ale jest też stable_sort).

• Oczekiwany czas to O⁢n⁢l⁢g⁢n, pesymistyczny nie gorszy niż O⁢n2, zależnie od implementacji.

Oczywiście potrzeba sortowania tablicy dowolnych elementów jest tak powszechna, że biblioteka standardowa zawiera stosowne narzędzie. Najpopularniejsze z nich to sort. Powyżej wymieniono najważniejsze cechy tej funkcji, a teraz przypatrzmy się przykładom zastosowania.

const int n = 10;
int tab[n];
// ...
ini(tab, tab+n);   // Treść w wykładzie
pokaż(tab, tab+n); // Treść w wykładzie
sort(tab, tab+n);
pokaż(tab, tab+n);
// ...
 

Tu sort zostało wywołane dla fragmentu tablicy tab zadanego indeksami (w tym przypadku tym fragmentem jest cała tablica tab). Zwróćmy uwagę, że elementu o adresie tab+n nie ma w tablicy. Jest to zgodne z podanym wcześniej opisem znaczenia parametrów funkcji sort.

Oto przykładowa implementacja pomocniczych funkcji użytych w przedstawionym przykładzie.

void ini(int* start, int* stop){
  for(int* p=start; p<stop; p++)
    *p = rand() % (stop-start);
}

void pokaż(int* start, int* stop){
  for(int* p=start; p<stop; p++)
    cout << (*p) << ", ";
  cout << endl;
}

Przyjrzyjmy się jeszcze na koniec trudniejszemu przypadkowi. Co zrobić wtedy, gdy tablica zawiera elementy nie dające się porównać operatorem <? Na przykład gdy chcemy posortować liczby zespolone według ich modułu. Albo gdy mamy tablicę nie liczb całkowitych, lecz wskaźników do liczb całkowitych. Porównywanie elementów takiej tablicy - czyli wskaźników - jest składniowo dozwolone w C++, ale oczywiście nie ma sensu w tej sytuacji. Chcemy sortować tablicę według wartości liczb, na które wskazują wskaźniki.

Rozwiązanie polega na podaniu trzeciego parametru, funkcji realizującej operację porównywania. Uwaga: ta funkcja koniecznie musi realizować operację “ostro mniejsze” (<). Podanie zamiast tego funkcji realizującej operację “mniejsze bądź równe” (<A=) może powodować na przykład błędy wykonania programu.

const int n = 10;
int* tab[n];

bool por_wsk(int* p1, int* p2){
  return *p1 < *p2; // Nie <= !!!
}
// ...
ini_wsk(tab, tab+n);   // Treść w wykładzie
pokaż_wsk(tab, tab+n); // Treść w wykładzie
sort(tab, tab+n, por_wsk);
pokaż_wsk(tab, tab+n);
// ...
 

Zwróćmy uwagę, że trzeci parametr sort nie ma postaci por_wsk() lecz por_wsk. Przekazujemy funkcję, a nie jej wartość.

Oto przykładowa implementacja pomocniczych funkcji użytych w przedstawionym przykładzie.

void ini_wsk(int** start, int** stop){
  for(int** p=start; p<stop; p++)
    *p = new int(rand() % (stop-start));
}

void pokaż_wsk(int** start, int** stop){
  for(int** p=start; p<stop; p++)
    cout << (**p) << ", ";
  cout << endl;
}