Programozás alapjai II. (7. ea) C++

Generikus szerkezetek, template

Szeberényi Imre, Somogyi Péter BME IIT szebi@iit.bme.hu

Hol tartunk?

Mi az objektummodell haszna?

Ismétlés (alakzat)

class Pont {}; class Szin {}; class Szin;
class Alakzat {
protected: // Tartalmazott objektumok:
  Pont p0; ///< alakzat origója
  Szin sz; ///< alakzat színe
public:
  Alakzat(const Pont &p0, const Szin &sz) : p0(p0), sz(sz) {}
  //      ^ Adattagok inicializálása
  Pont getp0() const { return p0; }
  Szin getsz() const { return sz; }
  virtual void rajzol() const = 0;
  // ^ Virtuális rajzol. Leszármazottban valósul meg.
  void mozgat(const Pont &d);
  virtual ~Alakzat() {}
  // ^ Virtuális destruktor
};
class Poligon : public Alakzat {
  size_t np;
  Pont *pontok;
  // rejtetve, kivülről nem elérhető, "letiltva":
  Poligon(const Poligon &);
  Poligon &operator=(const Poligon &);
public:
  Poligon(const Pont &p0, const Szin sz) : Alakzat(p0, sz), np(1),
  // Ős inicializálása                     ^
         pontok(new Pont[np - 1]) {} // Dinamikus területet
  int getnp() const { return np; }
  Pont getcsp(size_t i) const;
  void add(const Pont &p);  //  void rajzol() { /* ... */ }
  ~Poligon() { delete[] pontok; } // Dinamikus területet
};

Lehet-e tovább általánosítani?

Elemzés: Din. tömb

TArray megvalósítás

class T {};
class TArray {
  size_t n; // tömb mérete
  T *tp;          // elemek tömbjére mutató pointer
  // privátak, így nem érhetőek el:
  TArray(const TArray &);            // másoló konstr. tiltása
  TArray &operator=(const TArray &); // tiltás
public:
  TArray(size_t n = 5) : n(n) { tp = new T[n]; }
  T &operator[](size_t i) { return tp[i]; }
  const T &operator[](size_t i) const { return tp[i]; }
  ~TArray() { delete[] tp; }
};

Mit kell változtatni?

Lehet-e általánosítani?

Típusokat és neveket le kell cserélni → Generikus adatszerkezetek:

Osztálysablon

template <typename T> // Sablon kezdete
//                 ^ Formális sablonparamétert lecseréli az akt. paraméterre
class Array { // Azonosító
  size_t n; T *tp;
public:
  Array(size_t n = 5) : n(n) { tp = new T[n]; }
  // ^ Azonosító                     ^ Formális sablonparamétert
  // ...                              lecseréli az akt. paraméterre
}; // template hatókör vége
class Valami { /* ... */ };
int main() {
  Array<int> a1, a2, a3;
  //     ^ Formális sablonparamétert lecseréli az akt. paraméterre
  Array<Valami> v1, v2, v3;
} // ^ Azonosító

Array osztály sablonja

template <typename T> // osztálysablon
class Array { // Sablonparamétertől függő nevet generál (név elem csere)
  size_t n;                        // tömb mérete
  T *tp;                           // elemek tömbjére mutató pointer
  Array(const Array &);            // másoló konstr. tiltása
  Array &operator=(const Array &); // tiltás
public:
  Array(size_t n = 5) : n(n) { tp = new T[n]; }
  T &operator[](size_t);
  const T &operator[](size_t) const;
  ~Array() { delete[] tp; }
}; // ^ Sablonparamétertől függő nevet generál (név elem csere)

Array tagfüggvényeinek sablonja

template <typename T> // tagfüggvénysablon
T &Array<T>::operator[](size_t i) {
  //     ^ A scope-hoz a név a paraméterből generálódik
  return tp[i];
}

template <class T> // tagfüggvénysablon
const T &Array<T>::operator[](size_t i) const {
  return tp[i];
}

Sablonok használata (példányosítás)

