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 Iterators
typedef 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;
}
};
// 继承迭代器基类
template
struct _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和pointer
typedef _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容器有一个基类，负责空间配置，
templateclass _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，初始值calue
list(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也接受迭代器初始化，
templatelist(_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，每次插入的值就是当前迭代器的值
//优于直接取值，可以看到我们可以使用其他容器的迭代器来初始化list
for ( ; __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接受的参数是迭代器，
templatevoid 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
//直接调用一次insert
void 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
templatevoid 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函数，内部实现其实就是有序链表的合并，
// 合并两个有序list templatevoid 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可指向同一个list
void 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很多操作的基石。
