1、STL

库函数的设计第一位是通用性，模板为其提供了可能；标准模板库中的所有算法和容器都是通过模板实现的。

STL(标准模板库)是 C++最有特色，最实用的部分之一。

STL整个架构模型如下：

2、list(双向循环链表)

调用STL系统的#include<list>,用系统的双向循环链表结构处理：

#include<iostream>#include<list>//调用系统的list,双向循环链表结构usingnamespacestd;intmain(void){list<int>mylist;for(inti=1;i<=10;i++){mylist.push_back(i);//接口，末尾增加}list<int>::iteratorit=mylist.begin();//迭代器，while(it!=mylist.end()){cout<<*it<<"-->";//打印内部数字++it;//每次往后移一个}cout<<"NULL"<<endl;}

3、list部分源码实现剖析

list模型如下：

阅读其源代码，分析了部分的功能：

#ifndef_LIST_H//条件宏编译，避免重复定义#define_LIST_H#include<assert.h>//断言引入的头文件#include<malloc.h>//申请空间所引入的头文件template<class_Ty>//此处先不涉及空间置配器classlist{//list类public:struct_Node;typedefstruct_Node*_Nodeptr;//指向节点的指针类型struct_Node{//_Node这个是节点类型_Nodeptr_Prev;//前驱节点_Nodeptr_Next;//后继节点_Ty_Value;//模板数据类型};struct_Acc{//定义_Acc这个类型typedefstruct_Node*&_Nodepref;//指向节点类型指针的引用typedef_Ty&_Vref;//这个数据类型的引用static_Nodepref_Next(_Nodeptr_P)//静态方法，返回值是节点指针的引用，参数是指向节点的指针{return((_Nodepref)(*_P)._Next);}//：*_P得到这个节点，()强制类型转换的优先级没有.高，所以此时先取_Next，在进行强制类型转换的工作，返回一个指向节点指针的引用。static_Nodepref_Prev(_Nodeptr_P){return((_Nodepref)(*_P)._Prev);}static_Vref_Value(_Nodeptr_P){return((_Vref)(*_P)._Value);}};public://以下的类型是_A这个类下面的类型，_A这个类在空间置配器中定义typedeftypename_A::value_typevalue_type;typedeftypename_A::pointer_typepointer_type;typedeftypename_A::const_pointer_typeconst_pointer_type;typedeftypename_A::reference_typereference_type;typedeftypename_A::const_reference_typeconst_reference_type;typedeftypename_A::size_typesize_type;//这个类型其实就是size_tprivate:_Nodeptr_Head;//指向头结点的指针size_type_Size;//有几个节点个数};#endif

以上代码主要是struct _Acc这个类的理解好至关重要！！！

下面就是构造函数和析构函数了

public:explicitlist():_Head(_Buynode()),_Size(0)//explicit显示调用此构造函数，给头一个指向，刚开始0个{}~list(){//释放空间和空间配置器有关，在现阶段先不关心。erase(begin(),end());//调用开始，结束函数释放空间；_Freenode(_Head);//释放头；_Head=0,_Size=0;//都赋空；}..................................................protected:_Nodeptr_Buynode(_Nodeptr_Narg=0,_Nodeptr_Parg=0)//返回值为节点指针类型，参数都为节点指针类型，传的应该是后继和前驱指针，默认都为0；{_Nodeptr_S=(_Nodeptr)malloc(sizeof(_Node));//申请一个节点空间，把地址给了_S;assert(_S!=NULL);//所申请的空间存在的话_Acc::_Next(_S)=_Narg!=0?_Narg:_S;//给新生成的节点的_Next赋值_Acc::_Prev(_S)=_Parg!=0?_Parg:_S;//给新生成的节点的_Prev赋值return_S;//返回这个新生成节点的地址}//这个_Buynode函数的意思是：当创建的是第一个节点时，自己一个节点连向自己，构成双向循环链表，其他的情况则是插入到两个节点之间！！！........................................................

接下来写迭代器：