#include "generic_array.hpp" // sablonok
int main() {
// sablon példányosítása aktuális template paraméterrel:
  Array<int> ia(50), ia1(10); // int array
  Array<double> da;           // double array
  Array<const char *> ca;     // const char* array
  ia[12] = 4;
  da[2] = 4.54;
  ca[2] = "Hello Template";
  return 0;
}

Array osztály másként

template <class T, size_t s> // osztálysablon
class fixArray {
  T t[s]; // elemek tömbje
public:
  T &operator[](size_t i) {
    if (i >= s) { throw "Indexelési hiba"; }
    return t[i];
  }
  const T &operator[](size_t i) const;
};
int main() {
  fixArray<int, 10> a10; // Többször példányosodik! Növeli a kódot,
  fixArray<int, 30> a30; // ugyanakkor egyszerűsödött az osztály.
}

default paraméter is lehet

template <class T, size_t s = 10> // osztálysablon
class fixArray {
  T t[s]; // elemek tömbje
public:
  T &operator[](size_t i) {
    if (i >= s) { throw "Indexelési hiba"; }
    return t[i];
  }
  const T &operator[](size_t i) const;
};
int main() {
  fixArray<int> a10;
  fixArray<int, 30> a30;
}

Lehet-e tovább általánosítani?

Sablon specializáció (ism.)

template <typename T> T max(T a, T b) { return a < b ? b : a; }
// Teljes specializáció T::= const char* esetre
#include <cstring>
template <> inline const char *max(const char *a, const char *b) {
  return strcmp(a, b) > 0 ? a : b;
}

#include <iostream>
int main() { std::cout << max("Hello", "Adam"); }

Részleges és teljes specializáció

template <class R, class S, class T> struct A {/*…*/};
// részleges specializálás:
template <class S, class T> struct A<char, S, T> {/*…*/};
// teljes specializálás:
template <> struct A<char, char, char> {/*…*/};

Sablon specializáció (összef.)

Függvények különböző változatai: túlterhelés (overload)

Sablonok esetében a túlterhelés mellett egy újabb eszközünk is van: specializáció. Egy sablonnal megadott osztály, vagy függvény adott változatát átdefiniálhatjuk. Ilyenkor nem a sablonban megadott módon fog példányosodni.

Template paraméter

típus, konstans, függvény, sablon

template <class T1, typename T2, int i = 0>
//                             default ^
struct V {
  T1 a1;
  T2 a2;
  int x;
  V() { x = i; }
};
int main() {
  V<int, char, 4> v1;
  V<double, int> v2;
}
// paraméterként kapott típus és konstansa, ami
// csak integrális, vagy pointer típus lehet
template <typename T, T c = T()>
struct V1 {
  T val;
  V1() { val = c;}
};
V1<int, 30> v30; // v30.val <- 30;
V1<int*> v0;     // v0.val <- NULL;

Sablon, mint paraméter

template <class T> struct Pont { T x, y; };
template <class T> struct Pont3D { T x, y, z; };
template <class S, template <class T> class P = Pont>
struct Idom {
  P<S> origo; // idom origója
};
int main() {
  Idom<int> sikidom1;
  // sikidom1.origo <- Pont<int>
  Idom<double> sikidom2;
  // sikidom2.origo <- Pont<double>
  Idom<int, Pont3D> test;
  // test.origo <- Pont3D<int>
}

Függvénysablonok paraméterei

A sablonparaméterek általában levezethetők a függvényparaméterekből. Pl:

template <class T> void csere(T &p1, T &p2) {
  T tmp = p1;
  p1 = p2;
  p2 = tmp;
}
int main() {
  int x1 = 1, x2 = 2;
  csere(x1, x2);
}

Ha nem, akkor meg kell adni. Pl:

template <class T, int n> void fv(T t1[n], T t2[n]) {
  for (int i = n; i >= 0; i--) {
    t1[i] = t2[i]; // warning: Assigned value is garbage or undefined
  }
}
int main() {
  int it1[10], it2[10];
  fv<int, 10>(it1, it2);
}

Mi is a sablon?

