13.2 Szablony struktur

Podobnie jak dla funkcji, możemy definiować struktury w postaci wzorców (szablonów) zależnych od jednego lub więcej parametrów typu. Wywołując funkcję zadaną w postaci szablonu zazwyczaj nie musieliśmy specyfikować konkretnych typów jakie mają zostać podstawione za parametry typów szablonu: kompilator mógł je sam wywnioskować na podstawie typów argumentów. W przypadku szablonów struktur (klas) tak nie jest — zazwyczaj (choć nie zawsze) musimy ten typ określić. Jeśli, jak w przykładzie poniżej, Node jest szablonem struktury zależnym od jednego parametru typu, to tworząc obiekt tego typu musimy określić typ: Node jest nazwą szablonu, nazwą konkretnej struktury będzie Node<int>, Node<std::string>, itd. Ilustruje to poniższy przykład:

P104: listy.cpp Prosta lista jednokierunkowa jako szablon

      1.  #include <iostream>
      2.  #include <string>
      3.  using namespace std;
      4.  
      5.  template <typename T>
      6.  struct Node {
      7.      T data;
      8.      Node *next;
      9.  };
     10.  
     11.  template <typename T>
     12.  void addFront(Node<T>*& head, T data) {   ➊
     13.      head = new Node<T>{data, head};
     14.  }
     15.  
     16.  template <typename T>
     17.  void addBack(Node<T>*& head, T data) {
     18.      if (head == nullptr) addFront(head, data);
     19.      else {
     20.          Node<T>* tmp = head;              ➋
     21.          while (tmp->next != nullptr)
     22.              tmp = tmp->next;
     23.          tmp->next = new Node<T>{data, nullptr};
     24.      }
     25.  }
     26.  
     27.  template<typename T>
     28.  void printList(const Node<T>* h) {        ➌
     29.      std::cout << "[ ";
     30.      while (h != nullptr) {
     31.          std::cout << h->data << " ";
     32.          h = h->next;
     33.      }
     34.      std::cout << "]\n";
     35.  }
     36.  
     37.  template <typename T>
     38.  void deleteList(Node<T>*& h) {            ➍
     39.      while (h != nullptr) {
     40.          Node<T>* t = h->next;
     41.          delete h;
     42.          h = t;
     43.      }
     44.  }
     45.  
     46.  int main() {
     47.        // "jakisnapis"s będzie literałem typu std::string
     48.      using namespace std::literals;        ➎
     49.  
     50.      Node<int>* headI{nullptr};
     51.      addBack(headI,  3);
     52.      addBack(headI,  4);
     53.      addFront(headI, 2);
     54.      addFront(headI, 1);
     55.      printList(headI);
     56.      deleteList(headI);
     57.  
     58.      Node<std::string>* headS{nullptr};
     59.      addBack(headS,  "kiery"s);
     60.      addBack(headS,  "piki"s);
     61.      addFront(headS, "kara"s);
     62.      addFront(headS, "trefle"s);
     63.      printList(headS);
     64.      deleteList(headS);
     65.  }

Szablon struktury Node opisuje pojedynczy element listy jednokierunkowej. Typ danych nie jest określony — jest parametrem typu szablonu (tu oznaczonym przez T). Definiujemy też dwie funkcje (znów, w postaci szablonów) które dodają nowe elementy do listy. W funkcji main lista reprezentowana jest przez wskaźnik do pierwszego węzła listy (nazywany głową, ang. head) — wartość nullptr tego wskaźnika odpowiada liście pustej.

Funkcja addFront pobiera głowę listy i daną: tworzy obiekt zawierający tę daną a jego pole next wskazuje na dotychczasową głowę; nowy węzeł staje się nową głową a dotychczasowa głowa będzie teraz drugim węzłem listy. Zwróćmy uwagę (➊), że głowa została przekazana do funkcji przez referencję, aby funkcja mogła ją zmodyfikować.

Podobna jest funkcja addBack, która dodaje nowy węzęl na końcu listy. Jeśli lista jest pusta, to wywoływana jest funkcja addFront, która radzi sobie z takim przypadkiem. W przeciwnym razie, przebiegamy przez listę w pętli tak, aby zatrzymać się gdy tmp wskazuje na ostatni węzeł – ten, którego pole next jest nullptr. To właśnie pole zastępujemy wskaźnikiem na nowoutworzony węzeł, który staje się ostatnim. Zwróćmy uwagę, że aby przebiegać przez listę, utworzyliśmy kopię wskaźnika head (➋). Musieliśmy tak zrobić, bo head został przekazany przez referencję (oryginał), więc nie możemy go dowolnie zmieniać!
Inaczej jest w funkcji printList (➌), gdzie wskaźnik head jest przekazywany przez wartość, a więc jego zmiana wewnątrz funkcji nie wpłynie na oryginał.
Nie możemy też zapomnieć o funkcji deleteList (➍), która usuwa w pętli wszystkie węzły listy (utworzone wcześniej na stercie za pomocą operatora new).

W programie tworzymy listę z danymi typu int, a potem string. Zauważmy, że napisy, które są danymi w drugiej z tych list, musieliśmy zapisać w postaci literałów typu string — bez sufiksu 's' typem ich byłoby const char*, co nie byłoby zgodne z typem elementów listy; aby skorzystać z tego sufiksu, trzeba „otworzyć” przestrzeń nazw std::literals (➎). Wydruk programu to

Inny, podobny, przykład ilustruje jak za pomocą listy można łatwo i efektywnie zaimplementować stos

P105: StackTmplt.cpp Implementacja stosu poprzez szablony

      1.  #include <iostream>
      2.  #include <string>
      3.  
      4.  template <typename T>
      5.  struct Node {
      6.      T     data;
      7.      Node* next;
      8.  };
      9.  
     10.  template <typename T>
     11.  void push(Node<T>*& head, T d) {
     12.      head = new Node<T>{d, head};
     13.  }
     14.  
     15.  template <typename T>
     16.  T pop(Node<T>*& head) {
     17.      T d{head->data};
     18.      Node<T>* n{head->next};
     19.      delete head;
     20.      head = n;
     21.      return d;
     22.  }
     23.  
     24.  template <typename T>
     25.  bool empty(Node<T>* head) {
     26.      return head == nullptr;
     27.  }
     28.  
     29.  int main() {
     30.        // "something"s is now a literal of type std::string
     31.      using namespace std::literals;
     32.  
     33.      Node<int>* headI{nullptr};
     34.      Node<std::string>* headS{nullptr};
     35.      push(headI, 3); push(headS, "3"s);
     36.      push(headI, 2); push(headS, "2"s);
     37.      push(headI, 1); push(headS, "1"s);
     38.                      push(headS, "0"s);
     39.      while(!empty(headI))
     40.          std::cout << pop(headI) << " ";
     41.      std::cout << std::endl;
     42.  
     43.      while(!empty(headS))
     44.          std::cout << pop(headS) << " ";
     45.      std::cout << std::endl;
     46.  }

Dzięki zastosowaniu szablonu możemy tworzyć stosy dla różnych typów (w powyższym przykładzie są to int i string). Wydruk programu to