List中的迭代器实现【C++】

一. list的结构

其实按照习惯来说，应该要专门出一篇博客来写

list的模拟实现，但是其实list与vector以及string的主要区别在于迭代器的设计。

所以就偷个懒直接写迭代器的部分了。

这里先声明以下，我这里就是进行一下模拟实现，STL中的list的iterator虽然并不是这样实现的，但是实现逻辑和结构都大差不差

这里就先贴上list类的结构：

namespace list
{
    template<class T>
    struct list_node
    {
        list_node<T>* _prev;
        list_node<T>* _next;
        T _val;
        //节点的构造函数
        list_node(const T& val = T())
            :_prev(nullptr)
            , _next(nullptr)
            , _val(val)
        {}
    };
    template<class T>
    class list
    {
    public:
        list()
        {
        //链表的默认构造
            list_node<T>* head = new list_node<T>;
            //初始化哨兵位
            _head = head;
            _head->_next = _head;
            _head->_prev = _head;
            _size = 0;
        }
        ~list()
        {
        }
    private:
        list_node<T>* _head;
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

这个其实和我们之前写的双向带头循环链表一样。

二. 迭代器的区别

迭代器的区别，落到实质问题上
还是容器与容器的区别，也就是vector与list的区别

vector中的iterator是这样去实现的。

首先：

typedef T* iterator;
1

这里先重命名

iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
1
2
3
4
5
6
7
8

随后直接设计end与begin的函数。

之后就能发现，范围for与迭代器能直接进行使用了。

因为我们实现vector指针的方法是直接将内置类型指针进行改名。

而内置类型指针支持++，所以可以直接运行程序了。
但我们想想list肯定就不支持这样的操作了

vector能这这样，是因为数据存储在内存空间中连续时，正好可以进行使用。

但是list的问题是，内存空间是不连续的
这样的话再用指针内部支持的++算法就不太合适了。

所以我们今天就是为了来模拟实现list的迭代器的实现。

首先的目标就是实现下面这个代码的跑动。

	list::list<int>::iterator it = l1.begin();
	while (it != l1.end())
	{
		std::cout << *it;
		++it;
	}
1
2
3
4
5
6

三. 迭代器的实现

我们首先来看，我们最难解决的问题就是it的前置++
因为vector和list最重要的问题就是运算的方式不一样。

那我们想要用我们自己的方式进行++。
这个时候就应该想到了我们模拟实现类的时候最常用的东西：重载运算符

重载运算符在哪里能用：自定义类型
所以我们这个时候应该自然而然的想到自己写一个类，来充当iterator
从而实现我们想要的++方式。

i. 类的设计

    template<class T>
    struct __list_iterator
    {
        list_node<T>* _node;
        __list_iterator(list_node<T>* node)
            :_node(node)
        {}

    };
1
2
3
4
5
6
7
8
9

基本上大致结构是这样。

其中list_node就是双链表的节点结构。（上面写过）

这里添加个typedef

        template<class T>
        class list
        {
        public:
            typedef __list_iterator<T> iterator;
1
2
3
4
5

这个typedef和vefctor的使用没有什么大区别了。

现在来专注实现上面代码的所有的重载即可

ii. ++重载

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

1
2
3
4
5
6

这个就是我们以前写的双链表和单链表的部分了。

iii. !=重载

 bool operator!=(const __list_iterator<T>& node)
 {
     return _node != node._node;
 }
1
2
3
4

iiii. begin()

注意：这里的end和begin都是在list中的

因为迭代器执行时，会在list中寻找begin和end

 iterator begin()
 {
     return iterator(_head->_next);
 }
1
2
3
4

这里我们需要返回的是迭代器的类型

所以需要调用一下迭代器的构造函数

iiiii. end()

 iterator end()
 {
     return _head;
 }

1
2
3
4
5

我们发现begin需要调用构造函数

但是这边end却没有调用

因为单参数的构造函数返回时
如果返回的类型和需要返回的类型不同
就会主动调用需要返回类型的构造函数进行转换

iiiii. operator*

