C++Linklist
发布时间:2020-12-16 07:19:43 所属栏目:百科 来源:网络整理
导读:#if 1 #ifndef _LINKLIST_H_ #define _LINKLIST_H_ #include iterator #pragma warning (disable : 26495) template typename T class linklist{ public : using uint = unsigned int ; struct _iterator; protected : struct _node; uint _size; _node * he
#if 1 #ifndef _LINKLIST_H_ #define _LINKLIST_H_ #include <iterator> #pragma warning (disable : 26495) template<typename T> class linklist{ public: using uint = unsigned int; struct _iterator; protected: struct _node; uint _size; _node *head; void copy_linklist(const linklist<T> &); void init_head(); public: //construction and destruction linklist(); linklist(const linklist<T> &ls); explicit linklist(const uint); linklist(const uint,const T &); linklist(_iterator,_iterator); ~linklist(); void push_back(const T &); void pop_back(); void push_front(const T &); void pop_front(); _iterator erase(_iterator); _iterator erase(_iterator,_iterator); const T &back() const{ return head->prior->_value; } T &back(){ return head->prior->_value; } //last element const T &front()const{ return head->next->_value; } T &front(){ return head->next->_value; } //first element linklist<T> &operator=(const linklist<T> &); void reverse(); bool empty()const{ return _size == 0; } uint size()const{ return _size; } _iterator begin(){ return _iterator(head->next); } _iterator end(){ return _iterator(head); } void clear(); }; template<typename T> struct linklist<T>::_node{ T _value; _node *prior; _node *next; _node &operator=(const _node &n){ this->next = n.next; this->prior = n.prior; this->_value = n._value; } _node() :_value(T()),prior(this),next(this){ } _node(const T &value) :_value(value),prior(this),next(this){ } _node(const _node &n) :_value(n._value),prior(n.prior),next(n.next){ } ~_node(){ } }; template<typename T> struct linklist<T>::_iterator : public std::iterator<std::bidirectional_iterator_tag,T>{ protected: _node *_real_node; public: _iterator():_real_node(){ } _iterator(const _iterator &iter) :_real_node(iter._real_node){ } _iterator(_node *n):_real_node(n){ } _node *get_ptr(){ return _real_node; } T &operator*()const{ return _real_node->_value; } T *operator->()const{ return &_real_node->_value; } _iterator &operator=(const _iterator &iter){ _real_node = iter._real_node; return *this; } bool operator==(const _iterator &iter) const{ return _real_node == iter._real_node; } bool operator!=(const _iterator &iter)const{ return _real_node != iter._real_node; } bool operator!()const{ return !_real_node; } _iterator &operator++(){ _real_node = _real_node->next; return *this; } _iterator operator++(int){ auto old = *this; ++ *this; return old; } _iterator &operator--(){ _real_node = _real_node->prior; return *this; } _iterator operator--(int){ auto old = *this; -- *this; return old; } }; template<typename T> void linklist<T>::copy_linklist(const linklist<T> &ls){ clear(); init_head(); auto p = ls.head->next; while(p != ls.head){ this->push_back(p->_value); p = p->next; } } template<typename T> void linklist<T>::clear(){ _size = 0; if(!empty()){ auto p = head; while(p->next != head){ auto q = p; p = p->next; delete q; } delete p; //p->next == head } delete head; } template<typename T> void linklist<T>::init_head(){ head = new _node; head->next = head->prior = head; head->_value = T(); } template<typename T> linklist<T>::linklist() : _size(0){ init_head(); } template<typename T> linklist<T>::linklist(const linklist<T> &ls){ copy_linklist(ls); } template<typename T> linklist<T>::linklist(const uint cnt) :_size(0){ init_head(); for(register uint i(0); i < cnt; ++i) this->push_back(T()); } template<typename T> linklist<T>::linklist(const uint cnt,const T &value) :_size(0){ init_head(); for(register uint i(0); i < cnt; ++i){ this->push_back(value); } } template<typename T> linklist<T>::~linklist(){ clear(); } template<typename T> linklist<T>::linklist(_iterator first,_iterator last) :_size(0){ init_head(); while(first != last){ this->push_back(*first); ++first; } } template<typename T> void linklist<T>::push_back(const T &value){ _node *p = new _node; p->_value = value; p->next = head; //head->next == first elem p->prior = head->prior; //head->prior == last elem head->prior->next = p; head->prior = p; ++_size; } template<typename T> void linklist<T>::push_front(const T &value){ auto p = new _node; p->_value = value; p->next = head->next; p->prior = head; head->next = head->next->prior = p; ++_size; } template<typename T> void linklist<T>::pop_back(){ auto p = head->prior; p->prior->next = head; head->prior = p->prior; p->_value.~T(); --_size; delete p; } template<typename T> void linklist<T>::pop_front(){ auto p = head->next; head->next = p->next; p->next->prior = head; p->_value.~T(); --_size; delete p; } template<typename T> typename linklist<T>::_iterator linklist<T>::erase(_iterator iter){ auto ptn = iter.get_ptr(); auto ptn_next = ptn->next; ptn->next->prior = ptn->prior; ptn->prior->next = ptn->next; delete ptn; --_size; return _iterator(ptn_next); } template<typename T> typename linklist<T>::_iterator linklist<T>::erase(_iterator first,_iterator last){ while(first != last){ first = erase(first); } return first; } template<typename T> linklist<T> &linklist<T>::operator=(const linklist<T> &ls){ copy_linklist(ls); return *this; } template<typename T> void linklist<T>::reverse(){ auto iter = begin(); for(register uint i(0); i < _size; ++i){ push_front(*iter); iter = erase(iter); } } #endif // !_LINKLIST_H_ #endif (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |