东莞网站开发报价,个人网站开发背景及意义,中国世界排名第一的专业,广州软件开发培训班list库实现的要点#xff1a;
构建list类时#xff0c;需要同时构建struct Node来存储节点信息#xff0c;list类中只存储哨兵位节点信息#xff0c;迭代器类需要templateT,Ptr,Ref来构建const和非const迭代器#xff0c;迭代器中也是存储节点信息。反向迭代器也…list库实现的要点
构建list类时需要同时构建struct Node来存储节点信息list类中只存储哨兵位节点信息迭代器类需要templateT,Ptr,Ref来构建const和非const迭代器迭代器中也是存储节点信息。反向迭代器也是同样道理但是可以用迭代器来构建反向迭代器。具体代码如下
#includeiostream
#includeassert.h
#includealgorithm
using namespace std;templateclass T
struct __list_node
{__list_node(const T val T()):_data(val),_prev(nullptr),_next(nullptr){}__list_node* _prev;__list_node* _next;T _data;
};//构建每个节点//构建迭代器struct
templateclass T, class Ptr, class Ref
struct __list_iterator
{typedef __list_nodeT Node;typedef __list_iteratorT, Ptr, Ref Self;Node* _node;//成员变量还是节点只是在成员函数做手脚__list_iterator(Node* val ):_node(val){}Self operator(){_node _node-_next;return *this;}Self operator(int)//后置{Self tmp *this;(*this);return tmp;}Self operator--(){_node _node-_prev;return *this;}Self operator--(int){Self tmp *this;--(*this);return tmp;}Ptr operator-(){return (_node-_data);}Ref operator*(){return _node-_data;}bool operator! ( const Self val ){return !(_node val._node);}};
templateclass T,class Ptr,class Ref
struct __list_reverse_iterator
{typedef __list_iteratorT, T*, T iterator;typedef __list_reverse_iteratorT, T*, T Self;iterator _it;__list_reverse_iterator(iterator it):_it(it){}Self operator(){_it _it._node-_prev;return *this;}T operator*(){return _it._node-_data;}bool operator!(const Self rit){return !(_it._node rit._it._node);}};//构建双向带头循环链表
templateclass T
class list
{typedef __list_nodeT Node;
public:typedef __list_iteratorT,T*,T iterator;typedef __list_iteratorT, const T*, const T const_iterator;typedef __list_reverse_iteratorT, T*, T reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(--end());}reverse_iterator rend(){return reverse_iterator(end());}iterator begin(){return iterator(_phead-_next);}const_iterator begin()const{return const_iterator(_phead-_next);}iterator end(){return iterator(_phead);}const_iterator end()const{return const_iterator(_phead);}list()//开头空间初始化{_phead new Node;_phead-_next _phead;_phead-_prev _phead;}~list(){clear();delete _phead;_phead nullptr;}//拷贝构造(先创建一个哨兵位然后再pushback)list(const listT l){_phead new Node;_phead-_next _phead;_phead-_prev _phead;for (auto x : l){push_back(x);}}listT operator(const listT l){listT tmp(l);swap(_phead, tmp._phead);return *this;}//尾插入void push_back(const T val){//Node* tail _phead-_prev;//Node* newnode new Node(val);更变链接//tail-_next newnode;//newnode-_prev tail;//newnode-_next _phead;//_phead-_prev newnode;insert(end(), val);}//头插void push_front(const T val){insert(begin(), val);}//头删除void pop_front(){erase(begin());}//尾删除void pop_back(){erase(--end());}//清空节点(除了哨兵位都清除)void clear(){iterator it begin();while (it ! end()){it erase(it);}}//随机插入void insert(iterator pos, const T val){Node* pcur pos._node;Node* prev pcur-_prev;Node* newnode new Node(val);//构建联系newnode-_prev prev;newnode-_next pcur;prev-_next newnode;pcur-_prev newnode;}//删除指定位置(不能将哨兵位删掉iterator erase(iterator pos){assert(pos ! end());Node* pcur pos._node;Node* prev pcur-_prev;Node* next pcur-_next;delete pcur;pcur nullptr;prev-_next next;next-_prev prev;return iterator(next);}private:Node* _phead;
};
