c++ - 删除后重建列表迭代器

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;
    }
}

---

迭代器.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);

删除范围

在那种情况下，你当然不会再增加迭代器，除非你不想跳过所有其他元素。