建设网站教程视频视频,能源企业 网站建设,取消网站备案时间,网站运营的工作内容前言 list是STL中重要的容器#xff0c;了解它的原理对于我们掌握它是有很多的帮助的#xff0c;一般list和vector都是一起来使用的#xff0c;因为它们的优缺点不同#xff0c;刚好可以互补。list的优点是任意位置的插入和删除都很快#xff0c;它的缺点是不支持随机访问…前言 list是STL中重要的容器了解它的原理对于我们掌握它是有很多的帮助的一般list和vector都是一起来使用的因为它们的优缺点不同刚好可以互补。list的优点是任意位置的插入和删除都很快它的缺点是不支持随机访问而vector的优点是支持随机访问进而就可以很好的支持排序算法二分查找堆算法等它的缺点是扩容要付出一定的代价而且除了尾上的插入和删除外其他位置的插入和删除都不快因为要挪动数据。下面让我们一起来实现一下list吧。
list的实现代码
#includeiostream
using namespace std;
namespace qyy
{
templateclass T
struct __list_node
{__list_node(const T data T())//构造函数函数:_prev(nullptr), _next(nullptr), _data(data){ }__list_nodeT* _prev;//前指针__list_nodeT* _next;//后指针T _data;//数据
};templateclass T, class Ref, class Ptr
struct __list_iterator//对链表的迭代器进行封装
{typedef __list_nodeT Node;typedef __list_iterator T, Ref, Ptr iterator;__list_iterator(Node* node)//构造函数:_node(node){ }//对指针行为的模仿Ref operator* (){return _node-_data;}Ptr operator-(){return (_node-_data);}iterator operator()//前置{_node _node-_next;return *this;}iterator operator--()//前置--{_node _node-_prev;return *this;}iterator operator(int)//后置{//Node tmp(_node);iterator tmp(*this);_node _node-_next;return tmp;}iterator operator--(int)//后置--{//Node tmp(_node);iterator tmp(*this);_node _node-_prev;return tmp;}bool operator(const iterator it){return _node it._node;}bool operator!(const iterator it){return _node ! it._node;}public:Node* _node;//存放一个节点的指针
};templateclass T
class list//带头双向循环链表
{
public:typedef __list_nodeT Node;//节点的重定义typedef __list_iteratorT,T,T* iterator;//迭代器重定义typedef __list_iteratorT, const T, const T* const_iterator;iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head-_next);}const_iterator end()const{return const_iterator(_head);}list()//构造函数:_head(new Node){_head-_next _head;_head-_prev _head;}list(const listT l1)//拷贝构造{_head new Node;//初始化头结点_head-_next _head;_head- _prev _head;const_iterator it l1.begin();while (it ! l1.end()){push_back(it._node-_data);//将节点插入it;}}listT operator(listT l1)//现代写法{if (this ! l1){swap(_head, l1._head);}return *this;}listT operator(const listT l1)const{clear();const_iterator it l1.begin();while (it ! l1.end()){push_back(it._node-_data);//将节点插入it;}return *this;}~list(){clear();//删除头结点以外的其他节点delete _head;//删除头结点}void clear()//除了头结点剩下的节点全部删除{if (begin() ! end())//判断不能删除头结点{iterator it begin();while (it ! end()){it erase(it);//删除当前节点之后迭代器就会 失效所以要用it来接收下一个节点的迭代器}}}void push_back(const T data)//尾插{//Node* tail _head-_prev;//Node* newNode new Node(data);//申请节点三个节点的相互链接//tail-_next newNode;//newNode-_prev tail;//_head-_prev newNode;//newNode-_next _head;insert(end(), data);//调用任意节点的插入来实现头删}void pop_back()//尾删{//assert(_head-_next ! _head);//除了头结点还有其他节点——因为头结点是不可以被删除的//Node* tail _head-_prev;//找到尾节点断开链接//Node* newtail tail-_prev;//找新的尾节点进行头尾链接//newtail-_next _head;//_head-_prev newtail;//delete tail;//删除尾节点//调用erase进行尾删erase(--end());}void push_front(const Tdata)//头插{//Node* newHead new Node(data);//申请新的节点//Node* oldHead _head-_next;进行链接//_head-_next newHead;//newHead-_prev _head;//newHead-_next oldHead;//oldHead-_prev newHead;//调用任意节点的插入和删除insert(begin(), data);}void pop_front()//头删{//assert(_head-_next ! _head);//除了头结点还有其他节点——因为头结点是不可以被删除的//Node* head _head-_next;//找到头节点断开链接//Node* newHead head-_next;//找新的尾节点进行链接//newHead-_prev _head;//_head-_next newHead;//delete head;//删除尾节点//调用erase进行头删erase(begin());}void insert(iterator pos, const T data)//{//申请新节点Node* newNode new Node(data);Node* prev pos._node-_prev;//迭代器前一个节点Node* next pos._node;//迭代器当前节点prev-_next newNode;newNode-_prev prev;next-_prev newNode;newNode-_next next;}iterator erase(iterator pos)//删除pos位置的值{assert(pos._node !_head);//不能删除头结点Node* cur pos._node;Node* prev pos._node-_prev;Node* next pos._node-_next;//断开当前迭代器所在节点的位置将迭代器前后节点进行链接prev-_next next;next-_prev prev;//保存下一个位置的迭代器iterator it1 pos;//记录下一个位置的迭代器//删除当前迭代器的节点delete cur;cur nullptr;return it1;//返回下一个位置的迭代器}
private:Node* _head;//头结点
};
} 1.构造函数和析构函数 1.1构造函数 构造函数主要完成的是对头结点的初始化如下
templateclass T//先定义结点类
struct __list_node
{__list_node(const T data T())//构造函数函数:_prev(nullptr), _next(nullptr), _data(data){ }__list_nodeT* _prev;//前指针__list_nodeT* _next;//后指针T _data;//数据
};
templateclass T//构造函数多头结点进行初始化
list()//构造函数:_head(new Node)
{_head-_next _head;_head-_prev _head;
} 2.2析构函数 析构函数主要完成对资源的清理这里通过调用clear对链表的节点进行删除。最后在删除头结点。
~list()
{clear();//删除头结点以外的其他节点delete _head;//删除头结点
}
2.operator的重载和拷贝构造函数 2.2拷贝构造 这里是通过对头结点进行初始化之后调用push_back函数尾插数据完成的拷贝构造。
list(const listT l1)//拷贝构造
{_head new Node;//初始化头结点_head-_next _head;_head- _prev _head;const_iterator it l1.begin();while (it ! l1.end()){push_back(it._node-_data);//将节点插入it;}
} 2.2operator的重载 operator赋值有两种写法一种是传统写法另一种是现代写法如下
//传统写法--
listT operator(const listT l1)
{if (this ! l1)//防止对象自己给自己赋值{clear();//先清理之前链表中的内容,然后通过调用push_back将l1中的内容插入const_iterator it l1.begin();while (it ! l1.end()){push_back(it._node-_data);//将节点插入it;}return *this;}
}
//现代写法
listT operator(listT l1)//现代写法
{if (this ! l1)//先拷贝构造一个对象,然后调用STL中的swap函数交换this指向的头结点的指针和 { //l1中头结点指针出了作用域临时对象l1就会被析构不要担心内存泄漏的问题swap(_head, l1._head);}
return *this;
}
3.迭代器的实现 list的迭代器比较特殊他不是原生的指针而是将节点的指针进行封装然后重载operator*operator,operator--等与指针相关的操作符来模拟指针的行为。 3.1普通迭代器 templateclass Tstruct __list_node{__list_node(const T data T())//构造函数函数:_prev(nullptr),_next(nullptr),_data(data){ }__list_nodeT* _prev;//前指针__list_nodeT* _next;//后指针T _data;//数据};templateclass Tstruct __list_iterator//对链表的节点进行封装{typedef __list_nodeT Node;__list_iterator(Node*node)//构造函数:_node(node){ }//对指针行为的模仿T operator* (){return _node-_data;}__list_iteratorT operator()//前置{_node _node-_next;return *this;}__list_iteratorT operator--()//前置--{_node _node-_prev;return *this;}__list_iteratorT operator(int)//后置{Node tmp(_node);_node _node-_next;return tmp;}__list_iteratorT operator--(int)//后置--{Node tmp(_node);_node _node-_prev;return tmp;}bool operator(const __list_iteratorTit){return _node it._node;}bool operator!(const __list_iteratorT it){return _node ! it._node;}T* operator-(){return (_node-_data);}public:Node *_node;//存放一个节点的指针}; 注意实现operator-的意义如果有下面的这种情况list存的不是一个内置类型而是一个自定义类型这时想要通过迭代器去访问里面的成员就会用来operator-,如下 class Date{public:Date():_year(0), _month(1), _day(1){ }public:int _year;int _month;int _day;};void TestList2(){list Date l1;Date d1, d2;l1.push_back(d1);l1.push_back(d2);listDate::iterator it l1.begin();cout it-_year it-_month it-_day;//访问list中存放的Date} 其实 it-_year是it-_node-_year,只是编译器对其进行了简化。 3.2const类型的迭代器 const类型的对象只能使用const类型的迭代器那么const类型的迭代器如何实现呢、需要再重新封装吗像上面那样可以但是没有必要因为那样代码的冗余度就会很高我们只需要给模板增加两个参数就可以了。templateclass T, class Ref, class Ptr。实现如下
templateclass T, class Ref, class Ptr
struct __list_iterator//对链表的迭代器进行封装
{typedef __list_nodeT Node;typedef __list_iterator T, Ref, Ptr iterator;__list_iterator(Node* node)//构造函数:_node(node){ }//对指针行为的模仿Ref operator* (){return _node-_data;}Ptr operator-(){return (_node-_data);}iterator operator()//前置{_node _node-_next;return *this;}iterator operator--()//前置--{_node _node-_prev;return *this;}iterator operator(int)//后置{//Node tmp(_node);iterator tmp(*this);_node _node-_next;return tmp;}iterator operator--(int)//后置--{//Node tmp(_node);iterator tmp(*this);_node _node-_prev;return tmp;}bool operator(const iterator it){return _node it._node;}bool operator!(const iterator it){return _node ! it._node;}public:Node* _node;//存放一个节点的指针
}; 这样看貌似看不出来这两个参数有什么用这两个参数一个代表T*一个代表T这样就可以解决代码冗余的问题在实例化的时候给模板不同的参数就可以实例化不同的内容
4.增删查改 4.1尾删尾插 void push_back(const T data)//尾插{Node* tail _head-_prev;Node* newNode new Node(data);//申请节点//三个节点的相互链接tail-_next newNode;newNode-_prev tail;_head-_prev newNode;newNode-_next _head;}void pop_back()//尾删{assert(_head-_next ! _head);//除了头结点还有其他节点——因为头结点是不可以被删除的Node* tail _head-_prev;//找到尾节点//断开链接Node* newtail tail-_prev;//找新的尾节点//进行头尾链接newtail-_next _head;_head-_prev newtail;delete tail;//删除尾节点} 4.2任意位置的插入和删除 void insert(iterator pos, const T data)//{//申请新节点Node* newNode new Node(data);Node* prev pos._node-_prev;//迭代器前一个节点Node* next pos._node;//迭代器当前节点prev-_next newNode;newNode-_prev prev;next-_prev newNode;newNode-_next next;}iterator erase(iterator pos)//删除pos位置的值{assert(pos._node !_head);//不能删除头结点Node* cur pos._node;Node* prev pos._node-_prev;Node* next pos._node-_next;//断开当前迭代器所在节点的位置将迭代器前后节点进行链接prev-_next next;next-_prev prev;//保存下一个位置的迭代器iterator it1 pos;//记录下一个位置的迭代器//删除当前迭代器的节点delete cur;cur nullptr;return it1;//返回下一个位置的迭代器} 4.3头插头删 头插头删可以复用上面的insert和erase如下 void push_front(const Tdata)//头插{insert(begin(), data);}void pop_front()//头删{erase(begin());} 5.测试代码
#includeassert.h
#includelist.hppvoid Print(const qyy::listint l1);//测试
void TestList()
{qyy::listintl1;//头删l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);for (auto e : l1){cout e ;}cout endl;Print(l1);//尾删l1.pop_back();l1.pop_back();l1.pop_back();l1.pop_back();l1.pop_back();}
void Print(const qyy::listint l3)
{qyy::listint::const_iterator it l3.begin();while (it ! l3.end()){//*it 1;cout *it ;it;}cout endl;
}
void TestList2()
{qyy::listint l2;//头插l2.push_front(1);l2.push_front(2);l2.push_front(3);l2.push_front(4);l2.push_front(5);l2.push_front(6);for (auto e : l2){cout e ;}//头删l2.pop_front();l2.pop_front();l2.pop_front();l2.pop_front();l2.pop_front();l2.pop_front();//l2.pop_front();//l2.clear();
}
void TestList3()
{qyy::listint l3;//头插l3.push_back(1);l3.push_back(2);l3.push_back(3);l3.push_back(4);l3.push_back(5);for (auto e : l3)cout e ;qyy::listint l4(l3);l3 l4;//测试operator
}
