轮胎 东莞网站建设,婚纱摄影网站图片,在线下单网站怎么做,国内个人网站欣赏前言
数据结构中#xff0c;我们了解到了链表#xff0c;但是我们使用时需要自己去实现链表才能用#xff0c;但是C出现了list将这一切皆变为现。list可以看作是一个带头双向循环的链表结构#xff0c;并且可以在任意的正确范围内进行增删查改数据的容器。list容器一样也是…前言
数据结构中我们了解到了链表但是我们使用时需要自己去实现链表才能用但是C出现了list将这一切皆变为现。list可以看作是一个带头双向循环的链表结构并且可以在任意的正确范围内进行增删查改数据的容器。list容器一样也是不支持下标访问的主要也是物理空间并不连续。 list的部分重要接口实现
一样的在实现之前我们要对list的结构有一个大概的框架 在此基础就很容易理解list的内部是一个个节点该节点的类型也都是自定义类型而模版参数是节点中val的类型。代码框架如下
namespace cr
{templateclass Tstruct ListNode{ListNode(const T x T())//T()匿名对象:val(x),pre(nullptr),next(nullptr){}T val;struct ListNodeT* pre;struct ListNodeT* next;};templateclass Tclass list{typedef ListNodeT Node;//对类进行重命名public:private:Node* _head;//自定义类型成员的指针};}1.迭代器实现 cr::listint::iterator it lt.begin();
while (it ! lt.end())//lt.end()临时对象
{cout *it endl;it;
} 先看这段代码该代码也就是我们想要最终实现的结果所以我们想知道对迭代器进行哪些操作可以先从需要实现的功能进行分析。可以初步知道迭代器“八成”是节点的指针节点是自定义类型所以*it和it这两个操作铁定是需要进行运算符重载的*it实际就是得到节点类的成员变量val的值而it就是通过指针的偏移指向下一个节点。而最重要的是应该知道*it和it操作对象是迭代器而不是list实例化出来的对象lt像begin和end函数面向的就是list实例化的对象所以可以直接在list类中实现。如果*it和it也在在list类中实现的话默认传参传的就是list实例化对象的地址最后默认由this指针接受。而我们需要的是对迭代器进行操作固然需要this指向迭代器的指针。所以应该将迭代器封装起来到一个类里里更理想的状态。 所以迭代器封装成类的话那么肯定需要的成员对象就是节点指针而成员函数就一定有operator*和operator。其实operator是最容易忽略的仔细想想迭代器类也是一个自定义类型这么可以直接去判断呢所以operator也是要实现的所以下边整理了需要实现的运算符重载函数以及其他的一些。 代码如下 templateclass T
struct _List_iterator
{typedef ListNodeT Node;_List_iterator(Node* node):_pnode(node){}T operator*(){return _pnode-val;}_List_iteratorT operator()//前置{_pnode _pnode-next;return *this;}_List_iteratorT operator(int)//后置{_List_iterator tmp *this;_pnode _pnode-next;return tmp;}_List_iteratorT operator--(){_pnode _pnode-pre;return *this;}_List_iteratorT operator--(int){_List_iterator tmp *this;_pnode _pnode-pre;return tmp;}bool operator!(const _List_iteratorT cmpnode)const {return _pnode ! cmpnode._pnode;}T* operator-(){return _pnode-val;//一般用于存自定义类型对象时会隐藏一个箭头}Node* _pnode;
}; 这里operator-的实现你可能会有疑问举例下列代码 class A
{
public:A(int a0,int b0):_a(a),_b(b){}int _a;int _b;
};
int main()
{cr::listA a;a.push_back(A(1, 1));//创建匿名对象初始化a.push_back(A(2, 2));a.push_back(A(3, 3));return 0;
} 面对这种情况list实例化的是一个类的对象的话而且想要打印出该类中成员变量的话就是下面的方法 cr::listA::iterator it a.begin();
while (it ! a.end())
{cout (*it)._a (*it)._b endl;it;
} 这里的*it就是list中的pnode-val也就是这个A类但是并没有重载流运算符所以就只能去访问里面的数据公有所以就是通过.运算符既然可以用.那么肯定也可以用-所以就重载了-运算符而-有点不一样 T* operator-()
{return _pnode-val;
}返回值的类型的是A*一个类型也就是返回一个指针所以在调用-运算赋不得加上两个-了吗一个是调用运算符重载函数返回A*另一个是指针访问符所以为了增强可读性就省略一个- cr::listA::iterator it a.begin();
while (it ! a.end())
{cout it-_a it-_b endl;it;
} 以上两种写法实现结果都是一样的 而对于begin和end函数面向的就是list实例化的对象那么说就是在list类中实现就行 iterator begin()
{ //return iterator(_head-next);//匿名对象return _head-next;
}
iterator end()
{//return iterator(_head);//匿名对象return _head;
} 因为迭代器封装的类是单参数所以可以直接返回节点的指针会自动调用迭代器的构造函数 2.const迭代的实现
首先我们要了解list中const迭代器与非const迭代器的区别const迭代器中的成员变量指向的数据是一个节点的指针并不是说const修饰了以后这个节点不能改变实际上是节点中的val成员变量不能改变。假如说是节点不能改变的话那么就连pre和next这两个成员变量也不可以改变如果连这两个都不能改变的话那么还怎么实现operator还怎么遍历链表中的数据呢。
所以凭这一点const迭代器就不可能是直接在iterator前面加上const限定符修饰那么容易。
而想要val的值不能改变的话实际上就是operator*和operator-这两个函数的返回值要加const引用来修饰 方法一再写一个_List_const_iterator的类
对于_List_terator类而言_List_const_iterator这个类只需要改一下类型而已像operator*和operator-的返回值加上const修饰而其他需要返回迭代器的地方改成_List_const_iteratorT就行最后在list类中typedef _List_const_iteratorT const_iterator就完成了 方法二通过模版实现
方法一是需要再实现一个_List_const_iterator的类但是本质上其实这个类相较于_List_iterator没什么区别也就是返回值的类型有区别而已所以此时对迭代器模版的引入就在合适不过了。而此时的模版参数肯定不能只有一个参数而应该有三个参数
templateclass T,class ref,class ptr
模版中第二个参数的实参其实就是const T用于operator*运算符函数的返回值而第三个参数的实参其实就是const T* 用于operator-函数的返回值。此时你可能会问为什么是需要这两个参数呢其实判断方法很简单就是通过实质上的比较const迭代器和非const迭代器实现时各函数返回值有哪些发生了改变。表面上你是只写了一个迭代器的类加一个模版就实现了两个迭代器干的活实际上在编译的时候编译器通过模版参数自动生成了两个类在使用时会优先找最匹配的调用。
所以这里提一点模版中类名相同模版参数不同并不代表是同一个类型类型类名模版参数
迭代器实现代码
templateclass T,class ref,class ptrstruct _List_iterator{typedef ListNodeT Node;_List_iterator(Node* node):_pnode(node){}ref operator*(){return _pnode-val;}ptr operator-(){return _pnode-val;}_List_iteratorT,ref,ptr operator(){_pnode _pnode-next;return *this;}_List_iteratorT,ref,ptr operator(int){_List_iterator tmp *this;_pnode _pnode-next;return tmp;}_List_iteratorT,ref,ptr operator--(){_pnode _pnode-pre;return *this;}_List_iteratorT,ref,ptr operator--(int){_List_iterator tmp *this;_pnode _pnode-pre;return tmp;}bool operator!(const _List_iteratorT,ref,ptr cmpnode)const{return _pnode ! cmpnode._pnode;}Node* _pnode;};
其实上面的代码本质上就是将operator*和operator-的返回值虚拟化然后在调用迭代器时才进行实例化的。 templateclass Tclass list{typedef ListNodeT Node;//对类进行重命名public:typedef _List_iteratorT,T,T* iterator;//实例化typedef _List_iteratorT, const T, const T* const_iterator;const_iterator begin()const{ //return iterator(_head-next);//匿名对象return _head-next;}const_iterator end()const{//return iterator(_head);//匿名对象return _head;}......}
在list类中分别将两种类型迭代器重命名所以在外面调用哪种迭代器时就会在内部模版实例化成具体的迭代器 3.list的插入与删除 iterator insert(iterator pos,const T x){Node* l1 pos._pnode-pre;Node* l2 pos._pnode;Node* tmp new Node(x);l1-next tmp;tmp-pre l1;tmp-next l2;l2-pre tmp;return tmp;}iterator erase(iterator pos)//调用之后pos节点失效{Node* l1 pos._pnode-pre;Node* l2 pos._pnode-next;l1-next l2;l2-pre l1;delete pos._pnode;return l2;}void push_back(const T x){insert(this-end(), x);//Node* tmp new Node(x);//Node* tail _head-pre;//找尾//tail-next tmp;//tmp-pre tail;//tmp-next _head;//_head-pre tmp;}
这里的插入删除同链表一样没什么好说的唯一要注意的就是迭代器失效的问题list的insert不存在扩容换址所以不会造成迭代器失效但是list的erase就不同了earase会释放当前的节点所以调用之后就会失效。所以给erase一个返回值返回需要删除的节点的下一个节点。 4.list的构造加赋值 list():_head(nullptr){_head new Node;//该节点也是一个类创建时调用构造函数_head-next _head;_head-pre _head;}list(const listT copy):_head(nullptr){_head new Node;//该节点也是一个类创建时调用构造函数_head-next _head;_head-pre _head;for (auto it : copy)//内部实际是用迭代器{push_back(it);}}listT operator(listT copy)//调用拷贝构造{std::swap(_head, copy._head);return *this;}
因为list容器类似带头双向循环链表所以构造时要new一个带头节点其次要注意的是new的这个节点的类型是我们自定义的类型所以在new时就会自动调用该节点的构造函数将其空间内容初始化。赋值函数就实现的比较巧妙通过传参调用拷贝构造函数的深拷贝然后再换值就行。 5.空间释放析构函数 void clear(){list::iterator del this-begin();while (del ! this-end()){del erase(del);}_size 0;}~list(){clear();delete _head;_head nullptr;} 若有不恰当的描述欢迎留言指正