 T& operator*()
 {
     return _node->_val;
 }
1
2
3
4

四.测试

这里就直接写一个push_back的方法

  void push_back(const T& val)
  {
      insert(end(), val);
  }
        void insert(iterator pos, const T& val)
        {
            list_node<T>* new_node = new list_node<T>(val);
            _size++;
            pos._node->_prev->_next = new_node;
            new_node->_prev = pos._node->_prev;
            new_node->_next = pos._node;
            pos._node->_prev = new_node;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13

接下来进行测试即可

	list::list<int> l1;
	l1.push_back(1);
	l1.push_back(1);
	l1.push_back(1);
	l1.push_back(1);
	l1.push_back(1);
	list::list<int>::iterator it = l1.begin();
	while (it != l1.end())
	{
		std::cout << *it;
		++it;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13

这里能发现程序完美执行了。

五. const迭代器的实现

我们在使用STL中自带的迭代器时

应该经常能用到const迭代器。

const_iterator

这里我们首先要清楚const_iterator实现的是什么：

我们清楚效果是：指向的内容不能修改，但是迭代器本身可以修改。

所以实现的类型就是const T* ptr

而不是T* const ptr

那我们要达成这种效果。
可以从函数的返回值上入手

平常使用函数时，基本上都是通过重载符*
来进行对应值的修改

 const T& operator*()
 {
     return _node->_val;
 }
1
2
3
4

那我们这样不就可以了吗。。

i. 实现

typedef __list_iterator<T>const_iterator;
1

这里在list中重命名一下。

    template<class T>
    struct __list_const_iterator
    {
        list_node<T>* _node;
        __list_const_iterator(list_node<T>* node)
            :_node(node)
        {}
      

        const T& operator*()
        {
            return _node->_val;
        }
        __list_const_iterator<T>& operator++()
        {
            _node = _node->_next;
            return *this;
        }
     
      

        bool operator!=(const  __list_const_iterator<T>& node)
        {
            return _node != node._node;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

之后再把这个类丢进去。

但是这样会发现，实现的太过繁杂了。

这里就来个优化版本。

ii 优化实现

这里先直接上结果

list中的重命名：

 typedef __list_iterator<T, T&, T*> iterator;
 typedef __list_iterator<T, const T&, const T*>const_iterator;
1
2

具体实现：

    template<class T, class ref>
    struct __list_iterator
    {
        list_node<T>* _node;
        __list_iterator(list_node<T>* node)
            :_node(node)
        {}
      

        ref& operator*()
        {
            return _node->_val;
        }
        __list_iterator<T, ref, ptr>& operator++()
        {
            _node = _node->_next;
            return *this;
        }
     
      

        bool operator!=(const  __list_iterator<T, ref, ptr>& node)
        {
            return _node != node._node;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这里是给模板新添加了一个参数。

从而实现const与普通的两种类型迭代器的实现。

六. 整体代码

//迭代器部分
 template<class T,class ref>
 struct __list_iterator
 {
     list_node<T>* _node;
     __list_iterator(list_node<T>* node)
         :_node(node)
    

     ref& operator*()
     {
         return _node->_val;
     }
     __list_iterator<T,ref>& operator++()
     {
         _node = _node->_next;
         return *this;
     }
     __list_iterator<T, ref>& operator++(int)
     {
         __list_iterator<T, ref>(*this);
         _node = _node->_next;
         return *this;
     }
     __list_iterator<T, ref>& operator--()
     {
         _node = _node->_prev;
         return *this;
     }
     __list_iterator<T, ref>& operator--(int)
     {
         __list_iterator<T, ref>(*this);
         _node = _node->_prev;
         return *this;
     }

     bool operator!=(const  __list_iterator<T, ref>& node)
     {
         return _node != node._node;
     }
 };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

//list中的public命名部分
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T, const T&,const T*>const_iterator; 
1
2
3