异同
STL list是个双向链表。SGI STL另提供了一个单向列表，叫slist。slist的迭代器属于单向的Forward iterator，list迭代器是双向的Bidirectional Iterator。slist功能少点，所耗用的内存小点。
- 共同点是插入，移除，接合等操作并不会造成原有的迭代器失效。
实现
节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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->next = prev_node->next; prev_node_next->next = new_node; return new_node; } //全局函数 inline size_t __slist_size(__slist_node_base * node) { size_t result = 0; for (; node != 0; node = node->next) ++result; return result; } |
迭代器
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//单链表的迭代器基本结构 struct __slist_iterator_base { typedef size_t size_type; typedef ptrdiff_t difference_type; typedef forward_iterator_tag iterator_category; __slist_node_base * node; __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; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
//单链表的迭代器结构 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;} pointer operator->() const {return &(operator*());} self& operator++() { incr();//前进一个节点 return *this; } self operator++(int) { self tmp = *this; incr();//前进一个节点 return tmp; } }; |
数据结构
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
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 destory_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 iterator(0);} size_type size() const {return __slist_size(head.next);} bool empty() const {return head.next == 0;} void swap(slist& l) { slist_node_base* tmp = head.next; head.next = l.head.next; l.head.next = tmp; } public: reference front() {return ((list_node*)head.next)->data;} 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); } }; |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ Boost 程序库完全开发指南：容器算法数学文件08/24
- ♥ breakpad记述：Windows下静态库的编译使用03/15
- ♥ C++14_第二篇06/29
- ♥ COM组件_303/07
- ♥ Json库RapidJson使用01/11
- ♥ STL_priority_queue08/26