c++ - 列表的元素和下一个元素的迭代器

Question

我不明白 Bjarne 的想法：

列表迭代器必须比指向元素的简单指针更复杂，因为列表的元素通常不知道该列表的下一个元素在哪里。因此，列表迭代器可能是指向链接的指针

我知道列表的节点有指向下一个和前一个节点的指针。那么它怎么“一般不知道”呢？

Answer 1

相比之下，让我们考虑一个std::vector. 尽管您可能不想这样做，但您基本上可以将其实现为一个简单的指针：

template <class T>
class vector {
    T *data;
    size_t current_size;
    size_t alloc_size;
public:
    typedef T *iterator;
    iterator begin() { return data; }
    iterator end() { return data+current_size; }
    // ...
};

并且由于向量中的数据是连续的，因此当您（例如）++在迭代器上执行操作时，它会做正确的事情（让您进入向量中的下一项）。

使用链表，它不可能那么简单——如果你曾经typedef让迭代器成为 的别名T *，它就不能正常工作。当您尝试++在迭代器上执行操作时，它只会增加指针，而不是像需要的那样将您带到链表中的下一个元素。

您需要在迭代器类中构建一些智能，以便 operator++（例如）知道“追逐”指针，而不仅仅是递增。

template <class T>
class list { 

    class node { 
        T data;
        node *next;
        node *prev;
    };
public:
    class iterator {
        node *pos;
    public:
        iterator operator++() {
            return pos = pos->next;
        }
        iterator operator--() {
            return pos = pos->prev;
        }
    };
};

Answer 2

不要将列表节点与列表元素混淆。它可能是一个指针，但指向一个包含元素和下一个/上一个链接的节点。如果它只是一个指向元素的指针，你将无法随它移动。（虽然它不太可能只是指针，因为它通常必须重载 operator++ 来获取下一个指针而不是自增）。

这不适用于插入式列表，其中节点 == 元素，但这不是 std::list。

// illustrative
template <typename ElementType>
struct list_node {
    ElementType element;
    list_node *next, *prev;
};