擦除后重构列表迭代器

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);删除范围

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