做网站php都用什么框架,把asp.net写的网站别人怎么访问,博客营销案例,海口仿站定制模板建站目录 一、模拟实现前的准备 1.list结构认识 2.迭代器的实现不同 3.如何实现需要的功能 二.结点类实现 三.迭代器实现 1.实现前的问题 2._list_iterator类的成员变量和构造函数 3.*和-运算符重载 4.前置和后置的实现 5.前置--和后置-- 6.和!运算符重载 四.list类的实现 1.li… 目录 一、模拟实现前的准备 1.list结构认识 2.迭代器的实现不同 3.如何实现需要的功能 二.结点类实现 三.迭代器实现 1.实现前的问题 2._list_iterator类的成员变量和构造函数 3.*和-运算符重载 4.前置和后置的实现 5.前置--和后置-- 6.和!运算符重载 四.list类的实现 1.list类和构造函数 2.析构 3.拷贝构造函数 4.赋值运算符重载 5.迭代器 6.insert() 7.erase() 8.clear() 9.头插头删尾插尾删 10.判空 五.完整代码 一、模拟实现前的准备 1.list结构认识 1.STLe的list的底层结构其实是带头结点的双向循环链表双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 2.迭代器的实现不同 list插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响。list的迭代器是自定义类型对原生指针的封装模拟指针的行为那为什么不像vector那样直接用原生指针呢因为list的每个结点在物理结构上面不是连续的直接对结点其得到的不是下一个结点指针。 3.如何实现需要的功能 这里我们可以用三个类来模拟实现结点类和list迭代器类用struct封装因为我们不需要对其做访问限制而list类就用class类封装。 二.结点类实现
结点类实现比较简单不过我们需要注意
1需要用到模板方便以后使用不同的类型
2结点成员变量包括结点值、指向前一个结点的指针指向后一个结点的指针
3不需要析构函数没有额外申请空间
4用struct来实现对访问不做限制 templateclass T //list的结点结构对访问不做限制所以用structstruct list_node{list_nodeT* _next; //成员变量list_nodeT* _prev;T _data;list_node(const T x T()) //构造函数:_next(nullptr), _prev(nullptr), _data(x){}};三.迭代器实现
list的迭代器实现是整个实现过程中最精彩的部分尤其是模板里的多个参数可谓是把规则用到了极致涉及到的知识点也非常多我们不得不感叹STL大佬的实力。 1.实现前的问题 迭代器分为普通迭代器和const迭代器之前的迭代器由于是直接用的原生指针所以就算两种迭代器分开实现其代码量夜很小。但是对于_list_iterator类要实现的普通的_list_iterator和const版本的_list_const_iterator因为对于两个类中的部分函数有普通函数和const函数之分如begin( )和end( )其他并无区别。因为这两个类的大部分代码相似那么怎么解决呢
查看STL源码我们可以发现用下面的方法非常不错
迭代器模板用到了三个参数
templateclass T, class Ref, class Ptr
list在实例化时通过不同的参数实例出两个类一个是普通的不带const的TT T*另一个是带const的Tconst T const T*其中Ref是引用Ptr是指针该类模板实例化了以下这两个类模板
typedef __list_iteratorT, T, T* iterator; //非const 迭代器typedef __list_iteratorT, const T, const T* const_iterator; //const迭代器
这样我们就解决了代码冗余的问题大佬不愧是大佬。 2._list_iterator类的成员变量和构造函数 成员变量只有结点node构造函数负责初始化结点
templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT node; //typedef __list_iteratorT, Ref, Ptr self;node* _node; //成员变量__list_iterator(node* n) //构造函数:_node(n){}}; 3.*和-运算符重载
Ref operator*()
{
return _node-_data; //解引用之后我们需要得到拷贝的值所以返回引用
}Ptr operator-()
{
return _node-_data; //结构体指针解引用返回结点指针
}注意It-_dataIt是一个迭代器我们平时这样用没问题但是我们要知道这里其实省略了一个-,It-其实就是It.operator-()其返回值是_data*类型我们还需要It.operator-()-_data但是为了可读性编译器优化了一个箭头。 4.前置和后置的实现
self operator() //都需要用到自身所以是self
{
_node _node-_next;
return *this;
}self operator(int)
{
self tmp(*this);
_node _node-_next;
return tmp;
} 5.前置--和后置-- self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;} 6.和!运算符重载 bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;} 四.list类的实现 1.list类和构造函数
templateclass Tclass list //list类{typedef list_nodeT node;public:typedef __list_iteratorT, T, T* iterator; //非const 迭代器typedef __list_iteratorT, const T, const T* const_iterator; //const迭代器//typedef __list_const_iteratorT const_iterator;list(){_head new node; //默认构造函数_head-_next _head;_head-_prev _head;}private:node* _head; }; 2.析构
复用了后面的函数 ~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){//it erase(it);erase(it);}} 3.拷贝构造函数 void empty_init() //空初始化{_head new node;_head-_next _head;_head-_prev _head;}list(const listT lt){empty_init();for (auto e : lt){push_back(e);}} 4.赋值运算符重载
1现代的赋值运算符重载
void swap(listT tmp){std::swap(_head, tmp._head);}listT operator(listT lt){swap(lt);return *this;}
在执行赋值运算符重载时会调用拷贝构造函数执行深拷贝然后再交换两个链表头节点的指针把this要释放的资源交给临时对象临时对象出了swap的函数作用域就被this要释放的资源也会被同时释放。 5.迭代器 iterator begin(){//iterator it(_head-_next);//return it;return iterator(_head-_next); //匿名对象}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{//iterator it(_head-_next);//return it;return const_iterator(_head);} 6.insert()
先构造一个结点然后插入 void insert(iterator pos, const T x){node* cur pos._node;node* prev cur-_prev;node* new_node new node(x);prev-_next new_node;new_node-_prev prev;new_node-_next cur;cur-_prev new_node;} 7.erase()
删除后需要返回删除位置的下一个结点 iterator erase(iterator pos){assert(pos ! end());node* prev pos._node-_prev;node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;return iterator(next);} 8.clear()
不能把哨兵卫清理了否则链表就不存在了 void clear(){iterator it begin();while (it ! end()){//it erase(it);erase(it);}} 9.头插头删尾插尾删
这里直接复用insert()和erase() void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());} 10.判空
bool empty()
{return end()begin();
} 五.完整代码 #pragma once
#includeassert.h
#includeiostreamnamespace bit
{templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _data;list_node(const T x T()):_next(nullptr), _prev(nullptr), _data(x){}};// 1、迭代器要么就是原生指针// 2、迭代器要么就是自定义类型对原生指针的封装模拟指针的行为templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;node* _node;__list_iterator(node* n):_node(n){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}self operator(){_node _node-_next;return *this;}self operator(int){self tmp(*this);_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}};templateclass Tclass list{typedef list_nodeT node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;//typedef __list_const_iteratorT const_iterator;iterator begin(){//iterator it(_head-_next);//return it;return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{//iterator it(_head-_next);//return it;return const_iterator(_head);}void empty_init(){_head new node;_head-_next _head;_head-_prev _head;}list(){empty_init();}template class Iteratorlist(Iterator first, Iterator last){empty_init();while (first ! last){push_back(*first);first;}}// lt2(lt1)/*list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}*/void swap(listT tmp){std::swap(_head, tmp._head);}list(const listT lt){empty_init();listT tmp(lt.begin(), lt.end());swap(tmp);}// lt1 lt3listT operator(listT lt){swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){//it erase(it);erase(it);}}void push_back(const T x){/*node* tail _head-_prev;node* new_node new node(x);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){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T x){node* cur pos._node;node* prev cur-_prev;node* new_node new node(x);prev-_next new_node;new_node-_prev prev;new_node-_next cur;cur-_prev new_node;}iterator erase(iterator pos){assert(pos ! end());node* prev pos._node-_prev;node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;return iterator(next);}bool empty(){return end()begin();}private:node* _head;};
}
