说明:本文仅供学习交流,转载请标明出处,欢迎转载!
list的底层采用数据结构是环形的双向链表, 相对于vector容器,list容器插入和删除操作付出的代价要比vector容器小得多,但是list带有链表的天生弱点,就是不支持随机访问。从内置的迭代器角度分析,vector容器对应的迭代器为随机访问迭代器,而list容器内置的迭代器则为双向迭代器。
我们也知道,STL中提供的很多算法都是基于随机访问迭代器的,如sort(b,e)函数,其所使用的迭代器就是随机访问迭代器,所以,list不能使用这类算法函数。为此,STL又在list容器中内置了其特有的算法,这些算法都是根据list容器的特点定身制造的。
所以,要设计一个list容器,我们需要考虑这些问题:
(1)结点设计。学过数据结构的都知道,链表就是将一个一个 的结点通过指针链接起来,结点是构成链表的元素。所以首先得考虑双链表结点的设计,对应的设计代码框架如下:
<pre name="code" class="cpp">/********底层结点的定义**********/ template<class T> struct _list_node { typedef _list_node<T> node_type;//指向本类结点的指针 node_type *pre;//前驱指针 node_type *next;//后继指针 T data; };
(2)迭代器的设计。由于list容器对应的迭代器是双向迭代器,既然是双向迭代器,我们就必须为该迭代器提供++、--操作。而又由于链表并不一定是连续的空间分配,所以不能直接对原生的指针做++、--的操作,而应该利用迭代器对原生指针做封装,然后对迭代器重载++、--的操作,其中迭代器的++对应原生指针的p=p->next,迭代器的--则对应原生指针的p=p->pre。
/*******list迭代器的定义**********/ template<class T,class Ref=T &, class Ptr=T*> struct _list_iterator { typedef _list_node<T>* link_type;//指向底层结点的指针类型 link_type p;//p表示一个原生指针,迭代器是一个智能指针,是对p的一个包装 /******下面定义迭代器的一个常用属性*******/ typedef T value_type;//元素类型 typedef Ptr pointer;//指针类型 typedef Ref reference;//引用类型 typedef ptrdiff_t difference_type;//指针差值类型 typedef bidirectional_iterator_tag iterator_category;//标记类型,属于双向迭代器,不支持随机访问 typedef size_t size_type;//大小类型 /******下面定义一个智能指针的常用操作**********/ typedef _list_iterator<T,T&,T*> iterator_type;//名字太长了,给迭代器类定义一个别名 _list_iterator(){}//无参构造函数 _list_iterator(link_type p1):p(p1){};//单形参构造函数,参数为原生指针 _list_iterator(const iterator_type & iter):p(iter.p){};//复制构造函数 bool operator==(iterator_type& iter)const;//判断两个迭代器的原生指针是否相等,即this->p是否等于iter.p bool operator!=(iterator_type& iter)const;//跟上相反 reference operator*()const;//解引用,返回p->data pointer operator->()const;//箭头操作符,返回&(p->data) /******下面定义作为一个双向容器的应有操作********/ iterator_type operator++();//定义++前置操作,++iter iterator_type operator++(int);//定义++后置操作,iter-- iterator_type operator--();//定义--前置操作,--iter iterator_type operator--(int);//定义--后置操作,iter-- };
(3)list容器的设计。list容器除了内部封装一个特殊的迭代器外,还需要提供一些特定算法,因为list容器的对象很多STL提供的算法都不能使用,所以需要其自身提供封装好相应的函数。
/***************list容器的定义*************************/ template<class T,class Alloc=alloc> class list { protected: typedef _list_node<T> node_type;//定义底层结点类型别名 typedef _list_node<T>* link_type;//连接底层结点的指针类型别名 typedef simple_alloc<Node_type,Alloc> node_allocator;//定义结点空间分配器类 Node_type empty_Node;//定义一个带空节点值的结点 void init();//创建一个空环形双向链表 public: /**************定义公有访问属性****************/ typedef T value_type;//底层结点内含的data所对应的数据类型 typedef value_type* pointer;//指针类型 typedef value_type& reference;//引用类型 typedef ptrdiff_t difference_type;//迭代器差值类型 typedef size_t size_type;//大小类型 typedef _list_iterator<T,T&,T*> iterator;//迭代器类型 typedef const iterator const_iterator;//指向常量的迭代器类型 /*************构造函数/析构函数**************/ list();//无参构造函数,仅调用init()来初始化链表 list(InputIterator b,InputIterator e);//用[b,e)去初始化容器 list(size_type n);//创建一个含有n个元素的容器 list(size_type n,const T &t);//用n个值为t的元素去创建容器 ~list();//析构函数 /*************插入操作********************/ void push_back(const T & t);//后插入 void push_front(const T & t);//前插入 iterator insert(interator iter,const T &t);//在iter前插入值t的元素,返回新添加元素的迭代器 void insert(iterator iter,size_type n,const T &t);//在iter前插入n个值为t的元素 void insert(iterator iter,iterator b,iterator e);//在iter前插入[b,e)范围的元素 /***********删除操作*********************/ iterator erase(iterator iter);//删除iter所指向的元素,返回所删除元素的下一个元素对应的迭代器 iterator erase(iterator b,iterator e);//删除[b,e)范围内的元素,返回原先e void clear();//删除容器内的所有元素 void pop_back();//删除容器内最后一个有效的元素 void pop_front();//删除容器内第一个有效的元素 /***********大小操作*********************/ size_type size()const;//返回容器内元素的个数 size_type max_size()const;//返回容器可容纳的最多元素的个数 bool empty()const;//判断容器是否为空 void resize(size_type n);//将容器的大小设置为n void resize(size_type n,T t);//将容器的大小设置为n,若需要需要新添加新的元素之,则其值为t /***********访问操作*******************/ iterator begin();//返回头指针 iterator end();//返回末端元素的下一个位置 iterator rbegin();//返回最后一个元素 iterator rend();//返回头指针的前一个位置 reference front();//返回第一个元素的引用 reference back();//返回最后一个元素的引用 /**********list特有的算法操作************/ void remove(const T& t);//删除之为t的元素 void remove_if(bool preFun);//将满足特定条件的值删除 void unique();//将容器中重复的元素删除,只留下第一次出现的那个元素集 void unique(bool preFun);//将满足条件的重复值删除 void reverse();//将容器的元素逆转,通过依次将尾部的元素剪切插入到首部 void sort();//将容器内的元素排序,内部是采用归并排序 /////使用merge函数必须保证连个list是有序的,否则会运行时出错,默认为升序,也可以自己定义降序/////////////// typedef list<T,alloc> List;//定义本类的类型别名,太长了 void merge(List &list2);//将list2中的元素剪切后再归并待本链表,升序 void merge(List &list2,int cmp);//将list归并到本链表,cmp指定排序方式 void splice(iterator iter,List list2);//将list2的元素剪切到本链表中的iter之前,注意:list2不同于*this void splice (iterator iter,List & list2,iterator iter2);//将list2中iter2指向的那一个元素(只有1个哈)剪切到本链表的iter之前,list2可以等于*this void splice(iterator iter,List & list2,iterator b,iterator e);//将list2中的[b,e)内的元素剪切到本链表的iter之前,list可以等于*this };
上面的代码中,指的一提是sort函数,该sort函数采用的是归并排序的非递归算法,还有就是reverse函数,reverse函数的实现思路是将原链表中的结点从头到尾依次剪切到头部,这样就可以将链表逆转。
参考文献
[1]《C++primer 第4版》
[2]《STL源码剖析 侯捷》
STL之list容器的实现框架,布布扣,bubuko.com
原文:http://blog.csdn.net/jxh_123/article/details/32722845