Szablony klas

Szablony można specyfikować również na poziomie klas, wtedy cała klasa staje się przepisem (szablonem) na powstawanie nowych klas specjalistycznych.

Przyglądnijmy się następującej implementacji uproszczonego vectora:

#include <cstddef>
#include <initializer_list>
#include <algorithm>
 
template<class T>
class MyVector {
 public:
  MyVector(size_t intial_capacity=16);
  MyVector(const std::initializer_list<T> &elements);
  ~MyVector();
  MyVector(const MyVector<T> &to_copy);
  MyVector(MyVector<T> &&to_move);
  void operator=(const MyVector<T> &to_copy);
  void operator=(MyVector<T> &&to_move);
 
 
  const T &operator[](size_t index) const;
  T &operator[](size_t index);
  size_t Size() const;
  void Reserve(size_t size);
 
  void PushBack(T i);
 private:
  void Swap(MyVector<T> &&other);
  void Copy(const MyVector<T> &other);
  void Destroy();
 
 
  T *elements_;
  size_t size_;
  size_t capacity_;
};
 
template<class T>
MyVector<T>::MyVector(size_t intial_capacity) {
  Reserve(intial_capacity);
}
 
template<class T>
MyVector<T>::MyVector(const std::initializer_list<T> &elements) {
  Reserve(elements.size());
  int i =0;
  for (const auto &el : elements) {
    elements_[i++] = el;
  }
  size_ = elements.size();
}
 
template<class T>
MyVector<T>::~MyVector() {
  Destroy();
}
 
template<class T>
MyVector<T>::MyVector(const MyVector<T> &to_copy) {
  Copy(to_copy);
}
 
template<class T>
MyVector<T>::MyVector(MyVector<T> &&to_move) {
  elements_= nullptr;
  Swap(std::move(to_move));
}
 
template<class T>
void MyVector<T>::operator=(const MyVector<T> &to_copy) {
  if (this != &to_copy) {
    Destroy();
    Copy(to_copy);
  }
}
 
template<class T>
void MyVector<T>::operator=(MyVector<T> &&to_move) {
  if (this != &to_move) {
    Destroy();
    Swap(std::move(to_move));
  }
}
 
template<class T>
const T &MyVector<T>::operator[](size_t index) const {
  return elements_[index];
}
 
template<class T>
T &MyVector<T>::operator[](size_t index) {
  return elements_[index];
}
 
template<class T>
size_t MyVector<T>::Size() const {
  return size_;
}
 
template<class T>
void MyVector<T>::Swap(MyVector<T> &&other) {
  std::swap(size_,other.size_);
  std::swap(capacity_,other.capacity_);
  std::swap(elements_,other.elements_);
}
 
template<class T>
void MyVector<T>::Destroy() {
  size_ = 0;
  capacity_ = 0;
  delete [] elements_;
  elements_ = nullptr;
}
 
template<class T>
void MyVector<T>::Reserve(size_t size) {
  elements_ = new T[size];
  capacity_ = size;
  size_ = 0;
}
 
template<class T>
void MyVector<T>::Copy(const MyVector<T> &other) {
  Reserve(other.size_);
  size_ = other.size_;
  for(int i=0; i<other.size_; ++i) {
    elements_[i] = other.elements_[i];
  }
}
 
template<class T>
void MyVector<T>::PushBack(T t) {
  if (size_ >= capacity_) {
    MyVector tmp(capacity_*2);
    for(int i=0; i<size_; ++i) {
      tmp.elements_[i] = elements_[i];
    }
    tmp.size_ = size_;
    *this = std::move(tmp);
  }
  elements_[size_++] = t;
}

Ćwiczenia do wykonania

  1. [? plusy] Drzewo wyszukiwań binarnych (BST) z możliwością przechowywania dowolnego typu posiadającego przeciążony operator<. Drzewo powinno udostępniać metody:
    1. void Insert(const Element &e)
    2. bool Find(const Element &e)
    3. size_t Depth()
    4. size_t Size()

Podpowiedź: poddrzewa można przechowywać jako raw pointer (*Tree), ale wtedy pamiętać o rule of 5 albo wykorzystać smart pointer (unique_ptr<Tree>)

  1. [1 punkty] Przygotować funkcję przyjumującą „obiekt” z możliwością wywołania siebie (tym „obiektem” może być lambda, wskaźnik do globalnej funkcji, struktura/klasa ze zdefiniowanym operatorem wywołania funkcji (operator()). Funkcja ma za zadanie zmierzenie czasu wykonania tego obiektu i zwrócenie tego czasu w razem z rezultatem wykonania „obiektu” jako parę. Czas ma być mierzony w milisekundach. Zakładamy, że „obiekt” nie przyjmuje, żadnych parametrów, ale może zwracać wartość dowolnego typu (nie void). Podpowiedź: biblioteka chrono może się przydać.
  2. [3 punkty] Przygotować klasę Teacher, TeacherId i TeacherHash, klasa Teacher jest zwykłą klasą wartości, TeacherId również (reprezentuje Id nauczyciela), natomiast TeacherHash to klasa/sturktura, która jest obiektem wyliczającym skrót za pomocą przeciążonego operatora wywołania funkcji (). Podpowiedzi: wyliczenia hash przy pomocy wbudowanej struktury hash<Type> i raczej + z mieszaniem, mnożeniem przez pierwszą niż xor
  3. [3 punkty] Zdefiniować klasę SequentialIdGenerator, która jest w stanie generować nowe wartości Id dla dowolnego typu Id (TeacherId, StudentId, CourseId, BuildingId…). Ponieważ klasy Id są obiektami niezmiennymi (a przynajmniej powinny być) SequentialIdGenerator powinien przyjmować jako parametr szablonu jeszcze jeden typ „prosty”, który będzie służył jako wewnętrzny licznik, który będzie inkrementowany przy potrzebie wygnenerowania nowego Id. Zakładamy, że typ Id musi posiadać konstruktor parametryczny z jednym argumentem typu „prostego”. Klasa SequentialIdGenerator powinna udostępniać metodę NextValue() która zwraca nowe Id, dodatkowo musi być możliwość wystartowania generatora z zadaną wartością (argument przekazany w konstruktorze). Tak naprawdę typ „prosty” nie musi być wcale wbudowanym typem, może to być dowolna klasa z przeciążonym preinkrementacji (operator++) i możliwością zrzutowania na int (operator int)
  4. [3 punkty] Przygotować funkcję PreOrder, PostOrder i InOrder dla drzewa BST, chodzi o to by możliwe było wykonanie:
    Tree<int> tree{5};
    tree.Insert(9); 
    ...
     
    cout << "PreOrder: ";
    for(const int &value_in_tree : PreOrder(tree)) {
      cout<<value_in_tree << " ";
    }
    cout << "InOrder: ";
    for(const int &value_in_tree : InOrder(tree)) {
      cout<<value_in_tree << " ";
    }
    cout << "PostOrder: ";
    for(const int &value_in_tree : PostOrder(tree)) {
      cout<<value_in_tree << " ";
    }

    Wskazówka: przyda się PreOrderTreeIterator z metodami operator++, operator*, operator!= i pewnie PreOrderTreeView z metodami begin() end(), zwaracjące wcześniejszy iterator.

pl/dydaktyka/jimp2/2017/labs/templates2.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0