A feldolgozás fordítási idejű

// Template metaprogram
template <int N> struct fakt {
  enum { fval = N * fakt<N - 1>::fval };
};
template <> struct fakt<0> { // Specializálás
  enum { fval = 1 };
};
#include <iostream>
int main() {
  std::cout << fakt<3>::fval << std::endl;
  // Fordítási időben 4 példány (3,2,1,0) keletkezik
  // Nehéz nyomkövetni, nagyon sok könyvtár (pl. boost) kihasználja.
}

Algoritmus módosítása

Példa: leg… elem kiválasztása

template <typename T, class S> T leg1(T a[], int n) {
  T tmp = a[0];
  for (int i = 1; i < n; ++i) {
    if (S::select(a[i], tmp)) { tmp = a[i]; }
}
  return tmp;
}

Az S sablonparaméter egy olyan osztály, melynek van egy select logikai tagfüggvénye, ami az algoritmus működését befolyásolja. Pl:

struct kisebb_int {
  static bool select(int a, int b) { return a < b; }
};
// Lehet egy sablonból generálódó osztály is
template <typename T> struct nagyobb {//szokásos nagyobb reláció
  static bool select(T a, T b) { return a > b; }
};
#include <iostream>
using namespace std;
int main() {
  int it[9] = {-5, -4, -3, -2, -1, 0, 1, 2, 3};
  double dt[5] = {.0, .1, .2, .3, 4.4};
  cout << leg1<int, kisebb_int>(it, 9) << endl;   // -5
  cout << leg1<int, nagyobb<int>>(it, 9) << endl; // 3
  cout << leg1<double, nagyobb<double>>(dt, 5);   // 4.4
}

Problémák, kérdések

Funktor

Kettő az egyben?

Mindent tudó legElem

template <typename T, typename S>
T legElem(const T a[], int n, S sel) {
  T tmp = a[0];
  for (int i = 1; i < n; ++i) {
    if (sel(a[i], tmp)) { tmp = a[i]; }
  }
  return tmp;
}

A függvény második paramétere logikai függvényként viselkedő valami, ami lehet önálló függvény, vagy funktor is.

Pl:

#include <iostream>
using namespace std;
int main() {
  cout << legElem<int,kisebbObj<int>>(it,
                                      9,
                                      kisebbObj<int>());
} //                 létre kell hozni ^

fixArray és legElem?

fixArray<int 100> fixa;
// használható igy?
legElem(fixa, 100, kisebObj<int>() );

// problémák:
template <typename T, typename S>
T legElem(const T a[], int n, S sel) {
  T tmp = a[0]; //...
}
// Elemtípus helyett adjuk át a tömböt:
template <typename T, typename S>
T legElem(const T& a, int n, S sel) {}
// Rendben, de honnan lesz elem típusunk a tmp-hez?
// 1. Adjuk át azt is.

// 2. Tegyünk be a  fixArray osztályba egy belső típust pl:
template <class T, size_t s = 10>
class fixArray {
  T t[s];
public:
  typedef T value_type; //...
};

Mindent tudó legElem

template <typename T, typename S>
T legElem(const T &a, int n, S sel) { // indexelhető tárolókhoz
  typename T::value_type tmp = a[0]; // Segítség a fordítónak
  for (int i = 1; i < n; ++i) { // van value_type belső típusa
    if (sel(a[i], tmp)) { tmp = a[i]; }
  } return tmp;
}
template <typename T, typename S>
T legElem(const T a[], int n, S sel) { // Túlterhelés
  T tmp = a[0]; // hagyományos tömbökhöz
  for (int i = 1; i < n; ++i) {
    if (sel(a[i], tmp)) { tmp = a[i]; }
  } return tmp;
}

Predikátum (összefoglalás)

Generikus példa 2

  1. Olvassunk be fájl végéig maximum 10 db valamit (pl. valós, komplex, stb. számot)!
  2. Írjuk ki!
  3. Készítsünk másolatot a tömbről!
  4. Rendezzük az egyik példányt nagyság szerint növekvően, a másikat csökkenően!
  5. Írjuk ki mindkét tömböt.

