【STLソース解析読書ノート】【第4章】シリアル型容器のリストとslist

5080 ワード

一、リスト
1、リスト概要
listは双方向チェーンテーブルであり、任意の位置の要素挿入または要素除去に対して、listは常に定数時間である.
2、リストのノード
リスト自体とリストノードは異なるデータ構造であり、別々に設計する必要がある.STLリストのノード構造:

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

3、
リスト
のローズマリー
STL listは双方向チェーン表であり、サブジェネレータは前に移動し、後に移動する能力を備えていなければならない.リストはBidirectional Iteratorsを提供する.リストの挿入操作と係合操作は元のリスト・シーケンサを失効させない.
4、リストのデータ構造
STLリストは環状双方向リンク表であり、1つのポインタでチェーン全体を表現できます.

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          ，   x
	link_type tmp = create_node(x);
	tmp->next = position.node;
	tmp->prev = position.node->node;
	(link_type(position.node->prev))->next = tmp;
	return tmp;
}

6、パンシュバック関数
新しい元素をリストの端に挿入し、内部でinsert()関数を呼び出します.

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

、
pushfront()
関数
新しい元素をリストヘッドに挿入し、内部で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、
トランスファー()
関数
ある連続範囲の要素をある特定の位置に移動する前に.

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に属し、後者のローズマリーが双方向のBidirectional Iteratorに属していることである.
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()
	
	//       (   )。  head
	void pop_front()
	{
		list_node* node = (list_node*)head.next ;
		head.next = node->next ;
		destroy_node(node);
	}
	.....
}  ;

、
slist
の要素操作

データ構造——チェーンが逆さまです.