节点
|
1 2 3 4 5 6 7 8 |
template <class T> struct __list_node { typedef void* void_pointer; void_pointer prev; void_pointer next; T data; }; |
迭代器
list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。
重要性质：
插入（insert)和结合（splice）都不会造成原有的list迭代器失效。
|
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 |
template<class T,class Ref,class Ptr> struct __list_iterator { typedef __list_iterator<T,T&,T*> 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; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node;//用于访问节点的普通指针 //constructor __list_iterator(link_type):node(x) {} __list_iterator() {} __list_iterator(const iterator& x):node(x) {} bool operator==(const self& x) const {return node == x.node;} bool operator!=(const self& x) const {return node != x.node;} //对迭代器取值 reference operator*() const {return (*node).data;} //迭代器成员存储运算子的实现 pointer operator->() const {return &(operator*());} //对迭代器累加 self& operator++() { node = (link_type)((*node).next); return *this; } self operator++(int) { self temp = *this; ++*this; return temp; } //对迭代器递减 self& operator--() { node = (link_type)((*node).prev); return *this; } self operator--(int) { self temp = *this; --*this; return temp; } }; |
数据结构
SGI list不仅是一个双向链表,而且是一个环状双向链表。
|
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 |
template<class T,class Alloc = alloc> class list { protected: typedef __list_node<T> list_node; public: typedef list_node* link_type; protected: link_type node;//只要一个指针,可表示整个环状双链表 //... public: iterator begin() {return (link_type)((*node).next);} iterator end() {return node;} bool isempty() const {return node->next == node;} size_type size() const { size_type result = 0; distance(begin(),end(),result);//全局函数 return result; } //取头节点值 reference front() {return *begin();} reference back() {return *(--end());} }; |
示意图:
构造与内存
|
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 |
template<class T,class Alloc = alloc> class list { //... protected: typedef __list_node<T> list_node; //专属空间配置器,每次配置一个节点大小 typedef simple_alloc<list_node,Alloc> list_node_allocator; protected: //配置一个节点并返回 link_type get_node() {return list_node_allocator::allocate();} //释放一个节点 void put_node(link_type p) {list_node_allocator::deallocate(p);} //产生一个节点,并带有元素 link_type create_node(const T& x) { link_type p = get_node(); construct(&p->data,x);//全局函数,构造/析构基本工具 return p; } void destroy_node(link_type p) { destroy(&p->data);//全局函数,构造/析构基本工具 put_node(p); } public: list() {empty_initialize();}//产生空链表 protected: void empty_initialize() { node = get_node();//配置一个节点空间,让node指向它 node->next = node; node->prev = 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 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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
//insert最简单的形式如下: iterator insert(iterator position,const T& x) { link_type temp = create_node(x); temp->next = position.node; temp->prev = position.node->prev; (link_type(position.node->prev))->next = temp; position.node->prev = temp; return temp; } void push_front(const T& x) {insert(begin(),x);} void push_back(const T& x) {insert(end(),x);} //移除迭代器iterator所指节点 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; destroy(position.node); return iterator(next_node); } //移除头节点 void pop_front() {erase(begin());} //移除尾节点 void pop_back() { iterator temp = end(); erase(--temp); } //清除所有节点(整个链表) template<class T,class Alloc> void list<T,Alloc>::clear() { link_type cur = (link_type)node->next;//begin() while(cur != node) { link_type temp = cur; cur = (link_type)cur->next; destroy(temp); } //恢复node原始状态 node->next = node; node->prev = node; } //将数值为value的所有元素移除 template<clss T,class Alloc> 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> 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;//如果删过东西,从头开始重新找;如果没,让first和next处于初始条件 } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//迁移操作,将[first,last)范围内元素移到position之前 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 temp = link_type((*position.node).prev);//4 (*position.node).prev = (*last.node).prev;//5 (*last.node).prev = (*first.node).prev;//6 (*first.node).prev = temp;//7 } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//接合元素 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); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
template<class T,class Alloc> void list<T,Alloc>::merge(list<T,Alloc>& x) { iterator first1 = begin(); iterator last1 = end(); iterator first2 = x.begin(); iterator last2 = x.end(); //前提是,两个lists都已经是排过序的 while(first1 != last1 && first2 != last2) { if(*first2 < *first1) { iterator next = first2; transfer(first1,first2,++next); first2 = next; } else ++first1; if(first2 != last2) return transfer(last1,first2,last2); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
template<class T,class Alloc> void list<T,Alloc>::reverse() { if(node->next == node || link_type(node->next)->next == node) return; iterator first = begin(); ++first; while(first != end()) { iterator old = first; ++first; transfer(begin(),old,first); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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]); } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ C++_函数模板、类模板、特化、模板元编程、SFINAE、概念06/22
- ♥ C++17_第三篇06/29
- ♥ COM组件_303/07
- ♥ C++20_第二篇03/21
- ♥ Skia总结概述11/15
- ♥ C++_多态、类型转换、数据段、BSS段、类型视图06/21