上海知名网站开发公司,xampp wordpress安装教程,江西省建设厅网站,综合查询目录
一.list的基本结构
二. 接下来就是对list类构造函数的设计了#xff1a;
三.链表数据的增加#xff1a;
四.接下来就是迭代器的创建了#xff1a;
四.简单函数的实现#xff1a;
五.构造与析构 六.拷贝构造和赋值重载
传统写法:
现代写法#xff1a;
七.迭…目录
一.list的基本结构
二. 接下来就是对list类构造函数的设计了
三.链表数据的增加
四.接下来就是迭代器的创建了
四.简单函数的实现
五.构造与析构 六.拷贝构造和赋值重载
传统写法:
现代写法
七.迭代器模板类型 一.list的基本结构 想要模拟实现list类就需要先了解它的底层架构上篇博客讲到list容器的底层是双向链表那么就需要自定义一个节点类通过节点类可以创建节点设置节点的前后指针和数据值。之后便可以通过该类类型创建list类的成员变量。 templateclass T
struct list_node { //该类为内部类是list的内部类list_node(const T val):_next(nullptr), _prev(nullptr), _data(val) {}//成员变量list_node* _next; //后指针list_node* _prev; //前指针T _data; //值
};templateclass T
class list {public:typedef list_nodeT node; //将节点类作为类类型private:node* _head; //指向堆区空间链表的指针size_t _size; //计数
};node* 类型就好比是对节点类的封装。 二. 接下来就是对list类构造函数的设计了 templateclass T
class list {public:typedef list_nodeT node; //将节点类作为类类型//初始化操作void empty_Init() {_head new node(T());_head-_next _head;_head-_prev _head;_size 0;}list() //构造函数:_head(nullptr),_size(0){empty_Init();}private:node* _head; //指向堆区空间链表的指针size_t _size; //计数
}; 对构造函数的初始化设计就是创建哨兵位头结点让链表指针指向哨兵位头结点由哨兵头节点去控制节点的增删查改避免了由链表指针去控制操作和形式上都方便了很多。 注哨兵位头结点的创建是在empty_Init()函数中进行的 三.链表数据的增加
templateclass T
class list{public:typedef NodeT node;//尾插 void push_back(const T val) {node* newnode new node(val);node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;_size;}//尾删void pop_back() {assert(!empty());node* tail _head-_prev;node* last tail-_prev;last-_next _head;_head-_prev last;delete tail;--_size;}//头插void push_front(const T val) {node* newnode new node(val);node* first _head-_next;_head-_next newnode;newnode-_prev _head-_next;newnode-_next first;first-_prev newnode;_size;}//头删void pop_front() {assert(!empty());node* first _head-_next;node* second first-_next;_head-_next second;second-_prev _head-_next;delete first;--_size;}//任意位置的插入iterator insert(iterator pos, const T valT()) {if (pos this-begin()) {push_front(val); //复用代码}else if (pos this-end()) {push_back(val); //复用代码}else {node* newnode new node(val);node* cur pos.phead;node* last cur-_prev;last-_next newnode;newnode-_prev last;newnode-_next cur;cur-_prev newnode;_size;}return pos;}//任意位置的删除iterator erase(iterator pos) {assert(!empty());if (pos this-begin()) {pop_front();}else if (pos this-end()) {pop_back();}else {node* cur pos.phead;node* tail cur-_next;node* last cur-_prev;last-_next tail;tail-_prev last;delete cur;--_size;}return pos;}private:node* _head; //指向堆区空间链表的指针size_t _size; //计数}; 对于数据的增加和删除头插头删、尾插尾删简单就不说了重点是insert和erase函数的实现如上代码在insert和erase中各有三种情况其中头尾的操作直接复用函数即可对于中间位置的插入删除情况我想说的是指定的pos参数是iterator类型——自定义迭代器类它是指针 它只是指向该节点元素的位置所以想要获取该位置的节点就需要pos.phead才能获取到该节点只有获取到该节点才能使用该节点附近的前后指针 四.接下来就是迭代器的创建了 在对vector、String容器的模拟实现中我并没有单独创建迭代器这是因为这两个容器的底层都是数组是一段连续的地址空间对于迭代器中的成员begin、end都是可以直接让指针进行类型的字节/--进行的很方便的是使用原生指针来确定位置 而对于list容器来说它的底层是链表各个节点的位置是不连续的随机的。使用原生指针并不能遍历到每一个对象的元素所以针对list容器需要创建一个自定义类型的迭代器进行链表的遍历。
templateclass Tstruct list_iterator{typedef list_nodeT node;node* _pnode; //成员变量list_iterator(node* p) //构造函数:_pnode(p){}T operator*(){ //指针解引用return _pnode-_data;}list_iteratorT operator(){ //指针_pnode _pnode-_next;return *this;}bool operator!(const list_iteratorT it){ //!运算符重载return _pnode ! it._pnode;}};templateclass Tclass list{public:typedef list_nodeT node;typedef list_iteratorT iterator;iterator begin(){return iterator(_head-_next);}iterator end(){//iterator it(_head);//return it;return iterator(_head);}};在自定义的迭代器类中我根据平常练习vector、String的迭代器代码中写了几个一定会用到的运算符重载函数解引用、指针遍历所用到的!等函数。 写好自定义迭代器类后需要在list类中重命名该类。 写好迭代器后我们就可以试验一下了 注上面的迭代器只是普通迭代器的实现还会有const迭代器、反向迭代器需要实现意味着还得再写两个迭代器类。 四.简单函数的实现
templateclass T
class list{public:size_t size()const {return _size;//方法2利用指针遍历每遍历一次记一次数}bool empty() const {//方法1return _size 0;//方法2return _head-next_head;}void clear() {node* cur _head-_next;while (cur ! _head) {node* del cur;cur cur-_next;delete del;}cur-_next _head;cur-_prev _head;_size 0;}T front() {return this-begin().phead-_data;}T back() {return this-end().phead-_prev-_data;}private:node* _head;size_t _size;};五.构造与析构 有了迭代器我们就可以对list构造函数进行迭代器区间构造实现了
templateclass T
class list{
public://迭代器区间构造函数templateclass Inputiteratorlist(Inputiterator first, Inputiterator last) { empty_Init();while (first ! last) {push_back(*first);first;}}void empty_Init() {_head new node(T());_head-_next _head;_head-_prev _head;_size 0;}list() //无参构造{empty_Init();}//析构函数~list() {this-clear();delete _head;_head nullptr;_size 0;}
private:node* _head;size_t _size;
}; 析构函数就是遍历链表中每个节点都进行遍历释放置空指针置零变量。 六.拷贝构造和赋值重载 传统写法:
//拷贝构造——传统写法list(const listT lt) {empty_Init();for (auto e : lt) {this-push_back(e);}}//赋值重载函数——传统写法listT operator(const listT lt) {if (this ! lt) {this-clear();}for (const auto e : lt) {this-push_back(e);}return *this;} 拷贝构造和赋值重载本质上都相同都是复制已有的list对象然后深拷贝数据给自己。深拷贝就是创建一个属于自己的头结点剩下的数据就是浅拷贝(无脑将数据以遍历的方式让自己的头指针进行指针链接)。 现代写法 //调用std库中swap函数进行成员交换void Swap(listT lt) {std::swap(this-_head, lt._head);std::swap(this-_size, lt._size);} //拷贝构造——现代写法list(const listT lt) {empty_Init();listT tmp(lt.begin(), lt.end()); //调用迭代器区间构造函数this-Swap(tmp);}//赋值重载——现代写法listT operator(listT lt) {this-Swap(lt); //值传递形参的改变不影响实参return *this;} 七.迭代器模板类型 上面讲迭代器的最后说了迭代器有普通版、const版、反向版、反向const版意味着我们需要创建四个迭代器类型但迭代器能用到的运算符重载函数都一样都是解引用、指针、!运算符。
//自定义普通迭代器类
templateclass Tstruct list_iterator{typedef list_nodeT node;node* _pnode;list_iterator(node* p):_pnode(p){}T operator*(){return _pnode-_data;}list_iteratorT operator(){_pnode _pnode-_next;return *this;}list_iteratorT operator--(){_pnode _pnode-_prev;return *this;}bool operator!(const list_iteratorT it){return _pnode ! it._pnode;}};//const迭代器类templateclass Tstruct list_const_iterator{typedef list_nodeT node;node* _pnode;list_const_iterator(node* p):_pnode(p){}const T operator*(){return _pnode-_data;}list_const_iteratorT operator(){_pnode _pnode-_next;return *this;}list_const_iteratorT operator--(){_pnode _pnode-_prev;return *this;}bool operator!(const list_const_iteratorT it){return _pnode ! it._pnode;}};templateclass Tclass list{typedef list_nodeT node;public:typedef list_iteratorT iterator;typedef list_const_iteratorT const_iterator;const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);} 如上普通迭代器类和const迭代器类唯一的区别是在遍历上const迭代器类的解引用运算符重载函数中不能用*it修改数据那么这俩迭代器类中其他函数的实现完全一样这极大的造成了代码的冗余降低了可读性 于是为了在一种迭代器类中体现不同类型的迭代器可以这样做:
templateclass T, class Ref, class Ptr
struct _list_iterator {typedef list_nodeT node;typedef _list_iteratorT, Ref,Ptr Self; //Self是T与ref,ptr 模板类型的另一种别称//迭代器构造函数_list_iterator(node* p):_pnode(p) {}//解引用Ref operator*() {return _pnode-_data;}//箭头只有是结构体才可以用Ptr operator-() {return _pnode-_data; //返回的是该结点的地址}Self operator() {_pnode _pnode-_next;return *this;}//后置使用占位符int与前置以示区分Self operator(int) {Self tmp(*this);_pnode _pnode-_next;return tmp;}//前置--Self operator--() {_pnode _pnode-_prev;return *this;}//后置--Self operator--(int) {Self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const Self lt) const {return _pnode ! lt._pnode;}bool operator(const Self lt) const{return _pnode lt._pnode;}node* _pnode;
};在迭代器类中采用了三个模板参数。这三个模板参数T代表泛型值Ref代表泛型引用Ptr代表泛型指针这三种参数主要应用于运算符重载函数的函数返回值函数形参相当方便一举多得通过不同实参的传递就可以调用不同类型的函数。 templateclass T
class list {
public:typedef list_nodeT node;typedef _list_iteratorT, T, T* iterator;//typedef list_const_iteratorT const_iterator;typedef _list_iteratorT, const T, const T* const_iterator; 完整模拟实现代码 .h文件
#includeiostream
#includeassert.husing std::cout;
using std::endl;templateclass T
struct list_node { //该类为内部类是list的内部类list_node(const T val):_next(nullptr), _prev(nullptr), _data(val) {}//成员变量list_node* _next;list_node* _prev;T _data;
};//typedef list_iteratorT, T iterator;
//typedef list_iteratorT, const T const_iterator;//这种写法来源vectorint,vectorstring,vectorvectorint
templateclass T, class Ref, class Ptr //新增一个模板参数 T是一种类型ref是一种类型
struct list_iterator {typedef list_nodeT node;typedef list_iteratorT, Ref, Ptr Self; //Self是T与ref,ptr 模板类型的另一种别称//迭代器构造函数list_iterator(node* p):_pnode(p) {}//在下面的运算符重载中const版与非const版只有解引用运算符重载函数的类型不同其他运算符重载都一样//所以operator* 的类型需要使用ref,ref可以理解为constT, 而非const对象也可以调用const函数权限够//const对象不可调用非const函数权限不够所以使用ref//解引用Ref operator*() {return _pnode-_data;}//箭头只有是结构体才可以用Ptr operator-() {return _pnode-_data; //返回的是该结点的地址}//前置//为啥要用引用 原因return *this ,this迭代器对象出了该函数体还存在this的生命周期在该类中是全局的Self operator() {_pnode _pnode-_next;return *this;//既然this还在那么直接用引用返回栈帧中不开临时空间减少拷贝次数提高效率//记住使用引用返回的前提是要返回的值出了函数体仍在才可以使用否则会报错}//后置使用占位符int与前置以示区分Self operator(int) {Self tmp(*this);_pnode _pnode-_next;return tmp;//返回tmp后tmp为临时对象出了函数就消失了tmp对象不在需要拷贝那就得用传值返回在栈帧中//创建一个临时空间去接收返回的tmp对象数据。设置一个默认参数和前置做区分构成函数重载。//若使用引用返回那么该函数结束后返回的tmp已经不存在了引用返回返回野指针随机值就会报错}Self operator--() {_pnode _pnode-_prev;return *this;}//后置--Self operator--(int) {Self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const Self lt) const {return _pnode ! lt._pnode;}bool operator(const Self lt) const{return _pnode lt._pnode;}node* _pnode;
};//--------------------------------------------------------------------------------templateclass T
class list {
public:typedef list_nodeT node;typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;void empty_Init() {_head new node(T());_head-_next _head;_head-_prev _head;_size 0;}list(){empty_Init();}//析构~list() {this-clear();delete _head;_head nullptr;_size 0;}templateclass Inputiteratorlist(Inputiterator first, Inputiterator last) { //拷贝构造的天选打工人//先初始化给头节点否则没法继续empty_Init();while (first ! last) {push_back(*first);first;}}void swap(listT lt) {std::swap(this-_head, lt._head);std::swap(this-_size, lt._size);}void clear() {iterator it this-begin();while (it ! this-end()) {it this-erase(it);}}//拷贝构造——传统写法/*list(const listT lt) {empty_Init();for (auto e : lt) {this-push_back(e);}}*///拷贝构造——现代写法list(const listT lt) {empty_Init();listT tmp(lt.begin(), lt.end()); //调用迭代器区间构造函数this-swap(tmp);}//赋值重载——传统写法/*listT operator(const listT lt) {if (this ! lt) {this-clear();}for (const auto e : lt) {this-push_back(e);}return *this;}*///赋值重载——现代写法listT operator(listT lt) {this-swap(lt);return *this;}//迭代器iterator begin() {return iterator(_head-_next);}iterator end() {return iterator(_head);}//const迭代器const_iterator begin() const {return const_iterator(_head-_next);}const_iterator end() const {return const_iterator(_head);}//尾插void push_back(const T val) {node* newnode new node(T(val));node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}//insertiterator insert(iterator pos, const T val) {node* newnode new node(T(val));node* cur pos._pnode;node* first cur-_prev;first-_next newnode;newnode-_prev first;newnode-_next cur;cur-_prev newnode;_size;//insert后返回新节点的位置那么下一次pos就会指向最近一次创建新节点的位置了return iterator(newnode);}iterator erase(iterator pos) {//pos不能指向哨兵位头节点因为pos一旦指向哨兵位头那么该链表一定为空空链表是不能再删数据的assert(pos ! end());node* first pos._pnode-_prev;node* last pos._pnode-_next;first-_next last;last-_prev first;delete pos._pnode;pos._pnode nullptr;--_size;return iterator(last);}void push_front(const T val) {insert(begin(), val);}void pop_back() {erase(--end());}void pop_front() {erase(begin());}size_t size() const{/*size_t s 0;iterator it this-begin();while (it ! this-end()) {it;s;}return s;*///复用insert和erase//因为在链表中一切的新增和减少都是复用的insert和erase,所以在insert和erase中size,size--即可return _size;}bool empty() const {//return _head-_next _head;//也可以复用size()return _size 0;}private:node* _head; //头节点size_t _size;
};
