网站排名top排行榜,网站做seo有什么作用,谷歌海外广告投放推广,微信小程序聊天室源码概述
SGI STL的list是一个双向链表#xff0c;单向链表是slist#xff0c;其不在标准规格之内单向和双向链表的区别在于#xff0c;单向链表的迭代器是单向的 Forward Iterator#xff0c;双向链表的迭代器属于双向的Bidirectional Iterator。因此很多功能都被受限但是单向…概述
SGI STL的list是一个双向链表单向链表是slist其不在标准规格之内单向和双向链表的区别在于单向链表的迭代器是单向的 Forward Iterator双向链表的迭代器属于双向的Bidirectional Iterator。因此很多功能都被受限但是单向链表的耗用的空间更小某些操作更快注意事项插入操作会将新的元素插入到指定的位置之前而不是之后的位置。但是单向链表无法回头确定前一个位置因此需要从头部开始重新找起即 除了在单向链表的起始处附近其余的地方进行insert 或者 erase都是不合适的操作。这也是单向和双向链表之间最大的差异因此 单向链表提供了 insert_after() 和 erase_after() 供灵活使用基于上述的考虑slist 也不提供push_back() 只提供push_front()因此一定要注意单向链表元素的顺序和 元素的插入进来的顺序 相反
slist的节点
单向链表的迭代器比双向链表更为复杂一些运用了继承关系因此在型别转换层面上有着复杂的表现#include iostream//单向链表的节点的基本结构
struct __slist_node_base{__slist_node_base* next;
};//单向链表的节点结构
template class T
struct __slist_node : public __slist_node_base{T data;
};//全局函数 已知某一个节点插入新的节点于其后
inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node,__slist_node_base* new_node){//令new_node节点的下一个节点为prev节点的下一节点new_node-next prev_node-next-next;prev_node-next new_node; //令prev节点的next指针指向new节点return new_node;
}//全局函数 单向链表的大小(元素的个数)
inline std::size_t __slist_size(__slist_node_base* node){std::size_t result 0;for( ; node ! 0;node node-next){result; //一个一个累计}return result;
}
slist的迭代器 实际构造的时候 注意迭代器和节点之间的关系
//单向链表的迭代器的基本结构
struct __slist_iterator_base{typedef std::size_t size_type;typedef std::ptrdiff_t difference_type;typedef std::forward_iterator_tag iterator_category; //注意 单向__slist_node_base* node; //指向节点的基本结构 next指针__slist_iterator_base(__slist_node_base* x): node(x){}void incr(){node node-next; } //前进一个节点bool operator(const __slist_iterator_base x)const{return node x.node;}bool operator!(const __slist_iterator_base x)const{return node ! x.node;}
};//单向链表的迭代器结构
template class T,class Ref,class Ptr
struct __slist_iterator : public __slist_iterator_base{typedef __slist_iteratorT,T,T* iterator;typedef __slist_iteratorT,const T,const T*const_iterator;typedef __slist_iteratorT,T,T* self;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __slist_nodeT list_node;//调用slistT::end()会造成__slist_iterator(0) 于是调用如下函数__slist_iterator(list_node* x) : __slist_iterator_base(x){}__slist_iterator(): __slist_iterator_base(0){}__slist_iterator(const iterator x): __slist_iterator_base(x.node){}reference operator*() const {return ((list_node*)node)-data;}reference operator-() const {return (operator*());}self operator(){incr(); //前进一个节点return *this;}self operator(int){self tmp *this;incr(); //前进一个节点return tmp;}//没有实现operator-- 因为这是一个单向链表使用的是forward iterator
};
注意比较两个slist迭代器是否等同时比如常规循环下需要判断 迭代器是否等同于 slist.end() 但是__slist_iterator并没有对operator进行重载所以会调用 __slist_iterator_base::operator __slist_iterator_base::operator内部通过判定 __slist_iterator_base* node来判定两个迭代器是否等同
slist的数据结构
#include iostream//单向链表的节点的基本结构
struct __slist_node_base{__slist_node_base* next;
};//单向链表的节点结构
template class T
struct __slist_node : public __slist_node_base{T data;
};//全局函数 已知某一个节点插入新的节点于其后
inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node,__slist_node_base* new_node){//令new_node节点的下一个节点为prev节点的下一节点new_node-next prev_node-next-next;prev_node-next new_node; //令prev节点的next指针指向new节点return new_node;
}//全局函数 单向链表的大小(元素的个数)
inline std::size_t __slist_size(__slist_node_base* node){std::size_t result 0;for( ; node ! 0;node node-next){result; //一个一个累计}return result;
}//单向链表的迭代器的基本结构
struct __slist_iterator_base{typedef std::size_t size_type;typedef std::ptrdiff_t difference_type;typedef std::forward_iterator_tag iterator_category; //注意 单向__slist_node_base* node; //指向节点的基本结构 next指针__slist_iterator_base(__slist_node_base* x): node(x){}void incr(){node node-next; } //前进一个节点bool operator(const __slist_iterator_base x)const{return node x.node;}bool operator!(const __slist_iterator_base x)const{return node ! x.node;}
};//单向链表的迭代器结构
template class T,class Ref,class Ptr
struct __slist_iterator : public __slist_iterator_base{typedef __slist_iteratorT,T,T* iterator;typedef __slist_iteratorT,const T,const T*const_iterator;typedef __slist_iteratorT,T,T* self;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __slist_nodeT list_node;//调用slistT::end()会造成__slist_iterator(0) 于是调用如下函数__slist_iterator(list_node* x) : __slist_iterator_base(x){}__slist_iterator(): __slist_iterator_base(0){}__slist_iterator(const iterator x): __slist_iterator_base(x.node){}reference operator*() const {return ((list_node*)node)-data;}reference operator-() const {return (operator*());}self operator(){incr(); //前进一个节点return *this;}self operator(int){self tmp *this;incr(); //前进一个节点return tmp;}//没有实现operator-- 因为这是一个单向链表使用的是forward iterator
};templateclass T,class Alloc
class simple_alloc{
public:static T* allocate(std::size_t n){return 0n?0:(T*)Alloc::allocate(n * sizeof(T));}static T* allocate(void){return (T*)Alloc::allocate(sizeof (T));}static void deallocate(T* p,size_t n){if (n!0){Alloc::deallocate(p,n * sizeof(T));}}static void deallocate(T* p){Alloc::deallocate(p,sizeof(T));}
};#ifdef __STL_USE_EXCEPTIONS
#define __STL_TRY try
#define __STL_UNWIND(action) catch(...) { action; throw; }
#else
#define __STL_TRY
#define __STL_UNWIND(action)
#endifnamespace Chy{template class Tinline T* _allocate(ptrdiff_t size,T*){std::set_new_handler(0);T* tmp (T*)(::operator new((std::size_t)(size * sizeof (T))));if (tmp 0){std::cerr out of memory std::endl;exit(1);}return tmp;}templateclass Tinline void _deallocate(T* buffer){::operator delete (buffer);}templateclass T1,class T2inline void _construct(T1 *p,const T2 value){new(p) T1 (value); //没看懂}template class Tinline void _destroy(T* ptr){ptr-~T();}template class Tclass allocator{public:typedef T value_type;typedef T* pointer;typedef const T* const_pointer;typedef T reference;typedef const T const_reference;typedef std::size_t size_type;typedef ptrdiff_t difference_type;templateclass Ustruct rebind{typedef allocatorUother;};pointer allocate(size_type n,const void * hint 0){return _allocate((difference_type)n,(pointer)0);}void deallocate(pointer p,size_type n){_deallocate(p);}void construct(pointer p,const T value){_construct(p,value);}void destroy(pointer p){_destroy(p);}pointer address(reference x){return (pointer)x;}const_pointer const_address(const_reference x){return (const_pointer)x;}size_type max_size()const{return size_type(UINT_MAX/sizeof (T));}};
}template class T,class 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 std::size_t size_type;typedef std::ptrdiff_t difference_type;typedef __slist_iteratorT,T,T* iterator;typedef __slist_iteratorT,const T,const T*const_iterator;
private:typedef __slist_nodeT list_node;typedef __slist_node_base list_node_base;typedef __slist_iterator_base iterator_base;typedef simple_alloclist_node,Alloclist_node_allocator;static list_node* create_node(const value_type x){list_node* node list_node_allocator::allocate(); //配置空间__STL_TRY{Chy::allocatorT::construct(node-data,x);node-next 0;};__STL_UNWIND(list_node_allocator::deallocate(node);) //释放空间}static void destroy_node(list_node* node){Chy::allocatorT::destroy(node-data);//将元素析构list_node_allocator::deallocate(node); //释放空间}
private:list_node_base head; //头部 注意head不是指针是事物
public:slist(){head.next 0;}~slist(){clear();}
public:void clear(){erase_after(head,0);}//全局函数 传递链表的头部和尾部inline list_node_base* erase_after(list_node_base* before_first,list_node_base* last_node){list_node * cur (list_node*)(before_first-next);while (cur ! last_node){list_node * tmp cur;cur (list_node *)cur-next;destroy_node(tmp);}before_first-next last_node;return last_node;}
public:iterator begin(){return iterator((list_node*)head.next);}iterator end(){return iterator(0);}size_type size() const{return __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;}//获取头部元素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);}};元素操作 参考链接
STL源码剖析十二序列式容器之slist_JT同学的博客-CSDN博客
