CONTENTS
备注:
本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
为了降低学习难度,作者这里换到了SGI-STL-2.91.57的源码来学习,代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】
stl_list.h:
部分代码如下,去掉了文件头部的注释。
//由于list在内存中的存储状态为双向链表式结构可知,每个节点都需要有指向其上一个和下一个的指针。 //因此这里需要专门定义一个结构体来描述节点 template <class T> struct __list_node { typedef void* void_pointer;//定义类型,个人认为可以改为 typedef __list_node* void_pointer void_pointer next;//指向下一个__list_node void_pointer prev;//指向上一个__list_node T data;//list_node中的数据 }; //由于list为链表式结构,而且节点的类型并不是存储的数据类型,而是__list_node, //因此在节点间进行上下移动的iterator也必须重新定义,以便支持节点上下移动,和读写内部存储的数据 template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type;//定义link_type为list中的节点指针类型 typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node;//interator中保存的它指向的节点的指针。 __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} //判断两个iterator是否相等,就是判断其指向的节点是否相同 bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } //对iterator进行解引用,就是想取得节点内部数据的引用,因此这里返回的是list_node中的data reference operator*() const { return (*node).data; } //重写了指针运算符,返回的指针是节点内部的数据的指针 #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ //这里是前置++( ++x ) //对于iterator来说,++就是指向下一个指针,因此这里将iterator内部的node赋值为下一个__list_node //然后返回本身 self& operator++() { node = (link_type)((*node).next); return *this; } //这里是后置++( x++ ) //和前置++功能类似,不过由于前置后置的语法问题,这里需要返回原来的数据 self operator++(int) { self tmp = *this; ++*this; return tmp; } //前置--( --x ) self& operator--() { node = (link_type)((*node).prev); return *this; } //后置--( x-- ) self operator--(int) { self tmp = *this; --*this; return tmp; } }; #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION //list的iterator是可以双向移动的,因此这里特化为返回bidirectional_iterator_tag template <class T, class Ref, class Ptr> inline bidirectional_iterator_tag iterator_category(const __list_iterator<T, Ref, Ptr>&) { return bidirectional_iterator_tag(); } //list的的iterator的value_type和distance_type都返回0,其实表示iterator不支持这两个操作 template <class T, class Ref, class Ptr> inline T* value_type(const __list_iterator<T, Ref, Ptr>&) { return 0; } template <class T, class Ref, class Ptr> inline ptrdiff_t* distance_type(const __list_iterator<T, Ref, Ptr>&) { return 0; } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ template <class T, class Alloc = alloc> class list { protected: typedef void* void_pointer; typedef __list_node<T> list_node; //使用简单的new,delete来申请和释放内存,注意这里内存单元节点类型为list_node,而不是T typedef simple_alloc<list_node, Alloc> list_node_allocator; 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 list_node* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; public: //定义两种不同类型的iterator typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION typedef reverse_iterator<const_iterator> const_reverse_iterator; typedef reverse_iterator<iterator> reverse_iterator; #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ typedef reverse_bidirectional_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator; typedef reverse_bidirectional_iterator<iterator, value_type, reference, difference_type> reverse_iterator; #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ protected: //申请一块新的内存,类型为__list_node<T> link_type get_node() { return list_node_allocator::allocate(); } //释放一块已有的内存 void put_node(link_type p) { list_node_allocator::deallocate(p); } //申请一块新的内存,并且用x来初始化它 link_type create_node(const T& x) { link_type p = get_node();//申请内存,类型为__list_node<T> __STL_TRY { construct(&p->data, x);//对__list_node<T>中的data上调用构造函数 } __STL_UNWIND(put_node(p)); return p;//返回构造好的__list_node<T> } //销毁一个已有的__list_node<T> void destroy_node(link_type p) { destroy(&p->data);//先调用析构函数,搞定__list_node<T>内部的数据 put_node(p);//释放掉这块内存 } protected: //初始化成一个空的list node首尾均指向自己 void empty_initialize() { node = get_node(); node->next = node; node->prev = node; } //初始化一个list,有n个节点,每个节点都初始化为value void fill_initialize(size_type n, const T& value) { empty_initialize();//先构造一个空的list __STL_TRY { insert(begin(), n, value);//然后在头部插入n个数据 } __STL_UNWIND(clear(); put_node(node)); } #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> void range_initialize(InputIterator first, InputIterator last) { empty_initialize(); __STL_TRY { insert(begin(), first, last); } __STL_UNWIND(clear(); put_node(node)); } #else /* __STL_MEMBER_TEMPLATES */ void range_initialize(const T* first, const T* last) { empty_initialize(); __STL_TRY { insert(begin(), first, last); } __STL_UNWIND(clear(); put_node(node)); } void range_initialize(const_iterator first, const_iterator last) { empty_initialize(); __STL_TRY { insert(begin(), first, last); } __STL_UNWIND(clear(); put_node(node)); } #endif /* __STL_MEMBER_TEMPLATES */ protected: //list中的保存的唯一一个节点的指针,通过它可以访问整个list中的所有的节点。 //而且node在list的节点操作中,均指向【最后】的那个节点的下一个节点【即空白节点,无有效数据】。 //node的下一个节点指向list的第一个节点。 link_type node; public: list() { empty_initialize(); }//构造函数 //begin方法 //由于node的下一个节点指向list的第一个节点,因此这里返回node的next, //由于node的next强转为link_type类型,而返回值为iterator,因此这里又会调用iterator的构造函数来构造一个iterator返回。 iterator begin() { return (link_type)((*node).next); } const_iterator begin() const { return (link_type)((*node).next); } //和begin类似,不过在返回时也构造了一个iterator 返回。注意这里的node是空白节点,无有效数据。 //因此它对应的iterator也是一个无效的位置,这个和vector是类似的。 iterator end() { return node; } const_iterator end() const { return node; } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } //node的下一个节点指向list的第一个节点。因此可以用它来判空 bool empty() const { return node->next == node; } //获取list的节点的个数,这里获取到指向list的第一个和最后一个无效节点的iterator size_type size() const { size_type result = 0; distance(begin(), end(), result); return result; } //list的节点是动态申请的,因此数目没有最大值限制 size_type max_size() const { return size_type(-1); } reference front() { return *begin(); } const_reference front() const { return *begin(); } reference back() { return *(--end()); } const_reference back() const { return *(--end()); } void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); } //在指定位置插入一个数据 iterator insert(iterator position, const T& x) { //list为链表结构,插入很简单,只要修改下next和prev即可。 //先用x构造一个节点, link_type tmp = create_node(x); //将这个新节点插入到链表中,并且维护下前后关系。 tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; } iterator insert(iterator position) { return insert(position, T()); } #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> void insert(iterator position, InputIterator first, InputIterator last); #else /* __STL_MEMBER_TEMPLATES */ void insert(iterator position, const T* first, const T* last); void insert(iterator position, const_iterator first, const_iterator last); #endif /* __STL_MEMBER_TEMPLATES */ void insert(iterator pos, size_type n, const T& x); void insert(iterator pos, int n, const T& x) { insert(pos, (size_type)n, x); } void insert(iterator pos, long n, const T& x) { insert(pos, (size_type)n, x); } //在首端插一个 void push_front(const T& x) { insert(begin(), x); } //在尾部差一个 void push_back(const T& x) { insert(end(), x); } //删除指定位置的一个数据 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; //销毁这个iterator对应的节点 destroy_node(position.node); return iterator(next_node); } iterator erase(iterator first, iterator last); void resize(size_type new_size, const T& x); void resize(size_type new_size) { resize(new_size, T()); } void clear(); void pop_front() { erase(begin()); } void pop_back() { iterator tmp = end(); erase(--tmp); } list(size_type n, const T& value) { fill_initialize(n, value); } list(int n, const T& value) { fill_initialize(n, value); } list(long n, const T& value) { fill_initialize(n, value); } explicit list(size_type n) { fill_initialize(n, T()); } #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> list(InputIterator first, InputIterator last) { range_initialize(first, last); } #else /* __STL_MEMBER_TEMPLATES */ list(const T* first, const T* last) { range_initialize(first, last); } list(const_iterator first, const_iterator last) { range_initialize(first, last); } #endif /* __STL_MEMBER_TEMPLATES */ list(const list<T, Alloc>& x) { range_initialize(x.begin(), x.end()); } //析构函数 ~list() { clear();//先清理掉所有的有效的数据 put_node(node);//然后将最后的那个空白节点销毁【 empty_initialize函数申请的 】 } list<T, Alloc>& operator=(const list<T, Alloc>& x); protected: //将【first,last)中的这部分链表插入到当前链表的position中。 void transfer(iterator position, iterator first, iterator last) { if (position != last) { (*(link_type((*last.node).prev))).next = position.node;//注意开闭关系,last指向的节点是不插入的 (*(link_type((*first.node).prev))).next = last.node; (*(link_type((*position.node).prev))).next = first.node; link_type tmp = link_type((*position.node).prev); (*position.node).prev = (*last.node).prev; (*last.node).prev = (*first.node).prev; (*first.node).prev = tmp; } } public: void splice(iterator position, list& x) { if (!x.empty()) transfer(position, x.begin(), x.end()); } void splice(iterator position, list&, iterator i) { iterator j = i; ++j; if (position == i || position == j) return; transfer(position, i, j); } void splice(iterator position, list&, iterator first, iterator last) { if (first != last) transfer(position, first, last); } void remove(const T& value); void unique(); void merge(list& x); void reverse(); void sort(); #ifdef __STL_MEMBER_TEMPLATES template <class Predicate> void remove_if(Predicate); template <class BinaryPredicate> void unique(BinaryPredicate); template <class StrictWeakOrdering> void merge(list&, StrictWeakOrdering); template <class StrictWeakOrdering> void sort(StrictWeakOrdering); #endif /* __STL_MEMBER_TEMPLATES */ friend bool operator== __STL_NULL_TMPL_ARGS (const list& x, const list& y); }; //判断两个list是否相等,这里采取的是遍历两个list,依次比较相同位置的节点 template <class T, class Alloc> inline bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y) { typedef typename list<T,Alloc>::link_type link_type; link_type e1 = x.node; link_type e2 = y.node; link_type n1 = (link_type) e1->next; link_type n2 = (link_type) e2->next; for ( ; n1 != e1 && n2 != e2 ; n1 = (link_type) n1->next, n2 = (link_type) n2->next) if (n1->data != n2->data) return false; return n1 == e1 && n2 == e2; } template <class T, class Alloc> inline bool operator<(const list<T, Alloc>& x, const list<T, Alloc>& y) { return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class T, class Alloc> inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) { x.swap(y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ #ifdef __STL_MEMBER_TEMPLATES template <class T, class Alloc> template <class InputIterator> void list<T, Alloc>::insert(iterator position, InputIterator first, InputIterator last) { for ( ; first != last; ++first) insert(position, *first); } #else /* __STL_MEMBER_TEMPLATES */ template <class T, class Alloc> void list<T, Alloc>::insert(iterator position, const T* first, const T* last) { for ( ; first != last; ++first) insert(position, *first); } template <class T, class Alloc> void list<T, Alloc>::insert(iterator position, const_iterator first, const_iterator last) { for ( ; first != last; ++first) insert(position, *first); } #endif /* __STL_MEMBER_TEMPLATES */ template <class T, class Alloc> void list<T, Alloc>::insert(iterator position, size_type n, const T& x) { for ( ; n > 0; --n) insert(position, x); } template <class T, class Alloc> list<T,Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last) { while (first != last) erase(first++); return last; } template <class T, class Alloc> //将list的大小重设置为new_size //多出来的删掉,不够的用x来补齐。 void list<T, Alloc>::resize(size_type new_size, const T& x) { iterator i = begin(); size_type len = 0; for ( ; i != end() && len < new_size; ++i, ++len) ; //计算list的节点的个数,这里退出for循环有两个判断: //1:list的节点数目<new_size,那么会补全 //2:在数list的节点数目时已经数到了new_size,没必要数下去了,后面的全部删掉。 if (len == new_size) erase(i, end()); else // i == end() insert(end(), new_size - len, x); } template <class T, class Alloc> //删除所有有效数据 void list<T, Alloc>::clear() { link_type cur = (link_type) node->next;//获取第一个有效数据 while (cur != node) {//如果要删除的节点==node空白节点,说明已经删除干净了 link_type tmp = cur; cur = (link_type) cur->next; destroy_node(tmp); } node->next = node; node->prev = node; } template <class T, class Alloc> //赋值构造函数 list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x) { if (this != &x) { iterator first1 = begin(); iterator last1 = end(); const_iterator first2 = x.begin(); const_iterator last2 = x.end(); while (first1 != last1 && first2 != last2) *first1++ = *first2++;//这里直接调用T的赋值构造函数,注意iterator的解引用 if (first2 == last2)//如果新的少,就把旧的删除 erase(first1, last1); else insert(last1, first2, last2);//如果新的多,就把多出来的插进去 } return *this; } template <class T, class Alloc> //遍历整个list,删除指定的节点 void list<T, Alloc>::remove(const T& value) { iterator first = begin(); iterator last = end(); while (first != last) { iterator next = first; ++next; if (*first == value) erase(first); first = next; } } template <class T, class Alloc> //删除list中的连续相同数据的节点。 void list<T, Alloc>::unique() { iterator first = begin(); iterator last = end(); if (first == last) return; iterator next = first; while (++next != last) { if (*first == *next) erase(next); else first = next; next = first; } } template <class T, class Alloc> //将listX中的节点合并到本list中 void list<T, Alloc>::merge(list<T, Alloc>& x) { iterator first1 = begin(); iterator last1 = end(); iterator first2 = x.begin(); iterator last2 = x.end(); while (first1 != last1 && first2 != last2) if (*first2 < *first1) { iterator next = first2; transfer(first1, first2, ++next); first2 = next; } else ++first1; if (first2 != last2) transfer(last1, first2, last2); } template <class T, class Alloc> //将list翻转过来 void list<T, Alloc>::reverse() { if (node->next == node || link_type(node->next)->next == node) return; iterator first = begin(); ++first; /* 翻转顺序 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1 */ while (first != end()) { iterator old = first; ++first; transfer(begin(), old, first); } } //将list进行排序,应该是快速排序 template <class T, class Alloc> void list<T, Alloc>::sort() { if (node->next == node || link_type(node->next)->next == node) return; list<T, Alloc> carry; list<T, Alloc> counter[64]; int fill = 0; while (!empty()) { carry.splice(carry.begin(), *this, begin()); int i = 0; while(i < fill && !counter[i].empty()) { counter[i].merge(carry); carry.swap(counter[i++]); } carry.swap(counter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]); swap(counter[fill-1]); } #ifdef __STL_MEMBER_TEMPLATES template <class T, class Alloc> template <class Predicate> void list<T, Alloc>::remove_if(Predicate pred) { iterator first = begin(); iterator last = end(); while (first != last) { iterator next = first; ++next; if (pred(*first)) erase(first); first = next; } } template <class T, class Alloc> template <class BinaryPredicate> void list<T, Alloc>::unique(BinaryPredicate binary_pred) { iterator first = begin(); iterator last = end(); if (first == last) return; iterator next = first; while (++next != last) { if (binary_pred(*first, *next)) erase(next); else first = next; next = first; } } template <class T, class Alloc> template <class StrictWeakOrdering> void list<T, Alloc>::merge(list<T, Alloc>& x, StrictWeakOrdering comp) { iterator first1 = begin(); iterator last1 = end(); iterator first2 = x.begin(); iterator last2 = x.end(); while (first1 != last1 && first2 != last2) if (comp(*first2, *first1)) { iterator next = first2; transfer(first1, first2, ++next); first2 = next; } else ++first1; if (first2 != last2) transfer(last1, first2, last2); } template <class T, class Alloc> template <class StrictWeakOrdering> void list<T, Alloc>::sort(StrictWeakOrdering comp) { if (node->next == node || link_type(node->next)->next == node) return; list<T, Alloc> carry; list<T, Alloc> counter[64]; int fill = 0; while (!empty()) { carry.splice(carry.begin(), *this, begin()); int i = 0; while(i < fill && !counter[i].empty()) { counter[i].merge(carry, comp); carry.swap(counter[i++]); } carry.swap(counter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1], comp); swap(counter[fill-1]); }
发表评论