Skip to main content
added 173 characters in body
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338
    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        // Though with the fix I suggested above this changes.
        return Iterator(_head->next);

        // If you only have the tail `Sentinel` this becomes
        return Iterator(_head);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }
    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        return Iterator(_head->next);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }
    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        // Though with the fix I suggested above this changes.
        return Iterator(_head->next);

        // If you only have the tail `Sentinel` this becomes
        return Iterator(_head);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }
added 6 characters in body
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338

Looks fine.
ThereThere is definitely a bug in your constructor where you build two Sentinels it should only be one. Otherwise your iterators for an empty list will iterate once.

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        return Iterator(_head->next);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }

I haven't yet figured out how to implement:

Iterator insert(const Iterator, T); Iterator erase(const Iterator);

If you have to insert before the iterator? Then you can simply implement like I did above:

Iterator insert(const Iterator iterator, T value) {
    Node* n = new Node(value, iterator->_current);
    return Iterator(n);
}

Lets assume erase returns the iterator to the next element.

Iterator erase(const Iterator iterator)
    Node* current = iterator->_current;
    if (current == _tail) // can't delete the tail
        return iterator;
    }

    // otherwise unlink from previous item.
    if (current->prev == nullptr) {
        head = current->next;
    }
    else {
        current->prev->net = current->next;
    }
    // Next unlink from the next item.
    current->next->prev=current->prev;

    // Get the next item so we can return it.
    Node* result = current->next;

    // Delete the old value.
    delete current;

    // return the new result.
    return Iterator(result);
}

Looks fine.
There is definitely a bug in your constructor where you build two Sentinels it should only be one. Otherwise your iterators for an empty list will iterate once.

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        return Iterator(_head->next);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }

There is definitely a bug in your constructor where you build two Sentinels it should only be one. Otherwise your iterators for an empty list will iterate once.

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        return Iterator(_head->next);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }

I haven't yet figured out how to implement:

Iterator insert(const Iterator, T); Iterator erase(const Iterator);

If you have to insert before the iterator? Then you can simply implement like I did above:

Iterator insert(const Iterator iterator, T value) {
    Node* n = new Node(value, iterator->_current);
    return Iterator(n);
}

Lets assume erase returns the iterator to the next element.

Iterator erase(const Iterator iterator)
    Node* current = iterator->_current;
    if (current == _tail) // can't delete the tail
        return iterator;
    }

    // otherwise unlink from previous item.
    if (current->prev == nullptr) {
        head = current->next;
    }
    else {
        current->prev->net = current->next;
    }
    // Next unlink from the next item.
    current->next->prev=current->prev;

    // Get the next item so we can return it.
    Node* result = current->next;

    // Delete the old value.
    delete current;

    // return the new result.
    return Iterator(result);
}
added 6 characters in body
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338

Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call). template Linked_List::~Linked_List() noexcept(false) { while (!empty()) { pop_back(); } delete head; delete tail; }

    template<typename T>
    Linked_List<T>::~Linked_List() noexcept(false)
    {
        while (!empty())
        {
            pop_back();
        }
        delete head;
        delete tail;
    }

Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call). template Linked_List::~Linked_List() noexcept(false) { while (!empty()) { pop_back(); } delete head; delete tail; }

Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call).

    template<typename T>
    Linked_List<T>::~Linked_List() noexcept(false)
    {
        while (!empty())
        {
            pop_back();
        }
        delete head;
        delete tail;
    }
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338
Loading