牟平建设企业网站,电商网站 开发成本,做网站仓库报表系统,网站开发行业新闻list模拟实现list迭代器失效问题 一#xff0c;list模拟实现1. list的主要框架接口模拟2. list构造拷贝构造析构3. list迭代器3.1 普通迭代器3.2 const迭代器 4. 增删查改 二#xff0c;迭代器失效问题1. list的迭代器失效原因2. 解决办法 一#xff0c;list… list模拟实现list迭代器失效问题 一list模拟实现1. list的主要框架接口模拟2. list构造拷贝构造析构3. list迭代器3.1 普通迭代器3.2 const迭代器 4. 增删查改 二迭代器失效问题1. list的迭代器失效原因2. 解决办法 一list模拟实现
在上节我们熟悉了list的底层结构和各个接口的含义后下面我们来对list的主要接口进行模拟实现
1. list的主要框架接口模拟
list的底层是双向带头循环链表所以我们先写一个节点的类这个节点类也是一个类模板由给定的数据类型生成相应的类
这个节点类可以写成结构体用结构体是为了方便访问数据,不用单独写取数据接口
//list的节点
templateclass T
struct ListNode {ListNode* _prev;ListNode* _next;T _data;ListNode(const T t T()):_prev(nullptr),_next(nullptr),_data(t){}};其次我们写list的基本框架其成员变量我们可以用节点声明一个头结点根据头结点的链接关系我们就可以知道其list存放的内容
templateclass T
class mylist {typedef ListNodeT Node;//方便阅读
public://....
private:Node* _head;
};
2. list构造拷贝构造析构
list的构造有无参的构造用n个值初始化构造迭代器区间构造 我们这里实现无参的构造
void list_init() {_head new Node;_head-_next _head;_head-_prev _head;
}mylist() {list_init();
}初始化时其头指针和外指针指向自己 现在我们来实现拷贝构造
拷贝构造的实现我们和vector一样依次去插入即可。
mylist(mylistT ml) {list_init();for (const auto e : ml) {push_back(e);}
}重载operator这里我们可以转变一下思路当传入一个list对象时发生了拷贝构造用拷贝构造的这个对象和当前要调用operator的对象进行交换再返回交换后的这个对象。
mylist operator(mylist lt)//在类中时可以省略模板参数swap(lt);return *this;
}3. list迭代器
由于list的底层空间的不连续性所以不能像string和vector一样直接用原生指针我们要对其进行封装使其可以像指针那样可以进行或者–那样去使用。
templateclass T
struct List_Iterator {typedef ListNodeT Node;typedef List_IteratorT self;Node* _node;//..
};对于迭代器的构造函数比较简单可写可不写
templateclass T
struct List_Iterator {typedef ListNodeT Node;typedef List_IteratorT self;Node* _node;List_Iterator(Node* n):_node(n){}//..
};3.1 普通迭代器
我们先实现普通迭代器 既然要对这个类进行封装那么就是为了让其可以进行或者–等运算所以我们需要对这些操作进行重载 重载operator有前置和后置
//前置
self operator() {_node _node-_next;return *this;
}//后置
self operator(int) {self tmp(*this);//拷贝构造_node _node-_next;return tmp;
}注拷贝构造我们后面会实现 重载operator--和operator类似我们直接上代码
//前置--
self operator--() {_node _node-_prev;return *this;
}
//后置--
self operator--(int) {self tmp(*this);_node _node-_prev;return tmp;
}重载operator-这是因为当list中存储的是其他结构体时可以通过 it-_data 来直接访问其内容。
T* operator-() {return _node-_data;
}这里来举个具体的场景看下面的代码
struct Exp {int _a1 1;int _a2 2;Exp(int a1 1,int a2 2):_a1(a1),_a2(a2){}
};void test() {mylistExp ex;ex.push_back(Exp(1, 2));mylistExp::iterator it ex.begin();while (it ! ex.end()) {cout (*it)._a1 (*it)._a2 endl;cout it-_a1 it-_a2 endl;it;}
}看到这段代码你可能会一头雾水为啥 it-_a1可以直接访问struct的成员变量it-不是返回的是这个结构体的指针吗 其实这里是省略了一个-我们可以加一句代码来解释
struct Exp {int _a1 1;int _a2 2;Exp(int a1 1,int a2 2):_a1(a1),_a2(a2){}
};void test() {mylistExp ex;ex.push_back(Exp(1, 2));mylistExp::iterator it ex.begin();while (it ! ex.end()) {cout (*it)._a1 (*it)._a2 endl;cout it-_a1 it-_a2 endl;cout it.operator-()-_a1 it.operator-()-_a2 endl;it;}
}it-_a1中it-取到的是结构体对象的地址其后面应该再用一个-访问到其中的变量但是后面的箭头被省略了这里也是C为了方便使用而做的处理。 operator*返回的是T 减少拷贝
T operator* () {return _node-_data;
}3.2 const迭代器
实现了普通迭代器现在我们终于要实现const迭代器了现在思考一下普通迭代器和const迭代器区别在哪其实const迭代器的区别就是operator*和operator-的返回值加上const。
试想一下如果我们像vector一样只在普通迭代器前面直接加一个const。我们直接再将普通迭代器的代码拷贝一份在operator*和operator-返回值前加上const其余代码不变也可以实现const迭代器。但是这样写代码难免有些冗余如果相同的场景下要拷贝的代码有上千万行呢难道也要拷贝吗
所以这里我们只需在模板参数中添加两个参数RefPtr。分别代表 operator和operator-的返回值当传入的是const T或者const T时迭代器类会返回相应的类型。具体在list的类中再对const迭代器进行封装。
templateclass T,class Ref,class Ptr
struct List_Iterator {//typedef ListNodeT Node;typedef List_IteratorT,Ref,Ptr self;Node* _node;List_Iterator(Node* n):_node(n){}//前置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;}Ref operator* () {return _node-_data;}Ptr operator-() {return _node-_data;}bool operator(const self s) {return _node s._node;}bool operator!(const self s) {return _node ! s._node;}};templateclass T
class mylist {typedef ListNodeT Node;//方便阅读public:typedef List_IteratorT,T,T* iterator;//写成公有,类外也可以访问typedef List_IteratorT,const T,const T* const_iterator;//....
}在list类中如何用用到iterator类呢下面我们来实现一下
iterator begin() {return _head-_next;//单参数的构造函数支持隐式类型转换,
}iterator end() {return _head;//迭代器区间是左闭右开,end指向最后一个元素的下一个位置
}4. 增删查改
list的插入删除比较简单因为不用考虑数据挪动的问题只要创建或者删除新的节点改变前后节点的指针即可。 insert
iterator insert(iterator pos,const T t) {Node* newnode new Node(t);Node* cur pos._node;Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return newnode;
}erase可能会造成迭代器失效的问题具体原因和解决办法我们在下面讲解。
iterator erase(iterator pos) {assert(pos ! end());//会发生隐式类型转换,将指针类型转换成iterator类Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;cur nullptr;return next;//迭代器失效,返回删除位置的下一个位置
}push_back()和push_front和pop_back()和pop_front的实现可以直接复用insert在末尾位置插入即可
void push_back(const T t) {insert(end(), t);
}void push_front(const T t) {insert(begin(), t);
}
void pop_back() {erase(--end());
}void pop_front() {erase(begin());
}二迭代器失效问题
1. list的迭代器失效原因
list的插入不会像vector造成迭代器失效因为vector一旦发生扩容其所有位置的迭代器都会失效但是list不用扩容当有元素插入时才创建节点再链接到链表中。 但是list的删除会造成迭代器失效因为删除一个节点后这个节点的迭代器位置实际上已经不存在了再继续使用则会出错除非下次使用时再给其赋值。
2. 解决办法
解决办法就是让删除后返回被删除节点的下一个节点的迭代器下面是正确的使用场景
void Test()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);}
}list的模拟实现部分我们讲解完了希望大家看了后会有所收获期待更多的C相关的知识请大家三连一波哦
