20170326STL07_STL_SGI_list

list&＃xff1a;

struct _List_node_base {//用于指向节点的下一个节点和上一个_List_node_base* _M_next;_List_node_base* _M_prev;
};template
struct _List_node : public _List_node_base {//用于保存每个节点的数据_Tp _M_data;
};
struct _List_iterator_base {//迭代器基类typedef size_t size_type;typedef ptrdiff_t difference_type;typedef bidirectional_iterator_tag iterator_category;_List_node_base* _M_node;//创建一个节点&＃xff0c;用于后期访问整个链表的数据_List_iterator_base(_List_node_base* __x) : _M_node(__x) {}_List_iterator_base() {}void _M_incr() { _M_node &＃61; _M_node->_M_next; }//访问下一个节点void _M_decr() { _M_node &＃61; _M_node->_M_prev; }//访问上一个节点bool operator&＃61;&＃61;(const _List_iterator_base& __x) const {return _M_node &＃61;&＃61; __x._M_node;}bool operator!&＃61;(const _List_iterator_base& __x) const {return _M_node !&＃61; __x._M_node;}
}; template
struct _List_iterator : public _List_iterator_base {typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;typedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;typedef _List_node<_Tp> _Node;_List_iterator(_Node* __x) : _List_iterator_base(__x) {}_List_iterator() {}_List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}reference operator*() const { return ((_Node*) _M_node)->_M_data; }//取值#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }//取值
#endif /* __SGI_STL_NO_ARROW_OPERATOR */_Self& operator&＃43;&＃43;() { //迭代器后移&＃xff08;前&＃43;&＃43;&＃xff09;this->_M_incr();return *this;}_Self operator&＃43;&＃43;(int) { //迭代器后移&＃xff08;后&＃43;&＃43;&＃xff09;_Self __tmp &＃61; *this;this->_M_incr();return __tmp;}_Self& operator--() { this->_M_decr();return *this;}_Self operator--(int) { _Self __tmp &＃61; *this;this->_M_decr();return __tmp;}
};
//部分方法实现iterator begin() { return (_Node*)(_M_node->_M_next); }//_M_node始终保存的是末尾的位置const_iterator begin() const { return (_Node*)(_M_node->_M_next); }iterator end() { return _M_node; }const_iterator end() const { return _M_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()); }bool empty() const { return _M_node->_M_next &＃61;&＃61; _M_node; }size_type size() const {size_type __result &＃61; 0;distance(begin(), end(), __result);return __result;}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<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); }iterator insert(iterator __position, const _Tp& __x) {//在中间位置插入元素_Node* __tmp &＃61; _M_create_node(__x);//新建临时对象__tmp->_M_next &＃61; __position._M_node;//修改临时对象下一个节点指向__tmp->_M_prev &＃61; __position._M_node->_M_prev;//修改临时对象前一个指向__position._M_node->_M_prev->_M_next &＃61; __tmp;//修改原来这里的节点__position._M_node->_M_prev &＃61; __tmp;return __tmp;}iterator insert(iterator __position) { return insert(__position, _Tp()); }

iterator erase(iterator __position) {//擦除&＃xff0c;和上面一样&＃xff0c;直接把此元素前后元素的指针指向改了&＃xff0c;然后析构这个元素就可以_List_node_base* __next_node &＃61; __position._M_node->_M_next;_List_node_base* __prev_node &＃61; __position._M_node->_M_prev;_Node* __n &＃61; (_Node*) __position._M_node;__prev_node->_M_next &＃61; __next_node;__next_node->_M_prev &＃61; __prev_node;_Destroy(&__n->_M_data);_M_put_node(__n);return iterator((_Node*) __next_node);}