C++list的模拟实现
链表节点
template<class T>struct ListNode{ListNode(const T& data = T()): _data(data){}ListNode<T> * _prev=nullptr;ListNode<T> *_next=nullptr;T _data;};
因为之后要访问这个类的成员变量函数和结构体,所以在这里将class直接改为struct 构造函数
成员变量:
typedef ListNode<T> Node;
typedef ListIterator<T> iterator;
typedef ListconstIterator<T> const_iterator;
Node* _head;
该链表的实现是带头双向循环链表
迭代器的实现:
因为list不像vector和string那样开连续的空间,不能直接++访问下一个节点,所以这里设置迭代器时要另外封装一个类来实现
iterator:
template<class T>class ListIterator {public:typedef ListNode<T> Node;Node* _node;ListIterator(Node* node):_node(node)//用node初始化{}ListIterator<T> operator++(){_node = _node->_next;return *this;}ListIterator<T> operator++(int){ListIterator<T> tem(*this);_node = _node->_next;return tem;}ListIterator<T> operator--(){_node = _node->_prev;return *this;}bool operator!=(ListIterator<T> it){return _node != it._node;}bool operator==(ListIterator<T> it){return _node == it._node;}ListIterator<T> operator--(int){ListIterator<T> tem(*this);_node = _node->_prev;return tem;}T& operator *(){return _node->_data;}T* operator->(){return &(_node->_data);}};
const_iterator:
template<class T>class ListconstIterator{public:typedef ListNode<T> Node;Node* _node;ListconstIterator(Node* node):_node(node){}ListconstIterator<T> operator++(){_node = _node->_next;return *this;}ListconstIterator<T> operator++(int){ListconstIterator<T> tem(*this);_node = _node->_next;return tem;}ListconstIterator<T> operator--(){_node = _node->_prev;return *this;}bool operator!=(ListconstIterator<T> it){return _node != it._node;}bool operator==(ListconstIterator<T> it){return _node == it._node;}ListconstIterator<T> operator--(int){ListconstIterator<T> tem(*this);_node = _node->_prev;return tem;}const T& operator *(){return _node->_data;}const T* operator->()//指向内容不能修改{return &(_node->_data);}};
对const_iterator的实现,因为指向内容不能修改,所以又封装了一个类来实现,其实还有另一种方法更为便捷,那就是增加两个模版参数
template<class T,class Ptr,class Ref>class ListIterator {public:typedef ListNode<T> Node;Node* _node;ListIterator(Node* node):_node(node)//用node初始化{}ListIterator<T,Ptr,Ref> operator++(){_node = _node->_next;return *this;}ListIterator<T, Ptr, Ref> operator++(int){ListIterator<T, Ptr, Ref> tem(*this);//拷贝构造,浅拷贝_node = _node->_next;return tem;}ListIterator<T, Ptr, Ref> operator--(){_node = _node->_prev;return *this;}bool operator!=(ListIterator<T, Ptr, Ref> it){return _node != it._node;}bool operator==(ListIterator<T, Ptr, Ref> it){return _node == it._node;}ListIterator<T, Ptr, Ref> operator--(int){ListIterator<T, Ptr, Ref> tem(*this);//拷贝构造,浅拷贝,不需要写赋值和拷贝构造,都是浅拷贝_node = _node->_prev;return tem;}Ptr operator *(){return _node->_data;}Ref operator->(){return &(_node->_data);}};
typedef ListIterator<T,T& , T*> iterator;
typedef ListIterator<T,const T&,const T*> const_iterator;增加两个模板参数后,编译器进行实例化时会帮你生成两个类
需要注意的几点:
1.这个类不用自己写拷贝构造和赋值运算符重载,因为编译器会默认生成,仅仅浅拷贝就7可以了
2.对->运算符的解释:
class Pos{public:Pos(int x=0,int y=0):_x(x),_y(y){}//private:int _x;int _y;};void test3(){list<Pos> lt;lt.push_back(Pos(1,1));lt.push_back(Pos(2, 2));lt.push_back(Pos(3, 3));lt.push_back(Pos(4, 4));list<Pos>::iterator it = lt.begin();while (it != lt.end()){//cout << *it << " ";错误//cout << it.operator->()->_x<<" "<<it.operator->()->_y << " ";cout << it->_x<<it->_y;//与上面等价it++;}cout << endl;}
当自定义类型没有重载流插入不能够直接打印数据,但调用->可以很好地解决问题,其实it->_x与it.operator->()->_x等价,只写一个->是为了可读性
构造:
void Init_list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){Init_list();}
list(initializer_list<T> il){Init_list();//先创造一个头结点for (const auto& e : il){push_back(e);}}
拷贝构造:
list(const list<T>& lt){Init_list();for (const auto& e : lt){push_back(e);}}
赋值运算符重载:
list<T>& operator=( list<T> lt){std::swap(lt._head, _head);return *this;}
析构函数:
~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it=erase(it);}}
push_back:
void push_back(const T& val){Node* newnode = new Node(val);newnode->_next = _head;newnode->_prev = _head->_prev;_head->_prev->_next = newnode;_head->_prev = newnode;}
pop_back:
void pop_back(){Node* tem = _head->_prev;_head->_prev->_prev->_next = _head;_head->_prev = _head->_prev->_prev;delete tem;tem = nullptr;}
insert:
iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* pcur = pos._node;newnode->_next = pcur;newnode->_prev = pcur->_prev;pcur->_prev->_next = newnode;pcur->_prev = newnode;return iterator(newnode);}
这里的插入不会出现迭代器失效问题
erase:
iterator erase(iterator pos){assert(pos != end());Node* pcur = pos._node;Node* next = pcur->_next;pcur->_prev->_next = pcur->_next;pcur->_next->_prev = pcur->_prev;delete pcur;pcur = nullptr;return iterator(next);}
erase会出现迭代器失效问题,该函数返回删除位置的下一个位置的迭代器,所以进行删除后要及时更新迭代器
push_front:
void push_front(const T& val){insert(begin(), val);}
pop_front:
void pop_front(){assert(begin() != end());erase(begin());}