SGISTL源码剖析——list容器

SGI STL源码剖析——list容器

list定义构造和初始化迭代器和元素操作 list定义

链表结构
list也是常用的容器，比起vector的连续线性空间，list是链表结构，既然是链表结构，必然存在经典的链表节点数据结构，

// 链表结构基类，双向链表struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev;};// 真正使用的链表节点template struct _List_node : public _List_node_base { _Tp _M_data;};

迭代器
vector使用的是原生指针，因此迭代器直接在vector中定义，list使用的是链表结构，其节点不是空间连续的，因此专门定义了迭代器。

struct _List_iterator_base {typedef size_t size_type;typedef ptrdiff_t difference_type;// list的迭代器类型是Bidirectional Iteratorstypedef bidirectional_iterator_tag iterator_category;// 原生指针，指向节点，用的是链表节点基类指针，成员变量// 迭代器再list中typedef定义，然后正是通过这个成员变量去访问迭代器指向的节点 _List_node_base* _M_node;// 构造函数_List_iterator_base(_List_node_base* __x) : _M_node(__x) {}_List_iterator_base() {}void _M_incr() { _M_node = _M_node->_M_next; }void _M_decr() { _M_node = _M_node->_M_prev; }// 重载比较运算符bool operator==(const _List_iterator_base& __x) const { return _M_node == __x._M_node;}bool operator!=(const _List_iterator_base& __x) const { return _M_node != __x._M_node;}}; // 继承迭代器基类templatestruct _List_iterator : public _List_iterator_base {// 迭代器typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;// 类名typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;// _Tp,_Tp&,_Tp* 对应value_type, reference和pointertypedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;// 链表节点typedef _List_node<_Tp> _Node;// 构造函数函数，直接调用基类构造函数初始化节点_List_iterator(_Node* __x) : _List_iterator_base(__x) {}_List_iterator() {}// 复制构造函数_List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {} // 解引用，获取data，从迭代器获取节点数据reference operator*() const { return ((_Node*) _M_node)->_M_data; }#ifndef __SGI_STL_NO_ARROW_OPERATOR// 间接引用，T->m使得可以像指针一样使用对象访问成员变量pointer operator->() const { return &(operator*()); }#endif //前置++运算符重载，实际上是改变迭代器内部指向的节点_M_node_Self& operator++() { this->_M_incr();return *this;}// 后置++运算符重载_Self operator++(int) { _Self __tmp = *this;this->_M_incr();return __tmp;}// 重载--运算符_Self& operator--() { this->_M_decr();return *this;}_Self operator--(int) { _Self __tmp = *this;this->_M_decr();return __tmp;}};

list容器结构定义
list不仅仅是一个双向链表，还是一个环状链表，这样设计的好处在于可以轻易完成迭代器的几个函数。
同vector一样，list容器有一个基类，负责空间配置，

template class _List_base {public:// 配置器typedef _Alloc allocator_type;allocator_type get_allocator() const { return allocator_type(); }// 构造函数，无实际参数，创建一个节点_List_base(const allocator_type&) {_M_node = _M_get_node();_M_node->_M_next = _M_node;_M_node->_M_prev = _M_node;}// 析构函数，clear析构对象同时回收空间~_List_base() {clear();//clear完以后还有一个node没有释放，在list中node是中国指向尾端的一个空白节点//所以，根据node作为入口，clear所有节点，然后再释放掉尾端的这个空白节点_M_put_node(_M_node);}void clear();protected:// simple_alloc 是 SGI STL 的空间配置器，以元素大小为配置单位typedef simple_alloc<_List_node<_Tp> , _Alloc> _Alloc_type;// 基类的这个函数值配置空间，不构造对象// 配置一个节点的空间，返回这个节点的内存位置；空间配置器返回的都是void*, 根据返回类型进行转换_List_node<_Tp> * _M_get_node() { return _Alloc_type::allocate(1); }// 释放一个节点的空间，空间配置器的操作void _M_put_node(_List_node<_Tp> * __p) { _Alloc_type::deallocate(__p, 1); } protected://list中的数据，比如传入int，实例化_List_node，就是一个链表节点，外层对list的方位实际上就是对//_M_node的访问，做了一层封装 _List_node<_Tp> * _M_node;};//clear的作用是通过当前节点，遍历整个环形链表，析构对象和释放空间template void _List_base<_Tp,_Alloc>::clear() {_List_node<_Tp> * __cur = (_List_node<_Tp> *) _M_node->_M_next;while (__cur != _M_node) { _List_node<_Tp> * __tmp = __cur; __cur = (_List_node<_Tp> *) __cur->_M_next; //析构对象 _Destroy(&__tmp->_M_data); //回收空间 _M_put_node(__tmp); } //最后一个节点先把其前驱和后驱设为自己_M_node->_M_next = _M_node;_M_node->_M_prev = _M_node;}

上面这个基类的实现，值得注意的就是list中的_M_node，永远指向尾端的一个空白节点。然后是实际的list容器类，继承上面的基类，

template class list : protected _List_base<_Tp, _Alloc> {__STL_CLASS_REQUIRES(_Tp, _Assignable);// 基类名称typedef _List_base<_Tp, _Alloc> _base;protected:// 不知道有啥用typedef void* _Void_pointer;public:// 迭代器所指对象类型 typedef _Tp value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef _List_node<_Tp> _Node;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef typename _base::allocator_type allocator_type;allocator_type get_allocator() const { return _base::get_allocator(); }public:// 注意这里和vector的不同，list的迭代器就是上面定义的那个迭代器类型typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;protected:// 创建一个节点，含有初始值_Node* _M_create_node(const _Tp& __x){// 配置节点空间回，注意基类_M_get_node()是返回的_List_node<_Tp> *_Node* __p = _M_get_node();__STL_TRY {//在配置好的节点空间中构造对象_Construct(&__p->_M_data, __x);}__STL_UNWIND(_M_put_node(__p));return __p;}// 创建一个节点，不含有初始值_Node* _M_create_node(){_Node* __p = _M_get_node();__STL_TRY {_Construct(&__p->_M_data);}__STL_UNWIND(_M_put_node(__p));return __p;}public://构造函数 explicit list(const allocator_type& __a = allocator_type()) : _base(__a) {}

构造和初始化

先来看list提供的构造函数，

explicit list(const allocator_type& __a = allocator_type()) : _base(__a) {}//接受元素数量n，初始值caluelist(size_type __n, const _Tp& __value, const allocator_type& __a = allocator_type()) : _base(__a){ insert(begin(), __n, __value); }// 接受元素n，不指定初值，用类型Tp的默认构造函数explicit list(size_type __n): _base(allocator_type()){ insert(begin(), __n, _Tp()); }

这两种是最常用的，直接创建一个list容器或者指定元素数量去创建。和vector一样，list也接受迭代器初始化，

template list(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()): _base(__a){ insert(begin(), __first, __last); }

然后还有复制构造函数，

list(const list<_Tp, _Alloc>& __x) : _base(__x.get_allocator()){ insert(begin(), __x.begin(), __x.end()); }

可以看到，list的构造全部通过insert完成，那我们来看一下这个insert函数，

// 接受一个位置和一个值，在指定位置前面插入一个节点iterator insert(iterator __position, const _Tp& __x) {// 新建一个节点_Node* __tmp = _M_create_node(__x);// 插入到当前节点的前方，注意迭代器__position，迭代器类中有声明一个成员变量_M_node，正是迭代器当前// 指向的链表节点，就是这个变量将迭代器和list关联起来,这里的操作其实就是一个双向链表插入节点__tmp->_M_next = __position._M_node;__tmp->_M_prev = __position._M_node->_M_prev;__position._M_node->_M_prev->_M_next = __tmp;__position._M_node->_M_prev = __tmp;return __tmp;}

// 接受插入位置，同时接受两个迭代器，可以用这两个迭代器范围的值去插入void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {//判断迭代器参数是否是整形typedef typename _Is_integer<_InputIterator>::_Integral _Integral;_M_insert_dispatch(__pos, __first, __last, _Integral());}//看下非整形版本的实现template void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, __false_type){//pos位置处连续执行insert，每次插入的值就是当前迭代器的值//优于直接取值，可以看到我们可以使用其他容器的迭代器来初始化listfor ( ; __first != __last; ++__first)insert(__position, *__first);}

// 批量插入，接受插入位置、插入元素数量以及值void insert(iterator __pos, size_type __n, const _Tp& __x){ _M_fill_insert(__pos, __n, __x); }void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x);{for ( ; __n > 0; --__n)insert(__position, __x);}

可以看到，list因为不用像vector那样考虑预备空间是否充足，因此insert非常简单，多个版本的insert也都是以第一个版本为基础，构造就是直接调用相应的insert。insert的基础操作就是双向链表插入一个节点，值得注意的是迭代器是如何访问链表节点的。

迭代器和元素操作

访问操作
前面说到，list中定义了一个_List_node<_Tp> * _M_node，list本身是一个双向环形链表结构，这个node呢则是一直指向链表尾端的一个空白节点，利用环形链表的特性，以下几个函数就很好实现，

// _M_node是末尾空白节点，它的next才是头节点iterator begin() { return (_Node*)(_M_node->_M_next); }// end就正好是这个空白节点了const_iterator end() const { return _M_node; }// 因为list至少有一个空节点，环形链表判断是否为空就是看头节点是否指向自己bool empty() const { return _M_node->_M_next == _M_node; }size_type size() const {size_type __result = 0;distance(begin(), end(), __result);return __result;}// 链表首个元素reference front() { return *begin(); }// 链表最后一个元素reference back() { return *(--end()); }// 相比vector，swap只需要交换节点_M_node，_M_node即可找到整个链表void swap(list<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); }

元素操作
1、assign
和vector一样，list支持assign操作，assign比起insert，它不存在指定插入位置，相当于重新填充整个容器，所以会清空容器原来的内容。assign接受的参数是迭代器，

template void assign(_InputIterator __first, _InputIterator __last) {typedef typename _Is_integer<_InputIterator>::_Integral _Integral;_M_assign_dispatch(__first, __last, _Integral());}template list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) {iterator __first1 = begin();iterator __last1 = end();for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)//循环复制迭代器指向的节点 *__first1 = *__first2;if (__first2 == __last2)//说明first2和last2形成的区间小于原来的容量，因此清空原来多余的部分 erase(__first1, __last1);else//否则执行插入 insert(__last1, __first2, __last2);}

assign也可以接受n个值

void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }void _M_fill_assign(size_type __n, const _Tp& __val) {iterator __i = begin();for ( ; __i != end() && __n > 0; ++__i, --__n) *__i = __val;if (__n > 0) insert(end(), __n, __val);else erase(__i, end());}

2、insert
在上面构造中，insert也基本说的差不多了

3、push_back等
list同样支持push_back、pop_back操作，比起vector，list还支持push_front、 pop_front

//直接调用一次insertvoid push_back(const _Tp& __x) { insert(end(), __x); }void push_front(const _Tp& __x) { insert(begin(), __x); }// 调用erase删除头节点void pop_front() { erase(begin()); }// 删除尾节点，注意要改变尾节点的指向，因为erase只负责删除节点void pop_back() { iterator __tmp = end();erase(--__tmp);}

至于erase的实现，同样是两个版本

// 移除iterator所指节点，返回删除节点的下一个迭代器iterator erase(iterator __position) {_List_node_base* __next_node = __position._M_node->_M_next;_List_node_base* __prev_node = __position._M_node->_M_prev;_Node* __n = (_Node*) __position._M_node;__prev_node->_M_next = __next_node;__next_node->_M_prev = __prev_node;_Destroy(&__n->_M_data);_M_put_node(__n);//调用迭代器的构造函数返回return iterator((_Node*) __next_node);}iterator erase(iterator __first, iterator __last){while (__first != __last)erase(__first++);return __last;}

vector还支持remove、unique、reverse，值得注意的是，list由于使用了双向迭代器，因此不能使用STL算法sort和merge，因此list实现了自己的sort和merge

template void list<_Tp, _Alloc>::sort(){// 使用 size() == 0 || size() == 1来判断，虽然也可以，但是比较慢// 注意链表一个节点代表list是空的，链表两个节点代表list是只有一个节点if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {list<_Tp, _Alloc> __carry;list<_Tp, _Alloc> __counter[64];int __fill = 0;while (!empty()) {__carry.splice(__carry.begin(), *this, begin());int __i = 0;while(__i < __fill && !__counter[__i].empty()) {__counter[__i].merge(__carry);__carry.swap(__counter[__i++]);}__carry.swap(__counter[__i]); if (__i == __fill) ++__fill;} for (int __i = 1; __i < __fill; ++__i)__counter[__i].merge(__counter[__i-1]);swap(__counter[__fill-1]);}}

list的提供merge函数，内部实现其实就是有序链表的合并，

// 合并两个有序listtemplate void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x){iterator __first1 = begin();iterator __last1 = end();iterator __first2 = __x.begin();iterator __last2 = __x.end();while (__first1 != __last1 && __first2 != __last2)if (*__first2 < *__first1) {iterator __next = __first2;transfer(__first1, __first2, ++__next);__first2 = __next;}else++__first1;if (__first2 != __last2) transfer(__last1, __first2, __last2);}

从上面可以看到，list内部有一个非常重要的实现，transfer，其作用是将连续范围的元素前移到某个指定位置之前，

// 元素搬移 [first, last)搬移到position之前void transfer(iterator __position, iterator __first, iterator __last) {if (__position != __last) {//list是一个双向链表结构，下面的操作其实就是移动链表节点的操作，画个图很好理解//首先改变next指针__last._M_node->_M_prev->_M_next = __position._M_node;__first._M_node->_M_prev->_M_next = __last._M_node;__position._M_node->_M_prev->_M_next = __first._M_node; //然后改变prev指针_List_node_base* __tmp = __position._M_node->_M_prev;__position._M_node->_M_prev = __last._M_node->_M_prev;__last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp;}}

splice对transfer进行封装，对外提供，

// 将另外一个链表连接到当前链表指定的位置之前void splice(iterator __position, list& __x) {if (!__x.empty()) this->transfer(__position, __x.begin(), __x.end());}// 将i所指元素接合于 position所指位置之前。position和 i可指向同一个listvoid splice(iterator __position, list&, iterator __i) {iterator __j = __i;++__j;// 构造一个first和last区间if (__position == __i || __position == __j) return;this->transfer(__position, __i, __j);}//将 [first,last)内的所有元素接合于 position所指位置之前。// position和[first,last)可指向同一个 list，//但 position不能位于[first,last)之内。void splice(iterator __position, list&, iterator __first, iterator __last) {if (__first != __last) this->transfer(__position, __first, __last);}

好了，list的代码就读到这里，list比起vector实现上有一些不同，特别是迭代器的使用要非常注意，list本质上是链表结构，所以学习list各种接口的实现对我们理解链表有很大帮助。特别是list本身使用环形双向链表，使得首尾方位非常方便。另外，也要注意list内部实现的transfer，是list很多操作的基石。