Реструктурировать список итераторов после стирания

Question

Я создал пользовательские Node, Iterator и List.

Я хотел бы сделать:

List<int> list;

// push_back objects here...

List<int>::Iterator it = list.begin();
list.erase(it);
++it;
list.erase(it); // error here

Так что мне нужно восстановить итератор послестирание элементаКак мне это сделать?

---

Node.h

#pragma once

namespace Util
{
    template<typename T>
    class Node
    {
    public:
        template<typename T> friend class Iterator;
        template<typename T> friend class List;
    private:
        Node();
        Node(T);
        ~Node();

        /* unlink(): takes out this node
        and links next and prev to each other

        prev <- this -> next
        prev <-      -> next
        this <- this -> this
        */
        void unlink();
    private:
        T value;
        Node<T>* next;
        Node<T>* prev;
    };

    template<typename T>
    Node<T>::Node() : next(this), prev(this)
    {
        // ...
    }

    template<typename T>
    Node<T>::Node(T t) : value(t), next(this), prev(this)
    {
        // ...
    }

    template<typename T>
    Node<T>::~Node()
    {
        unlink();
    }

    template<typename T>
    void Node<T>::unlink()
    {
        next->prev = prev;
        prev->next = next;
        next = this;
        prev = this;
    }
}

---

Iterator.h

#pragma once

#include "Node.h"

namespace Util
{
    template<typename T>
    class Iterator
    {
    public:
        template<typename T> friend class List;

        Iterator& operator++();
        T& operator*() const;
        bool operator==(const Iterator& rhs) const;
        bool operator!=(const Iterator& rhs) const;
    private:
        Iterator(Node<T>* n);
        Node<T>* node;
    };

    template<typename T>
    Iterator<T>::Iterator(Node<T>* n) : node(n)
    {
        // ...
    }

    template<typename T>
    Iterator<T>& Iterator<T>::operator++()
    {
        node = node->next;
        return *this;
    }

    template<typename T>
    T& Iterator<T>::operator*() const
    {
        return node->value;
    }

    template<typename T>
    bool Iterator<T>::operator==(const Iterator& rhs) const
    {
        return node == rhs.node;
    }

    template<typename T>
    bool Iterator<T>::operator!=(const Iterator& rhs) const
    {
        return node != rhs.node;
    }
}

---

List.h

#pragma once

#include "Iterator.h"

namespace Util
{
    template<typename T>
    class List
    {
    public:
        typedef Iterator<T> Iterator;
        typedef Node<T> Node;

        List();
        ~List();

        // Capacity
        bool empty() const;
        int size() const;

        // Modifiers
        void push_back(const T&);
        void push_front(const T&);
        void pop_back();
        void pop_front();
        Iterator erase(Iterator it);

        // Element access
        Iterator begin() const;
        Iterator end() const;
    private:
        Node* head;
        int list_size;
    };

    template<typename T>
    List<T>::List() : list_size(0)
    {
        head = new Node();
    }

    template<typename T>
    List<T>::~List()
    {
        while (!empty()) pop_back();
        delete head;
    }

    template<typename T>
    bool List<T>::empty() const
    {
        return head->next == head;
    }

    template<typename T>
    int List<T>::size() const
    {
        return list_size;
    }

    template<typename T>
    void List<T>::push_back(const T& t)
    {
        Node* n = new Node(t);
        n->next = head;
        n->prev = head->prev;
        head->prev->next = n;
        head->prev = n;
        ++list_size;
    }

    template<typename T>
    void List<T>::push_front(const T& t)
    {
        Node* n = new Node(t);
        n->prev = head;
        n->next = head->next;
        head->next->prev = n;
        head->next = n;
        ++list_size;
    }

    template<typename T>
    void List<T>::pop_back()
    {
        if (head->prev == head) return;
        delete head->prev;
        --list_size;
    }

    template<typename T>
    void List<T>::pop_front()
    {
        if (head->next == head) return;
        delete head->next;
        --list_size;
    }

    template<typename T>
    typename List<T>::Iterator List<T>::erase(Iterator it)
    {
        if (it.node == head) return it;
        Node* n = it.node->next;
        delete it.node;
        --list_size;
        return Iterator(n);
    }

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

    template<typename T>
    typename List<T>::Iterator List<T>::end() const
    {
        return Iterator(head);
    }
}

---

Редактировать: после обновления кода на основе полученных комментариев.Просматривая список и стирая, стирает только все остальные элементы;поскольку цикл увеличивает итератор, а стирание делает текущий объект итератора следующим объектом итератора.Так ли это в стандарте?

for (Util::List<int>::Iterator it = list.begin(); it != list.end(); ++it)
{
    it = list.erase(it);
}

Старый список: 0 1 2 3 4 5 6 7 8 9
После удаления: 1 3 5 7 9

---

Пожалуйста, не жалуйтесь на правилоиз пяти и вещей, не связанных с вопросом.Я еще не дошел до каждой части.Мое оправдание внесения изменений в публикацию нового вопроса состоит в том, что редактирование по-прежнему заключается в том, как правильно восстановить итератор после стирания.

Answer 1

Как уже упоминали некоторые люди, erase обычно возвращает новый действительный итератор, если это возможно / возможно для контейнера.

Вы можете определить семантику по своему усмотрению, но обычно вы стираете элемент, указывая prev->next на next и next->prev на prev, затем освобождаете узел и возвращаете итератор на next. Вы также можете вернуть итератор на prev, но это приведет к нескольким нелогичным действиям, таким как необходимость продвигать итератор, если вы выполняете операцию в некотором диапазоне. Возвращая итератор к next, вы можете просто удалить диапазоны с помощью while(foo(it)) it = c.erase(it);

В этом случае вы, конечно, больше не увеличиваете итератор, если только вы не хотите пропустить все остальные элементы.