【C 面试真题】聊聊 C 的迭代器迭代器是标准库的关节——容器和算法全靠它连接。背得出迭代器用来遍历容器只是及格真考你的是五种迭代器类别各是什么能力、它和指针到底什么关系、那张’各容器失效规则表’、range-for 里增删容器为什么炸。本文把迭代器一次讲透。一、开场迭代器有哪些类别❓ 介绍一下 C 的迭代器✅ 按能力分五级层层递进类别能力典型代表输入单遍读、istream_iterator输出单遍写、ostream_iterator前向多遍读写、forward_list、unordered_*双向再加回退--list、map、set随机访问再加跳转n、[]vector、deque、裸指针[C20]又补上最严格的连续迭代器ContiguousIterator——元素物理连续vector、string、array、裸指针都属于。回答思路从输入/输出 → 前向 → 双向 → 随机访问报能力阶梯每级点一个容器代表再补一句类别决定能用哪些算法——这半句就是你的加分项面试官多半会顺着它往下问。类别决定算法门槛std::sort只吃随机访问迭代器给它 list 直接编译报错——所以 list 自带成员sort()std::advance对随机访问 O(1)、对其余 O(n)。容器提供了哪类迭代器就决定了它能白嫖哪些算法。二、先说结论泛化的指针算法与容器的桥❓ 迭代器到底是什么✅ 一句话迭代器是泛化的指针——用统一接口*、、遍历任意容器让算法不必关心容器底层。inta[]{3,1,4};sort(a,a3);// 裸指针当迭代器vectorintv{3,1,4};sort(v.begin(),v.end());// 同一个 sortlistintl{3,1,4};l.sort();// list 只能用自己的 这是标准库的设计核心算法 容器通过迭代器解耦。九十多个标准算法只认迭代器区间[first, last)不认容器——sort能排数组、能排 vector靠的就是裸指针也满足迭代器要求这一条。三、与指针的关系像、是、超越❓ 迭代器和指针到底什么关系✅ 三层是裸指针满足随机访问迭代器的全部要求指针就是迭代器算法通吃像迭代器支持*、-、、!用法与指针一致超越迭代器是类对象时能干指针干不了的事——调试模式带边界检查、流迭代器把流包装成序列、插入迭代器把赋值变成插入。vectorintv{1,2,3};autoitv.begin();*it10;// 用法和指针一样it;// 走到下一个begin()/end()划出半开区间[begin, end)end()指向最后一格的下一格是个哨兵不可解引用。空容器就是begin() end()表达起来零成本。 全局版本std::begin(v)/std::end(v)连裸数组都能伺候——数组没有成员函数全局函数模板返回首指针和尾后指针让数组和容器在算法面前完全平权。四、各容器失效规则总表❓ 各容器的迭代器什么时候失效✅ 汇总成一张表容器插入删除vector/string扩容→全部失效否则插点及之后删点及之后deque两端插→迭代器失效、引用有效中间插→全失效两端删→仅被删点中间删→全失效list不失效仅被删元素map/set不失效仅被删元素unordered_*rehash→迭代器失效、引用不失效否则不失效仅被删元素⚠️本质迭代器失效就是悬空指针的泛化——它内部记着的内存已被释放或搬走再解引用就是未定义行为。表中引用是否幸存常被追问节点式容器list、map、unordered元素不搬家引用大多活下来连续内存vector 扩容整块搬家全军覆没。五、失效的三大应对❓ 实际编码怎么避开失效坑✅ 三个惯用法① erase 接返回值——它返回被删元素的下一个的有效迭代器for(autoitv.begin();it!v.end();)if(*it%2)itv.erase(it);elseit;② reserve 防扩容——提前开够容量循环里 push_back 不再触发搬家。③ 不缓存 end()——循环条件里现取v.end()别在循环外存下来。[C20]起还有一招更省的std::erase_if一个函数替代整段循环erase_if(v,[](intx){returnx%2;});④ erase-remove 惯用法——C98 时代的经典remove只把要留的元素前移、返回新逻辑终点真正删除交给 erase// 删掉所有 0v.erase(remove(v.begin(),v.end(),0),v.end());// [C20] 直接一行// erase(v, 0); 为什么 remove 不顺手删因为算法手里只有迭代器够不着容器的 size——真正缩短容器只能由容器自己erase完成。这道题单独出现频率极高。六、range-for迭代器的语法糖❓ 范围 for 和迭代器什么关系✅ range-for 就是迭代器循环的糖编译器把它展开成for(autox:v)use(x);// 等价于// for (auto it v.begin();// it ! v.end(); it)// use(*it);⚠️最大坑循环体内增删容器。展开后就是拿着迭代器循环一 push_back 触发扩容、一 erase 就失效直接未定义行为。要边遍历边改退回显式迭代器循环 erase 惯用法。另一个高频坑是auto的三种拷贝语义for(autox:v)x1;// ❌ 改副本for(autox:v)x1;// ✅ 真改元素for(constautox:v)// ✅ 只读免拷贝coutx;七、const_iterator 与 cbegin❓ 只读遍历用什么迭代器✅const_iterator——能读不能写的迭代器指向的元素视为 constconstvectorintcv{1,2};autoitcv.begin();// 推导出 const_iterator// *it 5; // ❌ 编译报错想显式要 const 版本用cbegin()/cend()容器本身是 const 时begin()也自动返回 const_iterator。只读遍历优先 const——把误写挡在编译期。八、面试高频追问❓ Q1为什么 std::sort 排不了 list✅ sort 要求随机访问迭代器分区要 O(1) 跳转list 只有双向迭代器直接编译报错。list 自带成员sort()归并实现O(n log n)。❓ Q2迭代器为什么设计成半开区间✅ 三个好处begin end天然表达空区间循环条件统一用!不依赖前向迭代器也能用判断结束只需一次比较。这个设计叫左闭右开贯穿整个标准库。❓ Q3std::advance 的复杂度✅ 随机访问迭代器 O(1)一次加法其余 O(n)逐步。std::distance同理——所以跨容器通吃的代价藏在迭代器类别里。❓ Q4unordered_map 的迭代器是哪一类✅前向迭代器——能多遍但不能--。所以它不能像 map 那样反向遍历。而 map/set 是双向的。这也是无序族功能换性能的体现之一。❓ Q5插入迭代器是什么✅ 把赋值给迭代器变成插入进容器的适配器back_inserter变 push_back、inserter变 insert。配合 copy 等算法往空容器里边构造边写不用先开好大小。❓ Q6迭代器失效和悬空指针是一回事吗✅ 本质是一回事——都是底层内存没了还去访问。区别只是迭代器把指针包了一层连续容器失效是整块搬家节点容器失效往往只死被删的那个。调试期可开_ITERATOR_DEBUG_LEVEL让越界早炸。九、总结速查表考点一句话结论本质泛化的指针算法与容器的桥五类输入/输出/前向/双向/随机访问空区间begin end右开哨兵vector 失效扩容全失效插删点及之后节点容器插入不失效删除仅被删点unorderedrehash 废迭代器、不废引用erase 惯用法it c.erase(it)range-for迭代器循环的糖体内勿增删只读遍历const_iterator / cbegin一句话回顾迭代器是泛化的指针按能力分五级类别决定容器能吃哪些算法失效规则一张表讲清——节点容器插入不失效、vector 扩容全失效、unordered rehash 只废迭代器不废引用range-for 是糖循环体内别增删容器。如果您觉得本篇内容对你有帮助欢迎点赞 、收藏 ⭐、转发 。下期我们继续标准库篇聊常用算法——sort/find/copy/accumulate 这些天天用的家伙各有什么讲究敬请关注
【C++ 面试真题】19. 聊聊 C++ 的迭代器
【C 面试真题】聊聊 C 的迭代器迭代器是标准库的关节——容器和算法全靠它连接。背得出迭代器用来遍历容器只是及格真考你的是五种迭代器类别各是什么能力、它和指针到底什么关系、那张’各容器失效规则表’、range-for 里增删容器为什么炸。本文把迭代器一次讲透。一、开场迭代器有哪些类别❓ 介绍一下 C 的迭代器✅ 按能力分五级层层递进类别能力典型代表输入单遍读、istream_iterator输出单遍写、ostream_iterator前向多遍读写、forward_list、unordered_*双向再加回退--list、map、set随机访问再加跳转n、[]vector、deque、裸指针[C20]又补上最严格的连续迭代器ContiguousIterator——元素物理连续vector、string、array、裸指针都属于。回答思路从输入/输出 → 前向 → 双向 → 随机访问报能力阶梯每级点一个容器代表再补一句类别决定能用哪些算法——这半句就是你的加分项面试官多半会顺着它往下问。类别决定算法门槛std::sort只吃随机访问迭代器给它 list 直接编译报错——所以 list 自带成员sort()std::advance对随机访问 O(1)、对其余 O(n)。容器提供了哪类迭代器就决定了它能白嫖哪些算法。二、先说结论泛化的指针算法与容器的桥❓ 迭代器到底是什么✅ 一句话迭代器是泛化的指针——用统一接口*、、遍历任意容器让算法不必关心容器底层。inta[]{3,1,4};sort(a,a3);// 裸指针当迭代器vectorintv{3,1,4};sort(v.begin(),v.end());// 同一个 sortlistintl{3,1,4};l.sort();// list 只能用自己的 这是标准库的设计核心算法 容器通过迭代器解耦。九十多个标准算法只认迭代器区间[first, last)不认容器——sort能排数组、能排 vector靠的就是裸指针也满足迭代器要求这一条。三、与指针的关系像、是、超越❓ 迭代器和指针到底什么关系✅ 三层是裸指针满足随机访问迭代器的全部要求指针就是迭代器算法通吃像迭代器支持*、-、、!用法与指针一致超越迭代器是类对象时能干指针干不了的事——调试模式带边界检查、流迭代器把流包装成序列、插入迭代器把赋值变成插入。vectorintv{1,2,3};autoitv.begin();*it10;// 用法和指针一样it;// 走到下一个begin()/end()划出半开区间[begin, end)end()指向最后一格的下一格是个哨兵不可解引用。空容器就是begin() end()表达起来零成本。 全局版本std::begin(v)/std::end(v)连裸数组都能伺候——数组没有成员函数全局函数模板返回首指针和尾后指针让数组和容器在算法面前完全平权。四、各容器失效规则总表❓ 各容器的迭代器什么时候失效✅ 汇总成一张表容器插入删除vector/string扩容→全部失效否则插点及之后删点及之后deque两端插→迭代器失效、引用有效中间插→全失效两端删→仅被删点中间删→全失效list不失效仅被删元素map/set不失效仅被删元素unordered_*rehash→迭代器失效、引用不失效否则不失效仅被删元素⚠️本质迭代器失效就是悬空指针的泛化——它内部记着的内存已被释放或搬走再解引用就是未定义行为。表中引用是否幸存常被追问节点式容器list、map、unordered元素不搬家引用大多活下来连续内存vector 扩容整块搬家全军覆没。五、失效的三大应对❓ 实际编码怎么避开失效坑✅ 三个惯用法① erase 接返回值——它返回被删元素的下一个的有效迭代器for(autoitv.begin();it!v.end();)if(*it%2)itv.erase(it);elseit;② reserve 防扩容——提前开够容量循环里 push_back 不再触发搬家。③ 不缓存 end()——循环条件里现取v.end()别在循环外存下来。[C20]起还有一招更省的std::erase_if一个函数替代整段循环erase_if(v,[](intx){returnx%2;});④ erase-remove 惯用法——C98 时代的经典remove只把要留的元素前移、返回新逻辑终点真正删除交给 erase// 删掉所有 0v.erase(remove(v.begin(),v.end(),0),v.end());// [C20] 直接一行// erase(v, 0); 为什么 remove 不顺手删因为算法手里只有迭代器够不着容器的 size——真正缩短容器只能由容器自己erase完成。这道题单独出现频率极高。六、range-for迭代器的语法糖❓ 范围 for 和迭代器什么关系✅ range-for 就是迭代器循环的糖编译器把它展开成for(autox:v)use(x);// 等价于// for (auto it v.begin();// it ! v.end(); it)// use(*it);⚠️最大坑循环体内增删容器。展开后就是拿着迭代器循环一 push_back 触发扩容、一 erase 就失效直接未定义行为。要边遍历边改退回显式迭代器循环 erase 惯用法。另一个高频坑是auto的三种拷贝语义for(autox:v)x1;// ❌ 改副本for(autox:v)x1;// ✅ 真改元素for(constautox:v)// ✅ 只读免拷贝coutx;七、const_iterator 与 cbegin❓ 只读遍历用什么迭代器✅const_iterator——能读不能写的迭代器指向的元素视为 constconstvectorintcv{1,2};autoitcv.begin();// 推导出 const_iterator// *it 5; // ❌ 编译报错想显式要 const 版本用cbegin()/cend()容器本身是 const 时begin()也自动返回 const_iterator。只读遍历优先 const——把误写挡在编译期。八、面试高频追问❓ Q1为什么 std::sort 排不了 list✅ sort 要求随机访问迭代器分区要 O(1) 跳转list 只有双向迭代器直接编译报错。list 自带成员sort()归并实现O(n log n)。❓ Q2迭代器为什么设计成半开区间✅ 三个好处begin end天然表达空区间循环条件统一用!不依赖前向迭代器也能用判断结束只需一次比较。这个设计叫左闭右开贯穿整个标准库。❓ Q3std::advance 的复杂度✅ 随机访问迭代器 O(1)一次加法其余 O(n)逐步。std::distance同理——所以跨容器通吃的代价藏在迭代器类别里。❓ Q4unordered_map 的迭代器是哪一类✅前向迭代器——能多遍但不能--。所以它不能像 map 那样反向遍历。而 map/set 是双向的。这也是无序族功能换性能的体现之一。❓ Q5插入迭代器是什么✅ 把赋值给迭代器变成插入进容器的适配器back_inserter变 push_back、inserter变 insert。配合 copy 等算法往空容器里边构造边写不用先开好大小。❓ Q6迭代器失效和悬空指针是一回事吗✅ 本质是一回事——都是底层内存没了还去访问。区别只是迭代器把指针包了一层连续容器失效是整块搬家节点容器失效往往只死被删的那个。调试期可开_ITERATOR_DEBUG_LEVEL让越界早炸。九、总结速查表考点一句话结论本质泛化的指针算法与容器的桥五类输入/输出/前向/双向/随机访问空区间begin end右开哨兵vector 失效扩容全失效插删点及之后节点容器插入不失效删除仅被删点unorderedrehash 废迭代器、不废引用erase 惯用法it c.erase(it)range-for迭代器循环的糖体内勿增删只读遍历const_iterator / cbegin一句话回顾迭代器是泛化的指针按能力分五级类别决定容器能吃哪些算法失效规则一张表讲清——节点容器插入不失效、vector 扩容全失效、unordered rehash 只废迭代器不废引用range-for 是糖循环体内别增删容器。如果您觉得本篇内容对你有帮助欢迎点赞 、收藏 ⭐、转发 。下期我们继续标准库篇聊常用算法——sort/find/copy/accumulate 这些天天用的家伙各有什么讲究敬请关注
