CONTENTS
备注:
本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
为了降低学习难度,作者这里换到了SGI-STL-2.91.57的源码来学习,代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】
slist是一个单向的链表,代码实现的比较简单。这里笔记下。
stl_slist.h:
//slist基础数据结构,什么信息都没有,因为是单向链表,只有一个指针。 struct __slist_node_base { __slist_node_base* next; }; // A->C ==>> A->B->C //将new_node(B)增加到链表中,放到prev_node(A)前面。 inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node, __slist_node_base* new_node) { new_node->next = prev_node->next; prev_node->next = new_node; return new_node; } //返回node的上一个节点。 //由于是单向链表,因此不能直接向前回溯。只能通过从起始点开始一个一个找 inline __slist_node_base* __slist_previous(__slist_node_base* head, const __slist_node_base* node) { while (head && head->next != node) head = head->next; return head; } //返回node的上一个节点。 //由于是单向链表,因此不能直接向前回溯。只能通过从起始点开始一个一个找 inline const __slist_node_base* __slist_previous(const __slist_node_base* head, const __slist_node_base* node) { while (head && head->next != node) head = head->next; return head; } //将(beforefirst,beforelast]间的所有节点截取出来,放到pos后面。 //A->B->C->D->E->F ==>> C->D->E->A->B->F inline void __slist_splice_after(__slist_node_base* pos, __slist_node_base* before_first, __slist_node_base* before_last) { if (pos != before_first && pos != before_last) { __slist_node_base* first = before_first->next; __slist_node_base* after = pos->next; before_first->next = before_last->next; pos->next = first; before_last->next = after; } } inline __slist_node_base* __slist_reverse(__slist_node_base* node) { __slist_node_base* result = node; node = node->next; result->next = 0; while(node) { __slist_node_base* next = node->next; node->next = result; result = node; node = next; } return result; } //节点类,继承自__slist_node_base,内部有真实数据T template <class T> struct __slist_node : public __slist_node_base { T data; }; //slist的iterator基础类 struct __slist_iterator_base { typedef size_t size_type; typedef ptrdiff_t difference_type; typedef forward_iterator_tag iterator_category; __slist_node_base* node;//iterator指向的节点 __slist_iterator_base(__slist_node_base* x) : node(x) {} void incr() { node = node->next; }//iterator递增,就是指向当前节点的下一个节点 bool operator==(const __slist_iterator_base& x) const { return node == x.node;//判断是否相等 } bool operator!=(const __slist_iterator_base& x) const { return node != x.node; } }; //slist的iterator类 template <class T, class Ref, class Ptr> struct __slist_iterator : public __slist_iterator_base { typedef __slist_iterator<T, T&, T*> iterator; typedef __slist_iterator<T, const T&, const T*> const_iterator; typedef __slist_iterator<T, Ref, Ptr> self; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __slist_node<T> list_node;//指向的节点的数据类型 //各种构造函数 __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; }//解引用,将内部指针强转之后返回节点中的数据。 #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self& operator++()//递增 { incr(); return *this; } self operator++(int)//递增 { self tmp = *this; incr(); return tmp; } }; #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION inline ptrdiff_t* distance_type(const __slist_iterator_base&) { return 0; } inline forward_iterator_tag iterator_category(const __slist_iterator_base&) { return forward_iterator_tag(); } template <class T, class Ref, class Ptr> inline T* value_type(const __slist_iterator<T, Ref, Ptr>&) { return 0; } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ //返回从此节点开始向后有多少个节点 inline size_t __slist_size(__slist_node_base* node) { size_t result = 0; for ( ; node != 0; node = node->next) ++result; return result; } //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; //构造一个slist的node,并用x将内部的T赋值。 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;//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);//在释放内存 } //构造n个节点,每个节点都用x来对内部T赋值,然后挂载到slist的头部。 void fill_initialize(size_type n, const value_type& x) { head.next = 0; __STL_TRY { _insert_after_fill(&head, n, x); } __STL_UNWIND(clear()); } //将【first,last)间的数据拷贝到slist中,挂载到slist的头部。 #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> void range_initialize(InputIterator first, InputIterator last) { head.next = 0; __STL_TRY { _insert_after_range(&head, first, last); } __STL_UNWIND(clear()); } #else /* __STL_MEMBER_TEMPLATES */ void range_initialize(const value_type* first, const value_type* last) { head.next = 0; __STL_TRY { _insert_after_range(&head, first, last); } __STL_UNWIND(clear()); } void range_initialize(const_iterator first, const_iterator last) { head.next = 0; __STL_TRY { _insert_after_range(&head, first, last); } __STL_UNWIND(clear()); } #endif /* __STL_MEMBER_TEMPLATES */ private: list_node_base head;//slist的头节点,指向slist的第一个节点。 public: slist() { head.next = 0; }//默认构造函数,slist内部数据为空,next=0。 //其他的构造函数。 slist(size_type n, const value_type& x) { fill_initialize(n, x); } slist(int n, const value_type& x) { fill_initialize(n, x); } slist(long n, const value_type& x) { fill_initialize(n, x); } explicit slist(size_type n) { fill_initialize(n, value_type()); } #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> slist(InputIterator first, InputIterator last) { range_initialize(first, last); } #else /* __STL_MEMBER_TEMPLATES */ slist(const_iterator first, const_iterator last) { range_initialize(first, last); } slist(const value_type* first, const value_type* last) { range_initialize(first, last); } #endif /* __STL_MEMBER_TEMPLATES */ //拷贝构造函数 slist(const slist& L) { range_initialize(L.begin(), L.end()); } //赋值构造函数 slist& operator= (const slist& L); //析构函数,清除掉内部的所有数据。 ~slist() { clear(); } public: //返回起始iterator。这里就是head的next节点 iterator begin() { return iterator((list_node*)head.next); } const_iterator begin() const { return const_iterator((list_node*)head.next);} //返回终止iterator,由于slist是单链表,因此最后终止就是NULL。 iterator end() { return iterator(0); } const_iterator end() const { return const_iterator(0); } //返回slist的大小。 size_type size() const { return __slist_size(head.next); } //返回slist的最大容量,由于slist的节点都是动态申请的,因此slist的最大容量由内存决定。 size_type max_size() const { return size_type(-1); } //判断slist是否为空。 bool empty() const { return head.next == 0; } //交换两个slist,由于slist中的head指向第一个节点,因此只要交换下两个head即可。 void swap(slist& L) { list_node_base* tmp = head.next; head.next = L.head.next; L.head.next = tmp; } public: friend bool operator== __STL_NULL_TMPL_ARGS(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2); public: //返回第一个节点【内部元素】的引用。 reference front() { return ((list_node*) head.next)->data; } const_reference front() const { return ((list_node*) head.next)->data; } //在slist的头部插入一个节点。 void push_front(const value_type& x) { __slist_make_link(&head, create_node(x)); } //从头部弹出一个节点。 void pop_front() { list_node* node = (list_node*) head.next; head.next = node->next; destroy_node(node); } //返回指定iterator的上一个iterator。 iterator previous(const_iterator pos) { return iterator((list_node*) __slist_previous(&head, pos.node)); } const_iterator previous(const_iterator pos) const { return const_iterator((list_node*) __slist_previous(&head, pos.node)); } private: //在某个节点之后插入一个新的节点。 list_node* _insert_after(list_node_base* pos, const value_type& x) { return (list_node*) (__slist_make_link(pos, create_node(x))); } //在某个节点之后插入n个新的节点。 void _insert_after_fill(list_node_base* pos, size_type n, const value_type& x) { for (size_type i = 0; i < n; ++i) pos = __slist_make_link(pos, create_node(x)); } #ifdef __STL_MEMBER_TEMPLATES template <class InIter> void _insert_after_range(list_node_base* pos, InIter first, InIter last) { while (first != last) { pos = __slist_make_link(pos, create_node(*first)); ++first; } } #else /* __STL_MEMBER_TEMPLATES */ void _insert_after_range(list_node_base* pos, const_iterator first, const_iterator last) { while (first != last) { pos = __slist_make_link(pos, create_node(*first)); ++first; } } void _insert_after_range(list_node_base* pos, const value_type* first, const value_type* last) { while (first != last) { pos = __slist_make_link(pos, create_node(*first)); ++first; } } #endif /* __STL_MEMBER_TEMPLATES */ //删除某个节点之后的一个节点。 list_node_base* erase_after(list_node_base* pos) { list_node* next = (list_node*) (pos->next); list_node_base* next_next = next->next; pos->next = next_next; destroy_node(next); return next_next; } //删除(before_first,last_node)之间的节点。 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后插入一个新的节点。 iterator insert_after(iterator pos, const value_type& x) { return iterator(_insert_after(pos.node, x)); } //在某个iterator后插入一个新的节点,节点值为默认值。 iterator insert_after(iterator pos) { return insert_after(pos, value_type()); } //在某个iterator后插入n个新的节点,节点值均为x。 void insert_after(iterator pos, size_type n, const value_type& x) { _insert_after_fill(pos.node, n, x); } void insert_after(iterator pos, int n, const value_type& x) { _insert_after_fill(pos.node, (size_type) n, x); } void insert_after(iterator pos, long n, const value_type& x) { _insert_after_fill(pos.node, (size_type) n, x); } #ifdef __STL_MEMBER_TEMPLATES template <class InIter> void insert_after(iterator pos, InIter first, InIter last) { _insert_after_range(pos.node, first, last); } #else /* __STL_MEMBER_TEMPLATES */ void insert_after(iterator pos, const_iterator first, const_iterator last) { _insert_after_range(pos.node, first, last); } void insert_after(iterator pos, const value_type* first, const value_type* last) { _insert_after_range(pos.node, first, last); } #endif /* __STL_MEMBER_TEMPLATES */ //在某个iterator前插入一个新的节点。 iterator insert(iterator pos, const value_type& x) { return iterator(_insert_after(__slist_previous(&head, pos.node), x)); } //在某个iterator前插入一个新的节点,节点值为默认值。 iterator insert(iterator pos) { return iterator(_insert_after(__slist_previous(&head, pos.node), value_type())); } //在某个iterator前插入n个新的节点。 void insert(iterator pos, size_type n, const value_type& x) { _insert_after_fill(__slist_previous(&head, pos.node), n, x); } void insert(iterator pos, int n, const value_type& x) { _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x); } void insert(iterator pos, long n, const value_type& x) { _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x); } #ifdef __STL_MEMBER_TEMPLATES template <class InIter> void insert(iterator pos, InIter first, InIter last) { _insert_after_range(__slist_previous(&head, pos.node), first, last); } #else /* __STL_MEMBER_TEMPLATES */ void insert(iterator pos, const_iterator first, const_iterator last) { _insert_after_range(__slist_previous(&head, pos.node), first, last); } void insert(iterator pos, const value_type* first, const value_type* last) { _insert_after_range(__slist_previous(&head, pos.node), first, last); } #endif /* __STL_MEMBER_TEMPLATES */ public: //删除iterator后面的一个节点。 iterator erase_after(iterator pos) { return iterator((list_node*)erase_after(pos.node)); } //删除(before_first,last)节点。 iterator erase_after(iterator before_first, iterator last) { return iterator((list_node*)erase_after(before_first.node, last.node)); } //删除iterator前面的一个节点。 iterator erase(iterator pos) { return (list_node*) erase_after(__slist_previous(&head, pos.node)); } //删除[first,last)节点。 iterator erase(iterator first, iterator last) { return (list_node*) erase_after(__slist_previous(&head, first.node), last.node); } void resize(size_type new_size, const T& x); void resize(size_type new_size) { resize(new_size, T()); } void clear() { erase_after(&head, 0); } public: // Moves the range [before_first + 1, before_last + 1) to *this, // inserting it immediately after pos. This is constant time. //将(beforefirst,beforelast]间的所有节点截取出来,放到pos后面。 void splice_after(iterator pos, iterator before_first, iterator before_last) { if (before_first != before_last) __slist_splice_after(pos.node, before_first.node, before_last.node); } // Moves the element that follows prev to *this, inserting it immediately // after pos. This is constant time. //将pre之后的节点插入到pos之后。 void splice_after(iterator pos, iterator prev) { __slist_splice_after(pos.node, prev.node, prev.node->next); } //将整个L插入到pos之前。 // Linear in distance(begin(), pos), and linear in L.size(). void splice(iterator pos, slist& L) { if (L.head.next) __slist_splice_after(__slist_previous(&head, pos.node), &L.head, __slist_previous(&L.head, 0)); } // Linear in distance(begin(), pos), and in distance(L.begin(), i). void splice(iterator pos, slist& L, iterator i) { __slist_splice_after(__slist_previous(&head, pos.node), __slist_previous(&L.head, i.node), i.node); } // Linear in distance(begin(), pos), in distance(L.begin(), first), // and in distance(first, last). void splice(iterator pos, slist& L, iterator first, iterator last) { if (first != last) __slist_splice_after(__slist_previous(&head, pos.node), __slist_previous(&L.head, first.node), __slist_previous(first.node, last.node)); } public: void reverse() { if (head.next) head.next = __slist_reverse(head.next); } void remove(const T& val); void unique(); void merge(slist& L); void sort(); #ifdef __STL_MEMBER_TEMPLATES template <class Predicate> void remove_if(Predicate pred); template <class BinaryPredicate> void unique(BinaryPredicate pred); template <class StrictWeakOrdering> void merge(slist&, StrictWeakOrdering); template <class StrictWeakOrdering> void sort(StrictWeakOrdering comp); #endif /* __STL_MEMBER_TEMPLATES */ }; //赋值构造函数 template <class T, class Alloc> slist<T, Alloc>& slist<T,Alloc>::operator=(const slist<T, Alloc>& L) { if (&L != this) { //如果不相等,则一个一个赋值。 list_node_base* p1 = &head; list_node* n1 = (list_node*) head.next; const list_node* n2 = (const list_node*) L.head.next; while (n1 && n2) { n1->data = n2->data; p1 = n1; n1 = (list_node*) n1->next; n2 = (const list_node*) n2->next; } if (n2 == 0)//多出来的就删了 erase_after(p1, 0); else//不够的往后补 _insert_after_range(p1, const_iterator((list_node*)n2), const_iterator(0)); } return *this; } //判断两个slist是否想等。 //通过一个一个元素进行对比。 template <class T, class Alloc> bool operator==(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2) { typedef typename slist<T,Alloc>::list_node list_node; list_node* n1 = (list_node*) L1.head.next; list_node* n2 = (list_node*) L2.head.next; while (n1 && n2 && n1->data == n2->data) { n1 = (list_node*) n1->next; n2 = (list_node*) n2->next; } return n1 == 0 && n2 == 0; } template <class T, class Alloc> inline bool operator<(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2) { return lexicographical_compare(L1.begin(), L1.end(), L2.begin(), L2.end()); } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class T, class Alloc> inline void swap(slist<T, Alloc>& x, slist<T, Alloc>& y) { x.swap(y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ //重新设置slist的大小 template <class T, class Alloc> void slist<T, Alloc>::resize(size_type len, const T& x) { list_node_base* cur = &head; //循环计算出当前slist的长度。 while (cur->next != 0 && len > 0) { --len; cur = cur->next; } if (cur->next) //多的删了 erase_after(cur, 0); else _insert_after_fill(cur, len, x);//少的添上。 } //删掉指定值的节点 template <class T, class Alloc> void slist<T,Alloc>::remove(const T& val) { list_node_base* cur = &head; while (cur && cur->next) { if (((list_node*) cur->next)->data == val) erase_after(cur);//注意这里没有break,会删掉所有的符和条件的节点。 else cur = cur->next; } } //删除slist中的具有相同值的节点,即只留有一份备份。 template <class T, class Alloc> void slist<T,Alloc>::unique() { list_node_base* cur = head.next; if (cur) { while (cur->next) { if (((list_node*)cur)->data == ((list_node*)(cur->next))->data) erase_after(cur); else cur = cur->next; } } } //将两个slist合并成一个。 template <class T, class Alloc> void slist<T,Alloc>::merge(slist<T,Alloc>& L) { list_node_base* n1 = &head; while (n1->next && L.head.next) { if (((list_node*) L.head.next)->data < ((list_node*) n1->next)->data) __slist_splice_after(n1, &L.head, L.head.next); n1 = n1->next; } if (L.head.next) { n1->next = L.head.next; L.head.next = 0; } } //对slist进行排序 template <class T, class Alloc> void slist<T,Alloc>::sort() { if (head.next && head.next->next) { slist carry; slist counter[64]; int fill = 0; while (!empty()) { __slist_splice_after(&carry.head, &head, head.next); int i = 0; while (i < fill && !counter[i].empty()) { counter[i].merge(carry); carry.swap(counter[i]); ++i; } carry.swap(counter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]); this->swap(counter[fill-1]); } } #ifdef __STL_MEMBER_TEMPLATES template <class T, class Alloc> template <class Predicate> void slist<T,Alloc>::remove_if(Predicate pred) { list_node_base* cur = &head; while (cur->next) { if (pred(((list_node*) cur->next)->data)) erase_after(cur); else cur = cur->next; } } template <class T, class Alloc> template <class BinaryPredicate> void slist<T,Alloc>::unique(BinaryPredicate pred) { list_node* cur = (list_node*) head.next; if (cur) { while (cur->next) { if (pred(((list_node*)cur)->data, ((list_node*)(cur->next))->data)) erase_after(cur); else cur = (list_node*) cur->next; } } } template <class T, class Alloc> template <class StrictWeakOrdering> void slist<T,Alloc>::merge(slist<T,Alloc>& L, StrictWeakOrdering comp) { list_node_base* n1 = &head; while (n1->next && L.head.next) { if (comp(((list_node*) L.head.next)->data, ((list_node*) n1->next)->data)) __slist_splice_after(n1, &L.head, L.head.next); n1 = n1->next; } if (L.head.next) { n1->next = L.head.next; L.head.next = 0; } } template <class T, class Alloc> template <class StrictWeakOrdering> void slist<T,Alloc>::sort(StrictWeakOrdering comp) { if (head.next && head.next->next) { slist carry; slist counter[64]; int fill = 0; while (!empty()) { __slist_splice_after(&carry.head, &head, head.next); int i = 0; while (i < fill && !counter[i].empty()) { counter[i].merge(carry, comp); carry.swap(counter[i]); ++i; } carry.swap(counter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1], comp); this->swap(counter[fill-1]); } }
发表评论