STL之list 剖析源码中的_Acc结构，迭代器，以及很赞的函数

一、_Buynode 的妙处

源码中的_Buynode函数                 是用来申请节点

_Nodeptr _Buynode(_Nodeptr _Narg=0,_Nodeptr _Parg=0)

这个函数设置了两个参数，同时给了两个默认值（空指针），这个写法咋一看感觉很怪，但细细品味之后就会发现很妙

 这个_Buynode有两个功能

1、申请节点，对自己进行循环

2、指向自己该指向的前驱和后继，这样的话也就是说在申请节点的同时就会把前驱和后继连接上

push_back函数实现

_Buynode函数实现的过程

 这里对_Buynode函数进行了好几次的升级，形式看起来就是很高级

二、_Acc结构

_Acc就是一个结构体

struct _Acc
		{
			 typedef _Node*&   _Nodepref;//节点指针的引用类型
			 typedef _Ty&    _Vref;      //值的引用类型
			//1、使用静态，被所以对象共有
			//2、不需要对象，使用类名就行了
			static _Nodepref _Next(_Nodeptr _P)
			{
				return (_Nodepref)(_P->_Next);
			}
			static _Nodepref _Prev(_Nodeptr _P)
			{
				return (_Nodepref)(_P->_Prev);
			}
			static _Vref _Value(_Nodeptr _P)
			{
				return (_Vref)(_P->_Value);
			}
		};

_Acc的优点：

1、代码颜值升级

​
    _Nodeptr _Buynode(_Nodeptr _Narg=0, _Nodeptr _Parg=0)
	{
          _Nodeptr _S = (_Nodeptr)malloc(sizeof(struct _Node))
          //再利用Acc进行颜值的提升
			_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
			_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;
	        return _S;
	}

​

2、不直接队成员进行操作，不会暴露节点成员的属性

3、_Acc里面的的函数是静态的，只需要类名就能去调用，不需要对象，直接用_Acc::_Next(_S)就能调用

三、iterator  迭代器

//遍历  每一个元素都要访问，且只访问一次

//迭代

迭代器的形式：

 在list类中定义了一个类 iterator    (类中类)

那么在使用他去实例化对象的时候，格式就是：

bit::list<int>::iterator it;

迭代器里面有两个主要的函数：

这两个函数返回值是迭代器类型

 编写begin和end的时候要延续【  ）前闭后开的思想

 使用iterator    

这里的报错是因为系统不知道！=是怎么进行的，遇到这种问题，我们就需要运算符重载来进行解决

 我们这时候就可以来进行输出数据了

//1-->2-->3
	bit::list<int>::iterator it=mylist.begin();
	while (it != mylist.end())
	{
		cout << *it << "-->";
		++it;
	}
	cout << "Over" << endl;

 来看看内部重载 ++和 * 的实现

iterator& operator++()
			{
				_Ptr=_Acc::_Next(_Ptr);
				return *this;
			}
			_Ty& operator*()
			{
				return _Acc::_Value(_Ptr);
			}

运行一下：

可以发现成功输出了   nice！

利用iterator迭代器实现插入

insert（）插入函数

再来验证代码实现

 可以发现确实是在第二个位置插入了20

insert基础上 来实现push_back

void push_back(const _Ty& x)
		{
			insert(end(), x);
		}

 在insert技术上实现push_front

void push_front(const _Ty& x)
		{
			insert(begin(), x);
		}

四、关于erase删除函数

我们可以先来看看源码中的erase函数是怎样进行定义的

iterator erase(iterator _P)
		{
			_Nodeptr _S = (_P++)._Mynode();
			_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
			_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
			//使用空间配置器
			//allocator.destroy(&_Acc::_Value(_S));
			//alloctor.destroy(&_Acc::_Value(_S));
			_Freenode(_S);
			--_Size;
			return (_P);
		}

删除一个节点其实原理很简单，在数据结构的学习里我们以及很熟悉了，

源码这里用了一个过河拆桥的方法

 先定义一个节点指针指向_P原来的位置，在把_P向后移动一位，接着就把_S所在的节点给free了

函数返回的是_P位置的迭代器，所以erase函数是删除当前位置的节点，

这个函数有一个迭代器类型的返回值，值是下一个节点构造出来的迭代器类型。

1、基于以上的信息，那么erase（lt.end()）就是错误的使用，这样用相当于把头节点给删除了

 要想真正删除最后一个节点，就要先把迭代器向前调一个位置

 2、迭代器失效问题

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了，并且失效的只是指向该节点的迭代器，其他迭代器还是正常的

void TestListIterator1()
{
 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 auto it = l.begin();
 while (it != l.end())
 {
 // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值
 l.erase(it); 
 ++it;
 }
}