Kidolgozás

#include <iostream>

#include "fixed_size_gen_array.hpp" // fix méretű generikus
        // tömb indexelhető, másolható, értékadható
#include "generic_sort.hpp" // indexelhető típus generikus
                // rendezése
#include "generic_cmp.hpp"  // generikus hasonlító függvények

// A bemutatott megoldás bármilyen indexelhető típussal,
// így pl. az alaptípusokból létrehozott tömbökkel is működik, ha
// az elemtípus másolható, értékadható és értelmezett a
//  <, > <<, és >>  művelet.
/// Indexelhető típus elemeit kiírja egy stream-re
template <typename T> void CopyToStream(const T &t, int n, std::ostream &os) {
  for (int i = 0; i < n; ++i)
    os << t[i] << ",";
  os << std::endl;
}
/// Indexelhető típus elemeit beolvassa egy stream-ről
template <typename T>
int ReadFromStream(T &t, size_t n, std::istream &is) {
  size_t cnt = 0;
  while (cnt < n && is >> t[cnt])
    cnt++;
  return cnt;
}
int main() {
  fixArray<double, 10> be; // max. 10 elemű double tömb

  int db = ReadFromStream(be, 10, std::cin);     // beolvasunk
  CopyToStream(be, db, std::cout);               // kiírjuk
  fixArray<double, 10> masolat = be;             // másolat készül
  insertionSort(be, db, less<double>());         // növekvő rendezés
  insertionSort(masolat, db, greater<double>()); // csökkenő
  CopyToStream(be, db, std::cout);               // kiírjuk az elemeket
  CopyToStream(masolat, db, std::cout);          // kiírjuk az elemeket
}

https://git.ik.bme.hu/Prog2/eloadas_peldak/ea_06 gen_pelda2

fixed_size_gen_array.hpp

#ifndef  FIXED_SIZE_GEN_ARRAY_H
#define FIXED_SIZE_GEN_ARRAY_H
template <class T, size_t s>
class fixArray {
  T t[s];
  void chkIdx(size_t i) const { if (i >= s) { throw "Index hiba"; } }
public:
 typedef T value_type; // a példában nem használjuk
  T& operator[](size_t i) {
        chkIdx(i);   return t[i]; }
  const T& operator[](size_t i) const {
        chkIdx(i);   return t[i]; }
};
#endif

generic_sort.hpp

#ifndef  .....
template <typename T>
void swap(T& a, T& b) { T tmp = a; a = b; b = tmp; }

template <typename T, class F>
void insertionSort (T& a, int n, F cmp) {
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && cmp(a[j], a[j-1])) {
            swap(a[j], a[j-1]);
            j--;
        }
    }
}

generic_cmp.hpp

#ifndef  GENERIC_CMP_H
#define GENERIC_CMP_H
template <typename T>
struct less {
    bool operator()(const T& a, const T& b) const {
        return a < b; }
};

template <typename T>
struct greater {
    bool operator()(const T& a, const T& b) const {
        return a > b; }
};
#endif

Módosítsuk a kiírót!

Ötlet: a funktor egy objektum

// ezért tud tárolni is. Tároljuk le, a referenciaértéket!
template <typename T> class greater_than {
  T ref_value;

public:
  greater_than(const T &val) : ref_value(val) {}
  bool operator()(const T &a) const { return a > ref_value; }
};
int main() {
  greater_than<int> gt(10); // konstruktor letárolja  a 10-et
  gt(8);                    // fv. hívás op. <- false
  gt(15);                   // fv. hívás op. <- true
}

Módosított kiíró használata

int main() {
  int it[9] = {-5, -4, -3, -2, -1, 0, 1, 2, 3 };

  CopyToStream(it, 9, std::cout, greater_than<int>(-1) );
  // 0,1,2,3,
  CopyToStream(it, 9, std::cout, greater_than<int>(0) );
  // 1,2,3,
  CopyToStream(it, 9, std::cout, greater_than<int>(1) );
  // 2,3,
}

Összefoglalás