list概述
相较于vector的连续线性空间,list就复杂很多，它的好处是每次插入或者删除一个元素，就配置或释放一个空间，因此，list对于空间的运用有绝对的精准，一点也不浪费
list的节点
以下是STLlist的节点结构:
template <class T>
struct _list_node
{
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
};
list的迭代器
由于STL list是一个双向链表，迭代器必须具备前移，后移的能力，所以list提供的是Bidirectional iterators
list有一个重要性质:插入操作和接合操作都不会造成原有的list迭代器失效，list的元素删除操作也只有“指向被删除元素”的那个迭代器失效
list迭代器的设计
template <class T,class Ref,class Ptr>
struct _list_iterator
{
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,Ref,Ptr> self;
typedef bidirection_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef _list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node;//迭代器内部要有一个普通指针，指向list的节点
//constructor
_list_iterator(link_type x):node(x) { }
_list_iterator() { }
_list_iterator(const iterator& x):node(x.node) { }
bool operator==(const self& x) const { return node==x.node;}
bool operator!=(const self& x) const { return node!=x.node;}
reference operator*() const { return (*node).data;}
pointer operator->() const { return &(operator*());}
self& operator++()
{
node=(link_type)((*node).next);
return *this;
}
self operator++(int)
{
self tmp=*this;
++*this;
return tmp;
}
self& operator--()
{
node=（link_type)((*node).prev);
return *this;
}
self operator--(int)
{
self tmp=*this;
--*this;
return tmp;
}
};
list的数据结构
SGI list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针，便可以完整表现整个链表
template <class T,class Alloc =alloc>
class list
{
protected:
typedef _list_node<T> list_node;
pubilc:
typedef list_node* link_type;
protected:
link_type node;//只要一个指针，便可表示整个环状双向链表
};
如果让指针node指向刻意置于尾端的一个空白节点,node便能符合STL对于“前闭后开”区间的要求，成为last迭代器
iterator begin() { return (link_type)((*node).next);}
iterator end() { return node;}
bool empty() const { return node->next==node;}
size_type size() const
{
size_type result = 0;
distance(begin(),end(),result);
return result;
}
//取头节点的内容
reference front() { return *begin();}
reference back() { return *(--end()); }
list的构造与内存管理
list缺省使用alloc作为空间配置器，并据此另外定义了一个list_node_allocator,为的是更方便地以节点大小为配置单位：
template <class T,class Alloc=alloc>
class list
{
protected:
typedef _list_node<T> list_node;
//专属之空间配置器，每次配置一个结点
typedef simple_alloc<list_node,Alloc> list_node_allocator;
};
以下四个函数，分别用来配置，释放，构造，销毁一个节点：
protected:
//配置一个节点并传回
link_type get_node() { return list_node_allocator::allocate();}
//释放一个节点
void put_node(link_type p) { list_node_allocator::deallocate(p);}
//产生一个节点，带有元素值
link_type create_node(const T& x)
{
link_type p=get_node();
construct (&p->data,x);
return p;
}
//摧毁一个节点
void destroy_node(link_type p)
{
destroy(&p->data);
put_node(p);
}
list提供有很多constructors，其中一个是default constructor,允许我们不指定任何参数做出一个空的list出来:
pubilc:
list() { empty_initialize(); }
protected:
void empty_initialize()
{
node=get_node();
node->next=node;//令node头尾指向自己，不设元素值
node->prev=node;
}
当我们以push_back()将新元素插入于list尾端时，此函数内部调用insert()
void push_back(const T& x) { insert(end(),x);}
insert()是一个重载函数，有多种形式，其中最简单的一种如下，符合以上需求，首先配置并构造一个节点，然后在尾端进行适当的指针操作，将新节点插入进去：
iterator insert(iterator position,const T& x)
{
link_type tmp=create_node(x);
tmp->next=position.node;
tmp->prev=positon.node->prev;
(link_type(position.node->prev))->next=tmp;
position.node->prev=tmp;
return tmp;
}
如果希望在list内的某处插入新节点，首先必须确定插入位置，例如希望在数据值为3的节点处插入一个数据为99的节点
ilite=find(il.begin(),il.end(),3);
if(ilite!=0)
il.insert(ilite,99);
list的元素操作
//插入一个节点，作为头节点
void push_front(const T& x) { insert(begin(),x)}
//插入一个节点，作为尾节点
void push_back(const T& x) { insert(end(),x);}
//移除迭代器position所指节点
iterator erase(iterator position)
{
link_type next_node =link_type(position.node->next);
link_type prev_node =link_type(position.node->prev);
prev_node->next=next_node;
next_node->prev=prev_node;
destroy_node(position.node);
return ierator(next_node);
}
list内部提供了一个所谓的迁移操作:将某连续范围的元素迁移到某个指定位置之前，下面是transfer的源码：
//将[first,last)内的所有元素移动到position之前
```cpp
void transfer(iterator position,iterator first,iterator last)
{
if(position!=last)
{
(*(link_type((*last.node).prev))).next=position.node;//(1)
(*(link_type((*first.node).prev))).next=last.node;//(2)
(*(link_type((*position.node).prev))).next=first.node;//(3)
link_type tmp=link_type((*position.node).prev);//(4)
(*position.node).prev=(*last.node).prev;//(5)
(*last.node).prev=(*first.node).prev;//(6)
(*first.node).prev=tmp;//(7)
}
}
上述的transfer并非公开接口，list公开提供的是所谓的接合操作(splice):将某连续范围的元素从一个list移动到另一个list的某个定点
为了提供各种接口的弹性，list::splice有许多版本:
public:
//将x接合于position所指位置之前，x必须不同于*this
void splice(iterator position,list& x)
{
if(!x.empty())
transfer(position,x.begin(),x.end());
}
//将i所指元素接合于position所指位置之前，position和i可指向同一个list
void splice(iterator position,list& ,iterator i)
{
iterator j=i;
++j;
if(position=i||position==j) return;
transfer(position,i,j);
]