静宁县建设局网站,有哪些建筑设计网站,wordpress插件后端页面,windows wordpress mi迭代器常见问题的汇总vector迭代器和list迭代器的使用vector迭代器list迭代器vector迭代器失效问题list迭代器失效问题vector和list的区别vector迭代器和list迭代器的使用
学习C#xff0c;使用迭代器和了解迭代器失效的原因是每个初学者都需要掌握的#xff0c;接下来我们就…
迭代器常见问题的汇总vector迭代器和list迭代器的使用vector迭代器list迭代器vector迭代器失效问题list迭代器失效问题vector和list的区别vector迭代器和list迭代器的使用
学习C使用迭代器和了解迭代器失效的原因是每个初学者都需要掌握的接下来我们就先从使用迭代器开始帮助大家浅浅的认识一下迭代器究竟是个什么东西
首先有一点我们需要认识到的是vector和list在内存上是有差异的vector是连续的一段内存而list是链表方式建立起来的。
vector迭代器
查询网站–www.cplusplus.com 建议切换到旧版进行查询 因为本篇文章的重点在于了解迭代器的失效问题所以这里我们只介绍一下前四个的使用要想了解的更多还请大家查询相关的文章。
#include iostream
#include vector
#include list
using namespace std;int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//通过迭代器来遍历vector容器auto it v1.begin();while (it ! v1.end()){cout *it ;}cout endl;return 0;
}我们暂时可以将vector的容器理解成指针这能更好的帮助我们理解接下来的东西但是是否真的是指针是跟编译器有关的像VS下vector的迭代器就不是指针而g下就是使用指针来实现的。
上面我们创建了一个int类型的容器使用vector就是说明使用的是一段连续的空间(数组)如下图所示
begin()就是第一个元素的位置end()就是最后一个元素的下一个位置这么看的话我们是否觉得使用迭代器还不如直接使用指针呢但是别忘了vector是被叫作容器的看下面的一段代码
vectorstring s1;s1.push_back(holle);s1.push_back(world);s1.push_back(holle);s1.push_back(iterator);auto lt s1.begin();while (lt ! s1.end()){cout *lt ;}cout endl;这次我们在容器中放入的是字符串类型而不是内置类型这在使用传统的数组是无法办到的这才是vector容器的价值体现所以我们C才需要封装一个叫迭代器的东西以便我们在面对不同的容器的时候都能通过同样的方式去遍历和访问这一点在list中的体现更大。
list迭代器 listint ls;//链表ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);ls.push_back(5);auto LT ls.begin();while (LT ! ls.end()){cout *LT ;}cout endl;在使用上是看不出来vector和list的迭代器的差别的但是我们细想一下的话就能发现其中并不是那么简单的
list是一种带头双向循环的链表那么每个结点就有三个区域 指向下一个结点的next指针 指向前一个结点的prev指针和 数据域data 如图 这时如果我们还将迭代器简单的理解为指针的话那么不妨想一下如果我们使用运算符的话还能找到下一个结点的位置吗答案是不能的因为list不像vector一样是一段连续的内存空间我们如果还以为迭代器是指针的话那么的位置只能是结点的下一个位置但这个位置极大的概率不是下一个结点的位置。 为什么说极大的概率呢虽然list构建链表的时候使用的是空间碎片构建的但是不排除正好是使用的连续的两块地址空间构造的。
那又为什么我们却能像vector一样的去使用list的迭代器呢 而且*就是访问的数据和- -就能找到结点的后一个结点和前一个结点。
这都归功于类的封装在对迭代器封装的时候重新的定义了这些符号的意义(, - - , *) 也就是符号的重载。这才使得我们能就像使用指针一样去使用迭代器但实际上它们的底层早已千差万别。
迭代器的封装具体是怎做到可以看一下这里的代码list的模拟实现这里就模拟了一份迭代器的封装重要的不是看懂这些代码而是认识到迭代器并不是简单的指针 代码
//结点templateclass Tstruct list_node{list_node* next;list_node* prev;T _data;list_node(const T x T())//所以要实现默认构造函数:next(nullptr), prev(nullptr), _data(x){}};// 1、迭代器要么就是原生指针// 2、迭代器要么就是自定义类型对原生指针的封装模拟指针的行为//这里如果单纯的使用结点的指针作为迭代器的话是没法用等操作符操作的所以我们对结点的迭代器进行了//封装templateclass T, class Ref, class Ptr//模板参数一个一个的去理解 1.先不考虑const对象的情况struct _list_iterator{//迭代器内部并不需要进行析构因为这个类对结点的指针进行了封装以便我们能够更好的访问链表typedef list_nodeT node;node* _node;typedef _list_iteratorT, Ref, Ptr self;//构造出一个结点的指针初始化这个指针的指向为我们想要的结点的位置_list_iterator(node* n):_node(n){}//const T* operator-()Ptr operator-() //优雅{return _node-_data;//取地址}Ref operator*() //Ref--const T / Ref--T 优雅{return _node-_data;}self operator() //前置{_node _node-next;return *this;}self operator(int) //后置{self temp(*this);_node _node-next;return temp;//返回的是之前的位置也就是原来的位置但是迭代器已经向后移动了}self operator--(){_node _node-prev;return *this;}self operator--(int){self temp(*this);_node _node-prev;return temp;}//bool operator!(self n)//权限的放大和缩小只针对引用和指针类型bool operator!(const self n){return _node ! n._node;}bool operator(const self n){return _node n._node;}};templateclass Tclass list{typedef list_nodeT node;public://第三个模板参数是类型指针为了重载-时使用typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, T* const_iterator;void empty_init(){_head new node;_head-next _head;_head-prev _head;}//构造函数--创建头结点list(){empty_init();}templateclass iteratorlist(iterator first, iterator second){empty_init();while (first ! second){push_back(*first);first;}}void swap(listT temp){std::swap(_head, temp._head);}list(const listT lt){empty_init();listT temp(lt.begin(), lt.end());swap(temp);}/*list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}*/listT operator(listT lt)//这里不能使用引用会改变原来list的数据{swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){//it erase(it);erase(it);//后置}}iterator begin(){return iterator(_head-next);//头结点的下一个就是第一个结点的位置}iterator end(){return iterator(_head);//头结点就是end结点的位置}const_iterator begin() const{return const_iterator(_head-next);}const_iterator end() const{return const_iterator(_head);}void insert(iterator pos, const T val){node* cur pos._node;//当前位置node* pre cur-prev;//pos的前一个位置node* new_node new node(val);//开始插入pre-next new_node;new_node-prev pre;new_node-next cur;cur-prev new_node;}iterator erase(iterator pos){assert(pos ! _head);node* pre pos._node-prev;//pos位置的前一个node* next pos._node-next;//pos位置的后一个pre-next next;next-prev pre;delete pos._node;return iterator(next);//返回的是删除位置的下一个位置}void push_back(const T val){创建结点//node* new_node new node(val);//node* tail _head-prev;//链表的最后一个结点的位置尾插过程//tail-next new_node;//new_node-prev tail;//new_node-next _head;//_head-prev new_node;insert(end(), val);//复用}void pop_back(){//erase(_head-prev);erase(--end());}void push_front(const T val){//insert(_head-next);insert(begin(), val);}void pop_front(){//erase(_head-next);erase(begin());}private:node* _head;//头结点指针};这份代码也是模拟实现list的完整代码。
vector迭代器失效问题
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//通过迭代器来遍历vector容器auto it find(v1.begin(), v1.end(), 3);//在begin()--end()的区间内查找1v1.erase(it);v1.insert(it, 0);for (auto e : v1){cout e ;}cout endl;
}上面代码的意思就是找到3的并删除掉他然后再在该位置插入0。 按照理解这段代码应该是没有问题的就是很简单的一段删除和插入嘛。
结果 代码崩了
这里就是很典型的迭代器失效问题迭代器it原本指向的是3的位置之后我们将他删除后it指向的数据是4不再是原数据了这就是迭代器的失效。对于迭代器失效VS是assert断言处理的所以我们才看到上面的信息。 同样- -也会导致一样的问题。 解决办法就是it接收一下erase的返回值erase的返回值是该位置的下一个位置的迭代器。这样就能有效的避免上面的问题。
还有一种迭代器失效是在insert时导致的。
假如我们一开始的容器大小是5个且这个容器已经满了此时我再进行insert的时候就会发生扩容。 而C的扩容是异地扩容的并没有像C语言的realloc函数一样的接口。
异地扩容就必定会导致一个问题我们原来it指向的地址发生了改变此时如果不做处理的话it指向的就是一块未知的空间it就变成了一个野指针这也是一种迭代器的失效。
这个问题在大家模拟实现vector的时候是特别需要注意的一点。
list迭代器失效问题
list的迭代器在删除时也会导致和上面相同的问题解决办法也是接受一下erase的返回值同样list的erase的返回值也是该位置的下一个结点位置(next)。
但是list在插入的时候并不会导致迭代器失效因为list不存在扩容的概念。 list就不存在扩容的问题了。
vector和list的区别 vector可以随机访问通过[ ]而list不支持随机访问。vector访问某个元素的效率为O(1) list访问某个元素的效率为O(n)。 vector中插入和删除都可能导致迭代器失效而list中插入元素不会导致迭代器失效删除元素会导致迭代器失效 vector中插入元素有可能需要增容迭代器指向的之前的空间会被释放之前的迭代器会失效删除元素也会导致迭代器失效 list中插入元素只是添加了一个新的节点不会导致之前存在的迭代器失效而删除元素只会导致当前迭代器失效其他迭代器不会受到影响。 vector中的迭代器是原生态指针也就是元素类型的指针(vs下不是g是) list中的迭代器是对原生态指针(节点指针)的封装
