Как использовать шаблоны в связанном списке c ++?

Question

Я не полностью понимаю концепцию шаблонов и пытаюсь получить некоторую помощь о том, как реализовать один из них в моем списке нижеЯ пытаюсь, чтобы мой код поддерживал следующие типы: List< List<std::string> > List<std::string> List<int>. Мне было интересно, может ли кто-нибудь дать мне пример того, как преобразовать эти элементы в шаблоны в дополнение к попыткам объяснить, что происходит? Я новичок в C ++, поэтому любая помощь, которую я могу получить, будет оценена.

#include <string>
#include <iostream>
#include <cstddef>


using Item = std::string;

// TURN DList into a template!
class DList {
private:

  class DListNode {
  public:
    Item item;
    DListNode * next;
    DListNode * prev;
    DListNode(Item i, DListNode *n=nullptr, DListNode *p=nullptr) {
      item = i;      
      next = n;
      prev = p;
    }
  };

  DListNode * head;
  DListNode * tail;

public:
  class iterator {
    DListNode *node;
  public:
    iterator(DListNode *n = nullptr) {
      node = n;
    }

    Item& getItem() { return node->item; }
    void next() { node = node->next; }
    void prev() { node = node->prev; }
    bool end() { return node==nullptr; }

    friend class DList;
  };



public:
  DList() {
    // list is empty
    head = nullptr;
    tail = nullptr;
  }

  bool empty() {
    return head==nullptr;
  }

  void append(Item a) {
    DListNode *node = new DListNode(a,nullptr,tail);
    if ( head == nullptr ) {
      // empty list
      head = node;
      tail = node;
    } else {
      tail->next = node;
      tail = node;
    }
  }

  void insertAfter(iterator it, Item item)
  {
    if(head == nullptr || it.node == nullptr) { // NULL iterator means insert at head
      DListNode *node = new DListNode(item,head); // next=head, prev=NULL
      if ( head == nullptr) // same as zyBook
        head = tail = node;
      else { // if inserting before head, it.node==NULL
        head->prev = node;
        head = node;
      }
    } else if (it.node == tail) {
      DListNode *node = new DListNode(item,nullptr,tail); // next=NULL, prev=old tail
      tail->next = node;
      tail = node;
    } else {
      DListNode *node = new DListNode(item,it.node->next,it.node);
      it.node->next = node;
      node->next->prev = node;
    }
  }

  void erase (iterator it) {
    DListNode *succ = it.node->next; // successor node
    DListNode *pred = it.node->prev; // predecessor node

    if (succ != NULL)
      succ->prev = pred;
    if (pred != NULL)
      pred->next = succ;

    if (it.node == head)
      head = succ; // head is following node
    if (it.node == tail)
      tail = pred; // tail is previous node

    delete it.node; // delete the node; not shown in zyBook, but necessary in C/C++
    // iterator is now invalid, caller should not use it again
  }

  iterator begin() {
    return iterator(head);
  }

  iterator reverse_begin() {
    return iterator(tail);
  }
};

template <typename Item>
std::ostream& operator << (std::ostream& out, DList<Item> &l)
{
  out << "{";
  auto it = l.begin();
  out << it.getItem();
  it.next();
  for(; !it.end(); it.next())
    {
      out << ", " << it.getItem();
    }
  out << "}" << std::endl;
  return out;
}


int main()
{
  {
    DList<std::string> l;

    l.append("eggs");
    l.append("milk");
    l.append("bread");

    std::cout << l;
  }
  {
    DList<int> l;

    l.append(1);
    l.append(2);
    l.append(3);

    std::cout << l;
  }
  return 0;
}

Answer 1

На самом деле у вас есть почти все, что вам нужно, но вы все еще используете обычный класс с конкретным типом.

using Item = std::string;

class DList { ... };

Итак, сначала мы отбрасываем конкретный тип:

// using Item = std::string;

class DList { ... }; // sure Item is now undefined...

Затем мы говорим, что класс должен быть шаблоном

template <typename Item>
class DList { ... };

Теперь Item вновь введен, но вместо того, чтобы быть конкретным типом, теперь он является универсальным. Вот и все, у вас есть список шаблонов (при условии, что список реализован правильно, я не проверял).

Всякий раз, когда вы сейчас создаете экземпляр своего списка:

DList<int>;
DList<std::string>;
// ...

Вы создаете совершенно новыйнезависимый тип данных (это означает, в частности, что вы не можете назначить DList<int> для указателя на DList<double>, просто все так же, как вы не можете назначить int для указателя, чтобы удвоить либо).

Когда выПри создании экземпляра шаблона каждый экземпляр параметра шаблона будет заменен типом, с которым вы создали экземпляр шаблона, например, в DList<int>, каждый случай Item будет заменен на int.

Ну,все это просто очень краткое введение, еще много чего нужно сделать, но это скорее будет рассмотрено в книге, чем в ответе на stackoverflow ...

Хотя некоторые примечания для конструктора вашего узла:

DListNode(Item i /* , ... */) { item = i; }

Сначала вы должны привыкнуть к использованию списка инициализатора конструктора (не путать с std::initializer_list):

DListNode(Item i /* , ... */) : item(i) { }

Вы избегаете стандартных инициализацийДействие + присваивание в пользу прямой инициализации по значению. Кроме того, некоторые типы (не конструируемые по умолчанию, константы и ссылки) только могут быть инициализированы таким образом.

Затем вы создаете ненужную копию:

DListNode(Item i /* , ... */) : item(i) { }
//             ^ temporary copy   ^ final copy, created from temporary

Вы избегаете этой копии, если принимаете элемент по ссылке:

DListNode(Item const& i /* , ... */) : item(i) { }
// now copies from reference, one copy less

Вы можете дополнительно указать семантику перемещения:

DListNode(Item&& i /* , ... */) : item(std::move(i)) { }

, чтобы объекты, которые вам не нужны, находились внеСписок больше можно перенести в (ну собственно их содержимое). В некоторых случаях это может быть намного дешевле, чем полная копия ...

Все сказанное о конструкторе (кроме списка инициализатора) относится и к функциям append и insertAfter.

Списки инициализаторов и избегание копий - это общий совет, не связанный с шаблонами ...