Le pointeur d'itérateur ne fait pas référence au premier élément

Question

J'essaie d'implémenter une LinkedList qui peut être itérée en C++.

J'ai donc créé une classe Iterator, de sorte que déréférencer un Iterator retournerait le premier élément. Cependant, cela n'a pas fonctionné. Quand j'instancie alors un nouvel int LinkedList et que j'essaie d'accéder au premier élément en déréférenciant le résultat de begin(), je ne récupère pas le premier élément de la liste, mais un numéro à 10 chiffres tel que '1453755360'

classe de noeud est juste composé de deux pointeurs de noeuds droite/gauche et une variable de données

classe LinkedList

template <typename T> 
class LinkedList{ 

public: 
    LinkedList(){ 
     count =(0); 
     head =(nullptr); 
     tail =(nullptr); 
    } 

    void push_head(T input){ 

     Node<T> newNode = Node<T>(input); 
     newNode.left = nullptr; 
     newNode.right = head; 

     head = &newNode; 
     count++; 
    } 

    T front(){ 
     T& data = (head->data); 
     return data; 
    } 

    void push_tail(T input){ 

     Node<T> newNode = Node<T>(input); 
     newNode.right = tail; 
     newNode.left = nullptr; 

     tail = &newNode; 
     count++; 
    } 

    T back(){ 
     T& data = (tail->data); 
     return data; 
    } 


    Iterator<T> begin(){ 
     Iterator<T> test = Iterator<T>(head); 
     return test; 
    } 


private: 
    int count; 
    Node<T> *head; 
    Node<T> *tail; 

}; 

Voici où je teste le code

LinkedList<int> ll; 

    ll.push_tail(7); 
    ll.push_tail(9); 

    if (*(ll.begin()) == 9) { 
     cout << "pass" << endl; 
    } else { 
     cout << "returned : " << *(ll.begin()) << endl; 
    } 

Answer 1

Vous allouez vos objets de noeud sur la pile, de sorte qu'ils sont détruits automatiquement lorsqu'ils sortent de la portée. Vous stockez des pointeurs sur ces objets, ce qui laisse les pointeurs suspendus lorsque les objets sont détruits. Vous devez allouer les noeuds sur le tas à l'aide de new à la place.

En outre, push_front() ne met pas à jour tail lorsque la liste est vide et ne met pas à jour un head existant pour pointer vers le nouveau noeud lorsque la liste n'est pas vide. Similaire avec push_back().

Essayez quelque chose comme ceci:

template <typename T> 
struct Node 
{ 
    T data; 
    Node *left; 
    Node *right; 

    Node(const T &d = T(), Node *l = nullptr, Node *r = nullptr) 
     : data(d), left(l), right(r) {} 
}; 

template <typename T> 
class NodeIterator { 
public: 
    typedef std::ptrdiff_t difference_type; 
    typedef T value_type; 
    typedef T* pointer; 
    typedef T& reference; 
    typedef std::bidirectional_iterator_tag iterator_category; 

    NodeIterator(Node<T> *input = nullptr) : cur(input) {} 
    NodeIterator(const NodeIterator &) = default; 
    NodeIterator(NodeIterator &&) = default; 
    ~NodeIterator() = default; 

    NodeIterator& operator=(const NodeIterator &) = default; 
    NodeIterator& operator=(NodeIterator &&) = default; 

    reference operator*() { 
     return cur->data; 
    } 

    NodeIterator& operator++() { 
     if (cur) cur = cur->right; 
     return *this; 
    } 

    NodeIterator operator++ (int) { 
     NodeIterator tmp(*this); 
     if (cur) cur = cur->right; 
     return tmp; 
    } 

    NodeIterator& operator--() { 
     if (cur) cur = cur->left; 
     return *this; 
    } 

    NodeIterator operator-- (int) { 
     NodeIterator tmp(*this); 
     if (cur) cur = cur->left; 
     return tmp; 
    } 

    bool operator==(const NodeIterator &rhs) const { 
     return (rhs.cur == cur); 
    } 

    bool operator!=(const NodeIterator &rhs) const { 
     return (rhs.cur != cur); 
    } 

private: 
    Node<T> *cur; 
}; 

template <typename T> 
class LinkedList { 
public: 
    typedef NodeIterator<T> iterator; 

    LinkedList() : count(0), head(nullptr), tail(nullptr) {} 

    ~LinkedList() { 
     while (head) { 
      Node<T> *tmp = head; 
      head = head->right; 
      delete tmp; 
     } 
    } 

    void push_front(const T &input) { 
     Node<T> *newNode = new Node<T>(input, nullptr, head); 

     if (head) head->left = newNode; 
     head = newNode; 

     if (!tail) tail = newNode; 

     ++count; 
    } 

    T& front() { 
     return head->data; 
    } 

    void push_back(const T &input) { 
     Node<T> *newNode = new Node<T>(input, tail, nullptr); 

     if (!head) head = newNode; 

     if (tail) tail->right = newNode; 
     tail = newNode; 

     ++count; 
    } 

    T& back() { 
     return tail->data; 
    } 

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

    iterator end() { 
     return iterator(); 
    } 

private: 
    int count; 
    Node<T> *head; 
    Node<T> *tail;  
}; 

Ensuite, vous pouvez faire ceci:

LinkedList<int> ll; 

ll.push_back(7); 
ll.push_back(9); 

auto iter = ll.begin(); 
if (*iter == 7) { 
    cout << "pass" << endl; 
} else { 
    cout << "returned : " << *iter << endl; 
} 

Vous pouvez même faire des choses comme ça maintenant:

for (LinkedList<int>::iterator iter = ll.begin(), end = ll.end(); iter != end; ++iter) { 
    cout << *iter << endl; 
} 

for (int i : ll) { 
    cout << i << endl; 
} 

Answer 2

L'implémentation push_back() nécessite que si head est nul, il doit être défini, de même pour push_front par rapport à tail.