【C++篇】list模拟实现
实现接口：
-
list的无参构造、n个val构造、拷贝构造
-
operator=重载
-
实现迭代器
-
push_back()
-
push_front()
-
erase()
-
insert()
-
头尾删
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace liu
{//定义list节点template<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x=T()):_data(x),_prev(nullptr),_next(nullptr){}};template<class T,class Ref,class Ptr>struct list_iterator{typedef list_node<T>Node;typedef list_iterator<T, Ref, Ptr>Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};template<class T>class list{//链表存储链表节点typedef list_node<T> Node;public://实现接口typedef list_iterator<T, T&, T*>iterator;typedef list_iterator<T, const T&, const T*> const_iterator;void empty_init(){_head = new Node();_head->_prev = _head;_head->_next = _head;}list()//无参构造{empty_init();}list(size_t n,const T& val=T())//n个val{empty_init();for (int i=0;i<n;i++){push_back(val);}}list(const list<T>& i1){empty_init();for(auto& x:i1){push_back(x);}}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it!=end()){it=erase(it);}}iterator begin(){return iterator(_head->_next);}const_iterator begin()const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}iterator insert(iterator pos,const T&val){Node* new_node = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = new_node;new_node->_prev = prev;cur->_prev = new_node;new_node->_next = cur;return iterator(new_node);}iterator erase(iterator pos){assert(pos!=end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;return iterator(next);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void swap(list<T>& i1){std::swap(_head,i1._head);}list<T>& operator=(list<T> il){swap(il);return *this;}void push_back(const T& x){/*Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(),x);}void push_front(const T& x){/*Node* new_node = new Node(x);Node* prev = _head->_next;_head->_next = new_node;new_node->_prev = _head;prev->_prev = new_node;new_node->_next = prev;*/insert(begin(), x);}private:Node* _head;//双端链表，哨兵位};template<class T>void swap(T&a,T& b){T c(a);a = b;b = c;}template<class T>void swap(list<T>& a, list<T>& b){a.swap(b);}void test1(){/*liu::list<int>i1;i1.push_back(1);i1.push_back(2);i1.push_back(3);i1.push_back(4);i1.push_front(5);i1.push_front(6);i1.push_front(7);liu::list<int>::iterator it1 = i1.begin();while (it1!=i1.end()){cout << *it1 << " ";++it1;}cout << endl;liu::list<int>::iterator it2 = i1.begin();it2=i1.erase(it2);while (it2 != i1.end()){cout << *it2 << " ";++it2;}*/liu::list<int>i1(10,1);liu::list<int>i2(10,2);liu::swap(i1, i2);for (auto x : i2){cout << x << " ";}cout << endl;for (auto x : i1){cout << x << " ";}cout << endl;}
}