C STL 迭代器一、什么是迭代器核心概念1. 通俗理解迭代器 STL 容器的通用智能指针指针用来访问数组迭代器用来访问所有 STL 容器vector、list、map、set……。2. 官方定义迭代器是一个重载了\*、-、、--、!等运算符的类模板作用统一所有容器的遍历方式屏蔽底层内存差异。3. 为什么要有迭代器容器底层不一样vector 是连续数组list 是链表map/set 是红黑树如果没有迭代器每种容器都要写一套遍历方式有了迭代器一套遍历写法通吃所有容器。二、迭代器基础语法固定格式1. 定义格式容器类型::iterator 迭代器变量名;示例vectorint::iterator it; listint::iterator it2; mapint,string::iterator it3;2. 两个核心接口所有容器都有begin()返回指向第一个元素的迭代器end()返回指向最后一个元素下一个位置的迭代器区间规则左闭右开 [begin, end)end 不指向有效元素只做结束标记。3. 迭代器基本操作*it // 取迭代器指向的元素值 it- // 访问成员容器存对象时用 it // 往后移动一个元素 --it // 往前移动一个元素 it ! end// 判断是否遍历结束4. 经典遍历模板必背vectorint v {1,2,3,4}; // 标准迭代器遍历 for(vectorint::iterator it v.begin(); it ! v.end(); it) { cout *it ; }C11 auto 简化for(auto it v.begin(); it ! v.end(); it) { cout *it ; }范围 for 本质底层还是迭代器。三、迭代器五大类型重点必考按访问能力强弱从低到高划分1. 输入迭代器只能只读、单向往后走特点只能 不能 --、不能随机跳转代表istream_iterator、map/set 迭代器基础2. 输出迭代器只能只写、单向往后走代表ostream_iterator、back_inserter3. 前向迭代器可读可写、只能单向 不能 --4. 双向迭代器可读可写、支持 和 --可以前后走代表list、map、set、multiset、multimap5. 随机访问迭代器最强迭代器具备指针所有能力支持 --、it n、it - n、[]、大小比较 代表vector、deque、string关键考点sort算法只支持随机访问迭代器list 不是随机迭代器不能用全局 sort只能用自己的成员 sort四、迭代器种类细分常用 4 种1. 普通正向迭代器vectorint::iterator it;可读可写正向遍历。2. 常量迭代器 const_iterator只能读、不能修改元素vectorint::const_iterator it;适合不修改容器只遍历的场景。3. 反向迭代器 reverse_iterator从末尾往前遍历vectorint::reverse_iterator it; for(it v.rbegin(); it ! v.rend(); it) { cout *it; }rbegin()最后一个元素rend()第一个元素前一个位置4. 只读反向常量迭代器const_reverse_iterator了解即可。五、迭代器底层原理通俗讲迭代器本质是类模板内部封装了容器底层指针 / 节点地址重载了vector 迭代器 → 地址 1list 迭代器 → 跳转到下一个链表节点对使用者完全屏蔽底层差异写法统一。一句话迭代器把不同容器的寻址方式包装成同一套用法。六、重点难点迭代器失效1. 什么是迭代器失效迭代器本质保存的是内存地址当容器增删元素、重新扩容后原来的地址失效变成野指针再使用程序崩溃。2. vector 迭代器失效场景尾部插入导致扩容重新分配内存所有旧迭代器全部失效中间 / 头部插入、删除后面元素全部后移当前及后面迭代器全部失效。解决办法操作后重新获取 begin ()、end () 迭代器。3. list 迭代器失效list 是链表删除当前节点仅当前迭代器失效其他迭代器不受影响几乎不会大范围失效。4. map/set 迭代器失效红黑树结构插入元素迭代器不失效删除元素仅被删元素的迭代器失效其他不变5. 通用避坑原则遍历过程中不要随意增删元素如果必须增删更新迭代器不要用旧的。七、迭代器辅助工具1. back_inserter 尾部插入迭代器不用关心容器大小直接尾部插入vectorint res; set_intersection(v1.begin(),v1.end(), v2.begin(),v2.end(), back_inserter(res));2. front_inserter 头部插入3. inserter 指定位置插入八、必考总结直接背迭代器是容器通用智能指针统一遍历所有容器核心接口begin()起始、end()末尾下一位区间左闭右开五大迭代器输入→输出→前向→双向→随机访问vector/string/deque 是随机迭代器支持加减、下标list/map/set 是双向迭代器不支持随机跳转不能用全局 sort四种常用迭代器普通、const、反向、常量反向迭代器失效vector 最容易失效list/map 相对稳定所有 STL 算法都依赖迭代器不依赖具体容器。
C++ 知识点26 STL 迭代器
C STL 迭代器一、什么是迭代器核心概念1. 通俗理解迭代器 STL 容器的通用智能指针指针用来访问数组迭代器用来访问所有 STL 容器vector、list、map、set……。2. 官方定义迭代器是一个重载了\*、-、、--、!等运算符的类模板作用统一所有容器的遍历方式屏蔽底层内存差异。3. 为什么要有迭代器容器底层不一样vector 是连续数组list 是链表map/set 是红黑树如果没有迭代器每种容器都要写一套遍历方式有了迭代器一套遍历写法通吃所有容器。二、迭代器基础语法固定格式1. 定义格式容器类型::iterator 迭代器变量名;示例vectorint::iterator it; listint::iterator it2; mapint,string::iterator it3;2. 两个核心接口所有容器都有begin()返回指向第一个元素的迭代器end()返回指向最后一个元素下一个位置的迭代器区间规则左闭右开 [begin, end)end 不指向有效元素只做结束标记。3. 迭代器基本操作*it // 取迭代器指向的元素值 it- // 访问成员容器存对象时用 it // 往后移动一个元素 --it // 往前移动一个元素 it ! end// 判断是否遍历结束4. 经典遍历模板必背vectorint v {1,2,3,4}; // 标准迭代器遍历 for(vectorint::iterator it v.begin(); it ! v.end(); it) { cout *it ; }C11 auto 简化for(auto it v.begin(); it ! v.end(); it) { cout *it ; }范围 for 本质底层还是迭代器。三、迭代器五大类型重点必考按访问能力强弱从低到高划分1. 输入迭代器只能只读、单向往后走特点只能 不能 --、不能随机跳转代表istream_iterator、map/set 迭代器基础2. 输出迭代器只能只写、单向往后走代表ostream_iterator、back_inserter3. 前向迭代器可读可写、只能单向 不能 --4. 双向迭代器可读可写、支持 和 --可以前后走代表list、map、set、multiset、multimap5. 随机访问迭代器最强迭代器具备指针所有能力支持 --、it n、it - n、[]、大小比较 代表vector、deque、string关键考点sort算法只支持随机访问迭代器list 不是随机迭代器不能用全局 sort只能用自己的成员 sort四、迭代器种类细分常用 4 种1. 普通正向迭代器vectorint::iterator it;可读可写正向遍历。2. 常量迭代器 const_iterator只能读、不能修改元素vectorint::const_iterator it;适合不修改容器只遍历的场景。3. 反向迭代器 reverse_iterator从末尾往前遍历vectorint::reverse_iterator it; for(it v.rbegin(); it ! v.rend(); it) { cout *it; }rbegin()最后一个元素rend()第一个元素前一个位置4. 只读反向常量迭代器const_reverse_iterator了解即可。五、迭代器底层原理通俗讲迭代器本质是类模板内部封装了容器底层指针 / 节点地址重载了vector 迭代器 → 地址 1list 迭代器 → 跳转到下一个链表节点对使用者完全屏蔽底层差异写法统一。一句话迭代器把不同容器的寻址方式包装成同一套用法。六、重点难点迭代器失效1. 什么是迭代器失效迭代器本质保存的是内存地址当容器增删元素、重新扩容后原来的地址失效变成野指针再使用程序崩溃。2. vector 迭代器失效场景尾部插入导致扩容重新分配内存所有旧迭代器全部失效中间 / 头部插入、删除后面元素全部后移当前及后面迭代器全部失效。解决办法操作后重新获取 begin ()、end () 迭代器。3. list 迭代器失效list 是链表删除当前节点仅当前迭代器失效其他迭代器不受影响几乎不会大范围失效。4. map/set 迭代器失效红黑树结构插入元素迭代器不失效删除元素仅被删元素的迭代器失效其他不变5. 通用避坑原则遍历过程中不要随意增删元素如果必须增删更新迭代器不要用旧的。七、迭代器辅助工具1. back_inserter 尾部插入迭代器不用关心容器大小直接尾部插入vectorint res; set_intersection(v1.begin(),v1.end(), v2.begin(),v2.end(), back_inserter(res));2. front_inserter 头部插入3. inserter 指定位置插入八、必考总结直接背迭代器是容器通用智能指针统一遍历所有容器核心接口begin()起始、end()末尾下一位区间左闭右开五大迭代器输入→输出→前向→双向→随机访问vector/string/deque 是随机迭代器支持加减、下标list/map/set 是双向迭代器不支持随机跳转不能用全局 sort四种常用迭代器普通、const、反向、常量反向迭代器失效vector 最容易失效list/map 相对稳定所有 STL 算法都依赖迭代器不依赖具体容器。
