C++模拟实现List迭代器详解

概念

迭代器是一种抽象的设计概念，其定义为：提供一种方法，使他能够按顺序遍历某个聚合体（容器）所包含的所有元素，但又不需要暴露该容器的内部表现方式。

迭代器是一种行为类似智能指针的对象，而指针最常见的行为就是内容提领和成员访问。因此迭代器最重要的行为就是对operator*和operator->进行重载。

STL的中心思想在于：将数据容器和算法分开，彼此独立设计，最后再以一贴胶合剂（ iterator）将它们撮合在一起。STL的迭代器是一个可遍历STL容器全部或者部分数据

迭代器使用

我们可以使用迭代器访问修改链表元素

list<int>  lt;
list<int>::iterator it=lt.begin();
while(it!=lt.end())
{
    *it+=2;
    cout<<*it<<" ";
    it++;
}

2.我们有些函数接口需要传迭代器，例如：

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);
?
template <class ForwardIterator, class T>
  void replace (ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value);

迭代器模拟实现

迭代器的大体结构

//链表节点
template<class T>
struct ListNode {
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;
    //构造节点值
    ListNode(const T& data = T())
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(data)
    {}
};
?
///迭代器
//T为list数据类型，Ref为T&,Ptr为T*
template<class T,class Ref,class Ptr>
struct __list_iterator
{
    typedef ListNode<T> Node;
    typedef __list_iterator<T,Ref,Ptr> self;
    Node* _node;//节点指针
    
    //接下来实现的函数都是在这个位置
};

构造函数

一般都会传过来一个节点地址

__list_iterator(Node* x)
:_node(x)
{ }

注意迭代器的拷贝构造、赋值重载以及析构函数不需要我们自己实现，编译器实现的完全够用。

拷贝构造与赋值重载：因为list迭代器本身就是一个自定义类型的指针，都是地址的拷贝与赋予。所以浅拷贝就满足使用。
析构函数：因为list迭代器是借助节点指针访问修改链表，节点是链表的，不需要迭代器释放。

解引用重载

解引用重载（*）

解引用本质是根据地址拿到在这个地址的有效数据

Ref operator*()
{
    return _node->_data;
}

重载

->重载

->本质是拿到所求数据的地址

Ptr operator->()
{
    return &_node->_data;
}

自增实现

前置++

++后迭代器指向当前位置的下一个位置，返回指向下一个位置的迭代器

self& operator++()
{
    _node=_node->_next;
    return *this;
}

后置++

++后迭代器指向当前位置的下一个位置，返回指向之前位置的迭代器,要使用一个临时变量保存++之前的this指针，然后后移_node,返回临时变量。

//这块一定要使用占位符，防止与前置++重命名。
self& operator++(int)
{
    __list_iterator<T> tmp(*this);
    _node=_node->_next;
    return tmp;
}

自减实现

与++基本一样，不做解释。

前置--

self& operator--()
{
    _node=_node->_prev;
    return *this;
}

后置--

self& operator--（int）
{
    __list_iterator<T> tmp(*this);
    _node=_node->_prev;
    return tmp;
}

运算符重载

bool operator!=(const self& it)const
{
    return _node!=it._node;
}
 
bool operator==(const self& it)const
{
    return _node==it._node;
}

迭代器失效

以vector为例，当我们插入一个元素时它的预分配空间不够时，它会重新申请一段新空间，将原空间上的元素复制到新的空间上去，然后再把新加入的元素放到新空间的尾部，以满足vector元素要求连续存储的目的。而后原空间会被系统撤销或征做他用，于是指向原空间的迭代器就成了类似于“野指针”一样的东西，指向了一片非法区域。如果使用了这样的迭代器会导致严重的运行时错误就变得很自然了。这也是许多书上叙述vector在insert操作后“可能导致所有迭代器实效”的原因。

但是想到这里我不禁想到vector的erase操作的叙述是“会导致指向删除元素和删除元素之后的迭代器失效” ，这里的删除元素不一定不成功，但一定存在迭代器失效。例：

vector<int> v;//{1,2,3,4,5}
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
    if(*it%2==0)
    {
        v.erase(it);
    }
    it++;
}

所以要避免这种情况，改进代码

vector<int> v;//{1,2,3,4,5}
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
    if(*it%2==0)
    {
        v.erase(it);
    }
    else
        it++;
}

list迭代器失效

list<int> l1;
list<int>::iterator it=l1.begin();
while(it!=l1.end())
{
    if(*it%2==0)
    {
        l1.erase(it);
    }
    else
        ++it;
}

改进代码

list<int> l1;
list<int>::iterator it=l1.begin();
while(it!=l1.end())
{
    if(*it%2==0)
    {
        it=l1.erase(it);
    }
    else
        ++it;
}

归纳迭代器失效的类型

（1）由于容器元素整体“迁移”导致存放原容器元素的空间不再有效，从而使得指向原空间的迭代器失效。

（2）由于删除元素使得某些元素次序发生变化使得原本指向某元素的迭代器不再指向希望指向的元素

模拟List

具体下一章讲

 template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        iterator begin()
        {
            return iterator(_head->_next);
        }
?
        iterator end()
        {
            return iterator(_head);
        }
?
        const_iterator begin()const
        {
            return const_iterator(_head->_next);
        }
?
        const_iterator end()const
        {
            return const_iterator(_head);
        }
?
        list()
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;
        }
        void push_back(const T& x)
        {
            Node* tail = _head->_prev;
            Node* newnode = new Node(x);
            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }
?
        void insert(iterator pos, const T& x)
        {
?
        }
        void erase(iterator pos)
        {
?
        }
    private:
        Node* _head;
    };

频道导航