档案网站建设优秀代表,门户网站开发 南宁,常州工厂网站建设,小制作小发明手工小学生文章目录 前言大体框架#xff1a; 一、节点的封装#xff08;list_node#xff09;二、迭代器的封装(_list_iterator)1.类模板的定义#xff1a;2.构造函数3.前置#xff0c;后置4.前置--#xff0c;后置--5.解引用(operator*())6. -重载#xff08;operator- … 文章目录 前言大体框架 一、节点的封装list_node二、迭代器的封装(_list_iterator)1.类模板的定义2.构造函数3.前置后置4.前置--后置--5.解引用(operator*())6. -重载operator- ()7.比较运算符的重载 三、list成员函数1.构造函数2.begin(),end()3.插入insert在pos之前一个位置插入4.删除erase5.尾插尾删6.头插头删7.析构函数8.赋值运算符重载9.拷贝构造函数10.大小size 前言 list的底层结构为带头结点的双向循环链表 大体框架
namespace simulation {template class Tstruct list_node {//成员函数};
templateclass T,class Ref,class Ptrstruct _list_iterator {//成员函数};templateclass Tclass list {typedef list_nodeT Node;public:typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;//成员函数private:Node* _head;size_t _size;};}
一、节点的封装list_node
template class Tstruct list_node {//带头的双向循环链表//在类模板中//类名不等于类型所以定义指针时类名要显示实例化list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const TvalT())//T相当于调用构造函数:_prev(nullptr),_next(nullptr),_val(val){}};二、迭代器的封装(_list_iterator) 因为list的数据不是在一片连续的内存中像vectorstring那样 所以我们不能用原生指针来当迭代器iterator我们要自己设计一个 迭代器自己去实现其以及比较等操作 1.类模板的定义
//设计const迭代器可以把迭代器理解为类似指针// 错误示范 typedef const __list_iteratorT const_iterator;// 这样设计const迭代器是不行的因为const迭代器期望指向内容不能修改// 这样设计是迭代器本身不能修改//为了设计不那么繁琐我们传入三个模板参数templateclass T,class Ref,class Ptr//相当于// typedef __list_iteratorT, T, T* iterator;// typedef __list_iteratorT, const T, const T* const_iterator;2.构造函数
typedef list_nodeT Node;typedef _list_iteratorT, Ref, Ptr self;Node* _node;//成员变量_list_iterator(Node* node):_node(node){}3.前置后置
self operator() {//前置//typedef _list_iteratorT, Ref, Ptr self;_node _node-_next;return *this;}self operator(int) {//后置self tmp(*this);_node _node-_next;return tmp;}4.前置–后置–
self operator--() {_node _node-_prev;return *this;}self operator--(int) {self tmp(*this);_node _node-_prev;return tmp;}5.解引用(operator*())
Ref operator*() {//因为可能为const T类型或者T类型//为了避免繁琐使用模板参数里面的Ref//编译器根据不同的类型会生成对应的函数return _node-_val;}6. -重载operator- () //templateclass T,class Ref,class Ptr//相当于// typedef __list_iteratorT, T, T* iterator;// typedef __list_iteratorT, const T, const T* const_iterator;
Ptr operator-() {return_node-_val;}7.比较运算符的重载 bool operator!(const self it)const {return _node ! it._node;}bool operator(const self it)const {return _node it._node;}三、list成员函数
1.构造函数
typedef list_nodeT Node;public:typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;void empty_init() {_size 0;_head new Node;_head-_prev _head;_head-_next _head;}list() {//构造函数empty_init();}privateNode*_head;//哨兵位size_t _size;
2.begin(),end() iterator begin() {//begin为哨兵位下一个return _head-_next;}const_iterator begin()const {return _head-_next;}//end为哨兵位iterator end() {return _head;}const_iterator end()const {return _head;}3.插入insert在pos之前一个位置插入 在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。 iterator insert(iterator pos, const T x) {Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);newnode-_prev prev;newnode-_next cur;prev-_next newnode;cur-_prev newnode;_size;//返回指向第一个新插入元素的迭代器。return newnode;}4.删除erase
iterator erase(iterator pos) {assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;--_size;//返回被删除节点的下一个位置return next;}5.尾插尾删 void push_front(const T x) {insert(begin(), x);}void pop_back() {erase(--end());}6.头插头删
void push_back(const Tx) {insert(end(), x);}
void pop_front() {erase(begin());}7.析构函数 void clear() {iterator it begin();while (it ! end()) {it erase(it);}_size 0;}~list() {clear();delete _head;_head nullptr;}8.赋值运算符重载
void swap(listTlt){std::swap(_head, lt._head);std::swap(_size, lt._size);}listToperator(listT lt) {swap(lt);return *this;}9.拷贝构造函数 list(const listT lt) {empty_init();_size lt._size;for (auto ch : lt) {push_back(ch);}}10.大小size
size_t size() {return _size;}