public:classiterator{//迭代器也是一个类，是list的内部类；public:iterator(){}iterator(_Nodeptr_P):_Ptr(_P){}public:iterator&operator++(){//++it,前++的运算符重载_Ptr=_Ptr->_Next;//因为是链表结构，内部实现迭代器的++,是进行了++的重载；使其指针的移动到下一个节点；return*this;//返回的是这个节点的引用。}iteratoroperator++(int)//it++{_Itit(_Ptr);//先保存原先节点_Ptr=_Ptr->_Next;//移到下一个节点returnit;//返回原先的；}iteratoroperator--(int);//类似iterator&operator--();reference_typeoperator*()const//对*的重载{return_Ptr->_Value;}//返回这个节点的_Value值pointer_typeoperator->()const//对->的重载//{return&_Ptr->_Value;}自己实现的，->的优先级高于&，所以将_Value的地址返回{return(&**this);}//系统中的，this是迭代器的地址，*this是迭代器对象，再来一个*时，调用上面的(对*的重载)，此时还是返回_Value的地址。public:booloperator!=(constiterator&it)const//迭代器对象的比较{return_Ptr!=it._Ptr;}//比的是指向节点的指针；public:_Nodeptr_Mynode()const//得到当前节点的地址；{return_Ptr;}protected:_Nodeptr_Ptr;//迭代器的数据成员是一个指向节点的指针。};typedefiterator_It;//_It就是迭代器类型public:iteratorbegin(){returniterator(_Acc::_Next(_Head));}//begin()函数得到头结点的后继(第一个有效节点的地址)iteratorbegin()const;iteratorend(){returniterator(_Head);}//end()函数得到的是头结点(也就是最后一个节点的后继地址);public://前面的已经讲的很清楚了，后面的都是调用即可；voidpush_back(const_Ty&x){insert(end(),x);}voidpush_front(const_Ty&x){insert(begin(),x);}public:iteratorinsert(iterator_P,const_Ty&_X=_Ty()){_Nodeptr_S=_P._Mynode();//得到节点地址_Acc::_Prev(_S)=_Buynode(_S,_Acc::_Prev(_S));//下面的三句调用前面的函数_Buynode()实现了插入功能;_S=_Acc::_Prev(_S);_Acc::_Next(_Acc::_Prev(_S))=_S;++_Size;//个数加1returniterator(_S);}voidinsert(iterator_P,size_type_M,const_Ty&_X)//插入个数_M个，以下几个调用前面函数；{for(;0<_M;--_M)insert(_P,_X);}voidinsert(iterator_P,const_Ty*_F,const_Ty*_L)//区间的插入{for(;_F!=_L;++_F)insert(_P,*_F);}voidinsert(iterator_P,_It_F,_It_L)//迭代器的插入{for(;_F!=_L;++_F)insert(_P,*_F);}/*voidpush_back(const_Ty&x)//尾随增加最后{_Nodeptr_S=_Buynode(_Head,_Acc::_Prev(_Head));//实现插入功能_Acc::_Value(_S)=x;_Acc::_Next(_Acc::_Prev(_Head))=_S;_Acc::_Prev(_Head)=_S;_Size++;//最后加1}iteratorerase(iterator_P)//删除空间{_Nodeptr_S=(_P++)._Mynode();_Acc::_Next(_Acc::_Prev(_S))=_Acc::_Next(_S);_Acc::_Prev(_Acc::_Next(_S))=_Acc::_Prev(_S);--_Size;//个数减少1个return_P;}iteratorerase(iterator_F,iterator_L)//调用函数，删除区间{while(_F!=_L)erase(_F++);return_F;}voidclear()//清除所有空间{erase(begin(),end());}#endif

4、总结：

(1)、迭代器的本质有了了解，是一个内部类，它将是一个对象，内部数据成员是一个指向节点的指针；

(2)、迭代器对->的重载返回的是节点内部数据的地址，而不是节点的地址；

(3)、迭代器对每种数据结构的实现均不相同，(Stack, queue, list...........)

(4)、空间配置器：对所有的数据结构而言，只有一份，

作用：申请，释放空间，构造，析构对象；