1

在过去，我使用节点实现了一个链表。

我正在查看标准库列表的一些属性，它具有迭代器和适当的成员函数。

列表中的迭代器到底是什么？它们是节点指针吗？

对于向量，基本上你有指向元素类型的指针，并且数据结构建立在该给定类型的底层动态数组上。

对于列表，它似乎只是一个节点序列，节点数组。那么迭代器是节点指针而不是指向节点数据类型的指针吗？

基本上我要问的是对于一个向量我是否有这个迭代器：

tyepdef T* iterator;

列表的迭代器是

typedef node* iterator;

其中节点类似于：

template <class T> struct node {
    node() { next = 0; }
    node(T i, node* n = 0) : data(i), next(n) {}
    node* next;
    T data;
}

如果是这种情况，似乎取消引用等操作将不得不重载。

4

2 回答 2

0

对象在std::list<T>::iterator内部指向一个节点，但具有适当地遵循指向下一个或前一个节点的指针的运算符。也就是说，它们不是指针，因为增加一个指针只是增加一个而不是跟随一个链接。你可以想象一个列表迭代器看起来有点像这样：

template <typename T>
class list_iterator {
    friend list<T>
    Node* node; 
    list_iterator(T* node):node(node) {}
    list_iterator& operator++() {
        node = node->next;
        return *this;
    }
    T& operator*() { return *node; }
     // ...
};
于 2013-11-09T22:21:43.730 回答
0

列表上的迭代器的行为应该类似于其他序列容器上的迭代器，例如vector. 即它应该表现得像一个指向 list::value_type 的指针，就好像它在一个数组或类似的东西中一样（使用 ++ 和 -- 执行预期的操作到下一个和上一个）。持有结构的内部并没有真正通过迭代器暴露出来。迭代器抽象通常使程序员不必考虑如何存储数据。将来，理论上您可以在不更改代码的情况下交换您std::list的 a std::vector，只要您只使用两者都可用的操作。

于 2013-11-09T22:22:10.110 回答