Les Modèles C++ - LinkedList

Alors que les réponses ont déjà été fournis, je pense que je vais ajouter mon grain de sel.

Lors de la conception de modèles de classe, c'est une bonne idée de ne pas répéter les arguments de modèle à peu près partout, juste au cas où vous le souhaitez (un jour) de changer un détail particulier. En général, cela est fait en utilisant des typedefs.

template <class T>
class Node
{
public:
  //bunch of types
  typedef T value_type;
  typedef T& reference_type;
  typedef T const& const_reference_type;
  typedef T* pointer_type;
  typedef T const* const_pointer_type;

  //From now on, T should never appear
private:
  value_type m_value;
  Node* m_next;
};


template <class T>
class List
{
  //private, no need to expose implementation
  typedef Node<T> node_type;

  //From now on, T should never appear
  typedef node_type* node_pointer;

public:
  typedef typename node_type::value_type value_type;
  typedef typename node_type::reference_type reference_type;
  typedef typename node_type::const_reference_type const_reference_type;
  //...

  void add(value_type info);

private:
  node_pointer m_head, m_tail;
};

C'est aussi pour mieux définir les méthodes en dehors de la déclaration de la classe, fait qu'il est plus facile de lire l'interface.

template <class T>
void List<T>::add(value_type info)
{
  if(head == NULL) //if our list is currently empty
  {
    head = new node_type;
    head->setData(info);
    tail = head;
  }
  else //if not empty add to the end and move the tail
  {
    Node* temp = new node_type;
    temp->setData(info);
    temp->setNextNull();
    tail->setNext(temp);
    tail = tail->getNext();
  }
}

Maintenant, quelques remarques:

• il serait plus convivial si List<T>::add revenait un itérateur pour les nouveaux objets, comme les insert méthodes ne dans la STL (et vous pouvez la renommer insérer trop)
• dans la mise en œuvre de List<T>::add vous affecter la mémoire à temp puis effectuer un tas d'opérations, le cas échéant jette, vous avez une fuite de mémoire
• la setNextNull appel ne devrait pas être nécessaire: le constructeur de Node devez initialiser toutes les données membres de significatif des valeurs, inclus m_next

Voici donc une version révisée:

template <class T>
Node<T>::Node(value_type info): m_value(info), m_next(NULL) {}

template <class T>
typename List<T>::iterator insert(value_type info)
{
  if (m_head == NULL)
  {
    m_head = new node_type(info);
    m_tail = m_head;
    return iterator(m_tail);
  }
  else
  {
    m_tail.setNext(new node_type(info));
    node_pointer temp = m_tail;
    m_tail = temp.getNext();
    return iterator(temp);
  }
}

Remarque comment le simple fait d'utiliser un bon constructeur améliore notre exception de sécurité: si jamais rien jeter pendant le constructeur, new est nécessaire de ne pas allouer de la mémoire, donc rien n'est coulé et nous n'avons effectué aucune opération encore. Notre List<T>::insert méthode est maintenant résistant.

Dernière question:

D'habitude insert méthodes de simples listes liées insérer au début, parce que c'est plus facile:

template <class T>
typename List<T>::iterator insert(value_type info)
{
  m_head = new node_type(info, m_head); //if this throws, m_head is left unmodified
  return iterator(m_head);
}

Êtes-vous sûr que vous voulez aller avec un insert à la fin ? ou avez-vous le faire de cette façon en raison de la push_back méthode traditionnelle des vecteurs et des listes ?

OriginalL'auteur Matthieu M.

Comme l'a dit, la solution est

Node<T>* temp = new Node<T>;

... parce que Node lui-même n'est pas un type, Node<T> est.

OriginalL'auteur Kornel Kisielewicz

Et vous aurez besoin de spécifier le paramètre de modèle pour le Nœud *temp en printlist aussi.

OriginalL'auteur UnknownGuy

Vous Devez ajouter un nouveau nœud de cette façon

Node<T>* temp=new node<T>;

Espère que vous avez Résolu 🙂

OriginalL'auteur user4350912