#ifndef _M_LIST_H #define _M_LIST_H /*************************************** * Description:list实现 * Create:2019/12/1 * Author:zhangfeng * History: * 2019-12-3 搭建初步框架和基本接口 * node是循环连接，end->next连接front, front-prev连接end * 2019-12-4 补齐构造函数，模板继承类不能调用基类成员，必须显示调用 * 2019-12-5 补齐修改器部分，list交换只需要替换_node * 2019-12-6 补齐操作相关 * *************************************/ #include <memory> #include <iostream> #include <algorithm> #include <cstddef> #include <type_traits> //节点 template <class T> struct List_node { T _data; List_node* _next; List_node* _prev; List_node(T x) : _data(x){} }; //迭代器 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 T value_type; typedef Ptr pointer; typedef Ref reference; typedef List_node<T> Node; Node* _node; List_iterator(Node *_x) : _node(_x) {} reference operator*() const { return _node->_data; } bool operator==(const iterator& rhs) const { return _node == rhs._node; } bool operator==(const const_iterator& rhs) const { return _node == rhs._node; } bool operator!=(const iterator& rhs) const { return _node != rhs._node; } bool operator!=(const const_iterator& rhs) const { return _node != rhs._node; } void incr() { _node = _node->_next; } void decr() { _node = _node->_prev; } //++it 前缀 _Self& operator++() { this->incr(); return *this; } //it++ 后缀 _Self operator++(int) { _Self tmp = *this; this->incr(); return tmp; } //--it 前缀 _Self& operator--() { this->decr(); return *this; } //it-- 后缀 _Self operator--(int) { _Self tmp = *this; this->decr(); return tmp; } }; template <class T, class Alloc > class mList_base { public: typedef List_node<T> Node; mList_base() { std::cout << "base mList" << std::endl; _node = _alloc.allocate(1); _node->_next = _node; _node->_prev = _node; } ~mList_base() { std::cout << "~ base mList" << std::endl; clear(); _alloc.deallocate(_node, 1); } Node* create_node(const T& _x){ Node* p = this->_alloc.allocate(1); try{ _alloc.construct(p, _x); }catch(...){ _alloc.deallocate(p, 1); } return p; } void clear() { Node* _cur = (Node*)_node->_next; while(_cur != _node) { Node* _tmp = _cur; _cur = (Node*)_cur->_next; _alloc.destroy(&_tmp->_data); _alloc.deallocate(_tmp, 1); } _node->_next = _node; _node->_prev = _node; } protected: Node* _node; Alloc _alloc; }; template <class T, class Alloc=std::allocator<List_node<T>>> class mList : protected mList_base<T, Alloc> { 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 List_node<T> Node; typedef mList_base<T, Alloc> _Base; public: typedef List_iterator<T, T&, T*> iterator; typedef List_iterator<T, const T&, const T*> const_iterator; protected: using _Base::_node; using _Base::_alloc; public: explicit mList() { } explicit mList( size_type _n, const T& _value ) { std::cout << " mList( size_type _n, const T& _value ) " << std::endl; this->insert(begin(), _n, _value); } mList( const mList& other ) { std::cout << " mList( const mList& other ) " << std::endl; this->insert(begin(), other.begin(), other.end()); } ~mList() { std::cout << "~mList" << std::endl; } //元素访问 iterator begin() { return (Node*)_node->_next; } const_iterator begin() const { return (Node*)_node->_next; } iterator end() { return _node; } const_iterator end() const { return _node; } reference front() { return *begin(); } const_reference front() const { return *begin(); } reference back() { return *(--end()); } const_reference back() const { return *(--end()); } //容量 bool empty() const { return _node->_next == _node; } size_type size() const { size_type result = 0; std::distance(begin(), end(), result); return result; } size_type max_size() const { return size_type(-1); } //修改器 void clear() { _Base::clear(); } void push_back( const T& _x ) { insert(end(), _x); } void push_front( const T& _x ) { insert(begin(), _x); } iterator insert(iterator _pos, const T& _x); void insert(iterator _pos, size_type _n, const T& _x); void insert( iterator _pos, const_iterator _first, const_iterator _last); iterator erase(iterator _pos); iterator erase( iterator _first, iterator _last ); void swap(mList& other) { std::swap(_node, other._node); } //操作 void merge( mList& other ); void splice( iterator _pos, mList& other ) { if(!other.empty()) { this->transfer(_pos, other.begin(), other.end()); } } void remove( const T& value); void reverse(); void unique(); void sort(); protected: void transfer(iterator _pos, iterator _first, iterator _last) { if( _pos != _last ) { // [_first, _last] 从原位置移除 _last._node->_prev->_next = _pos._node; _first._node->_prev->_next = _last._node; _pos._node->_prev->_next = _first._node; // Splice [first, last) into its new position. Node* _tmp = _pos._node->_prev; _pos._node->_prev = _last._node->_prev; _last._node->_prev = _first._node->_prev; _first._node->_prev = _tmp; } } }; template <class T, class Alloc> typename mList<T, Alloc>::iterator mList<T, Alloc>::insert(iterator _pos, const T& _x) { Node* tmp = _Base::create_node(_x); tmp->_next = _pos._node; tmp->_prev = _pos._node->_prev; _pos._node->_prev->_next = tmp; _pos._node->_prev = tmp; return tmp; } template <class T, class Alloc> void mList<T, Alloc>::insert(iterator _pos, size_type _n, const T& _x) { for(; _n > 0; --_n) { insert(_pos, _x); } } template <class T, class Alloc> void mList<T, Alloc>::insert( iterator _pos, const_iterator _first, const_iterator _last) { for(; _first != _last; ++_first) { insert(_pos, *_first); } } template <class T, class Alloc> typename mList<T, Alloc>::iterator mList<T, Alloc>::erase(iterator _pos) { Node* _next_node = _pos._node->_next; Node* _prev_node = _pos._node->_prev; _next_node->_prev = _prev_node; _prev_node->_next = _next_node; _alloc.destroy(&_pos._node->_data); _alloc.deallocate(_pos._node, 1); return iterator((Node*)_next_node); } template <class T, class Alloc> typename mList<T, Alloc>::iterator mList<T, Alloc>::erase( iterator _first, iterator _last ) { while (_first != _last) { erase(_first++); } return _last; } template <class T, class Alloc> void mList<T, Alloc>::merge( mList& other) { iterator _first1 = begin(); iterator _last1 = end(); iterator _first2 = other.begin(); iterator _last2 = other.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> void mList<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 mList<T, Alloc>::reverse() { Node* _tmp = _node; do { std::swap(_tmp->_next, _tmp->_prev); _tmp = _tmp->_prev; // Old next node is now prev. std::cout << std::endl; } while (_tmp != _node); } template <class T, class Alloc> void mList<T, Alloc>::unique() { iterator _first = begin(); while(_first != end()) { iterator _tmp = _first++; if( *_tmp == *(_first) ) { erase(_tmp); } } } template <class T, class Alloc> void mList<T, Alloc>::sort() { std::sort(begin(), end()); } #endif