【STL源码剖析读书笔记】【第4章】序列式容器之list和slist

本文主要是介绍【STL源码剖析读书笔记】【第4章】序列式容器之list和slist，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、list

1、list概述

list是双向链表，对于任何位置的元素插入或元素移除，list永远是常数时间。

2、list的节点

list本身和list节点是不同的数据结构，需要分开设计。STL list的节点结构：

template <class T>
struct __list_node {typedef void* void_pointer;void_pointer next;void_pointer prev;T data;
};

3、 list 的迭代器

STL list是一个双向链表，迭代器必须具备前移、后移的能力，list提供的是Bidirectional Iterators。list的插入操作和接合操作都不会导致原来的list迭代器失效。

4、list的数据结构

STL list是一个环状双向链表，只需一个指针就可以表现整个链表。

template<class T,class Alloc = alloc> //缺省使用alloc为配置器:w
class list{
protected :typedef	__list_node<T> list_node ;
public  :typedef	list_node* link_type ;
protected :link_type node ; //只要一个指针，便可以表示整个环状双向链表
};

如果让指针 node 指向刻意置于尾端的一个空白节点， node 便能符合 STL 对于“前闭后开”区间的要求，成为 last 迭代器。

5、insert()函数

insert()是一个重载函数，最简单的一种如下：

iterator insert(iterator position, const T& x){//在迭代器position所指位置插入一个节点，内容为xlink_type tmp = create_node(x);tmp->next = position.node;tmp->prev = position.node->node;(link_type(position.node->prev))->next = tmp;return tmp;
}

6、push_back()函数

将新元素插入于list尾端，内部调用insert()函数

void push_back(const T& x){
insert(end(),x);
}

7、 push_front() 函数

将新元素插入于list头端，内部调用insert()函数

void push_front(const T&x){
insert(begin(),x);
}

8、 erase() 函数

iterator erase(iterator position){
link_type next_node=link_type(position.node->next);
link_type prev_node=link_type(position.node->prev_nodext);
prev_node->next=next_node;
next_node->prev=prev_node;
destroy_node(position.node);
return iterator(next_node);
}

9、pop_front()函数

移除头结点，内部调用erase()函数

void pop_front(){
erase(begin());
}

10、 pop_back() 函数

移除尾结点，内部调用erase()函数

void pop_back(){
iterator i=end();
erase(--i);
}

11、 transfer() 函数

将某连续范围的元素迁移到某个特定位置之前。

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)}}

二、slist

1、slist概述

SGI STL另提供一个单向链表slist。slist和list的主要差别在于，前者的迭代器属于单向的Forward Iterator，后者的迭代器属于双向的BidirectionalIterator。

根据STL的习惯，插入操作会将新元素插入于指定位置之前。作为单向链表，slist没有任何方便的方法可以回头定出前一个位置，因此它必须从头找起。

2、slist的节点

3、slist的迭代器

4、slist的数据结构

template<class T, class Alloc = alloc>
class slist
{
public :typedef	T	value_type ;typedef	value_type*	pointer ; typedef	const	value_type*	const_pointer ;typedef	value_type&	reference ;typedef	const value_type& const_reference ;typedef	size_t	size_type ;typedef	ptrdiff_t	difference_type ;typedef	__slist_iterator<T,T&,T*>	iterator ;typedef	__slist_iterator<T,const T&,const T*> const_iterator ;private :typedef	__slist_node<T>	list_node ;typedef	__slist_node_base	list_node_base ;typedef	__slist_iterator_base	iterator_base ;typedef simple_alloc<list_node,Alloc> list_node_allocator ;static	list_node* create_node(const value_type& x){list_node* node = list_node_allocator:;allocate() ; //配置空间__STL_TRY{construct(&node->data,x) ;node->next = 0 ;}__STL_UNWIND(list_node_allocator:;deallocate(node)) ;return node ;}static void destroy_node(list_node* node){destroy(&node->data) ; //将元素析构	list_node_allocator::deallocate(node) ; //释放空间}private :list_node_base head  ; //头部。注意，它不是指针，是实物public:slist() {head.next = 0 ;} ~slist(){clear() ;}public :iterator begin() {return iterator((list_node*)head.next) ;}iterator end() {return iteator(0) ;}iterator size() {const __slist_size(head.next) ;}bool empty() const {return head.next == 0 ;} //两个slist互换：只要将head交换互指即可void swap(slist &L){list_node_base* tmp = head.next;head.next = L.head.next ;L.head.next = tmp ;}public ://取头部元素reference front() {return ((list_node*)head.next)->data ;}//从头部插入元素(新元素成为slist的第一个元素)void push_front(const value_type& x){__slist_make_link(&head,create_node(x)) ;}//注意,没有push_back()//从头部取走元素(删除之)。修改headvoid pop_front(){list_node* node = (list_node*)head.next ;head.next = node->next ;destroy_node(node);}.....
}  ;

5、 slist 的元素操作