1. 什么是迭代器在C STLStandard Template Library标准模板库中迭代器iterator是连接容器和算法的桥梁。简单来说迭代器是一种类似指针的对象它可以访问容器中的元素并且能够遍历容器。例如vectorint v {1,2,3,4,5}; for(auto e : v) { cout e ; }这是C11提供的范围for本质上编译器帮我们使用了迭代器。实际上for(auto e : v)大致等价于auto begin v.begin(); auto end v.end(); while(begin ! end) { cout *begin ; begin; }这里begin()返回第一个元素的位置end()返回最后一个元素的下一个位置*begin获取元素begin移动到下一个元素2. 为什么需要迭代器2.1 不同容器底层结构不同STL中有很多容器容器底层结构vector动态数组list双向链表deque双端队列map红黑树unordered_map哈希表访问方式完全不同。例如vector内存连续------------ |10 |20 |30 |40 | ------------ 地址: 100 104 108 112可以通过指针移动ptr;list链表10 | v 20 | v 30 | v 40节点地址可能完全不连续1000 - 5000 - 2000无法ptr;因为下一个节点不一定在下一个地址。2.2 迭代器统一访问方式有了迭代器vectorvectorint::iterator it;listlistint::iterator it;mapmapint,int::iterator it;虽然底层完全不同但是遍历方式一样for(auto itcontainer.begin(); it!container.end(); it) { cout*it; }这就是STL设计思想不关心容器底层只通过迭代器访问元素。3. 迭代器的本质迭代器本质是一种类对象。例如vectorint::iterator it;实际上iterator是vector内部定义的一个类型。简单模拟templateclass T class VectorIterator { public: T* ptr; T operator*() { return *ptr; } VectorIterator operator() { ptr; return *this; } };这个类实现*!于是它就像指针一样使用。4. 迭代器的基本使用4.1 begin()返回第一个元素的位置vectorint v{1,2,3}; auto itv.begin(); cout*it;输出1结构begin() | v --------- | 1 | 2 | 3 | --------- ^ it4.2 end()返回最后一个元素后面的位置auto itv.end();注意end不是最后一个元素。而是------------- | 1 | 2 | 3 | | ------------- ^ end所以错误cout*v.end();这是非法访问。5. 使用迭代器遍历容器vector遍历#includeiostream #includevector using namespace std; int main() { vectorint v{1,2,3,4}; vectorint::iterator itv.begin(); while(it!v.end()) { cout*it ; it; } return 0; }输出1 2 3 46. auto简化迭代器以前vectorint::iterator it;非常长。C11auto itv.begin();编译器自动推导类型。推荐for(auto itv.begin(); it!v.end(); it) { cout*it; }7. const_iterator普通迭代器iterator可以修改元素。例如vectorint v{1,2,3}; auto itv.begin(); *it100;结果100 2 3但是如果只想读取使用const_iterator例如vectorint::const_iterator it; itv.begin();此时*it100;错误。原因不能通过const迭代器修改数据。8. reverse_iterator反向迭代器普通迭代器方向begin() | v 1 2 3 4反向迭代器rbegin() 4 3 2 1使用vectorint v{1,2,3,4}; auto itv.rbegin(); while(it!v.rend()) { cout*it ; it; }输出4 3 2 19. 五种迭代器类型STL根据功能不同把迭代器分为五类。9.1 输入迭代器Input Iterator特点只能读取。支持* !例如读取文件istream_iterator9.2 输出迭代器Output Iterator只能写。例如ostream_iterator用于输出copy(v.begin(), v.end(), ostream_iteratorint(cout, ));9.3 前向迭代器Forward Iterator支持读取写入移动例如forward_list9.4 双向迭代器Bidirectional Iterator支持向前向后--例如list map set9.5 随机访问迭代器Random Access Iterator功能最强。支持 - [] 例如vectorit5dequeit-2迭代器能力关系Random Access | Bidirectional | Forward Iterator | Input Iterator能力越往上越强。10. 不同容器迭代器类型容器迭代器类型vector随机访问deque随机访问array随机访问list双向map双向set双向forward_list前向unordered_map前向11. 迭代器失效问题重点这是面试高频问题。所谓迭代器失效迭代器仍然保存地址但是这个地址已经不是有效元素。11.1 vector插入导致失效例如vectorint v{1,2,3}; auto itv.begin(); v.push_back(4); cout*it;可能错误。原因vector扩容原空间1000: 1 2 3扩容5000: 1 2 3 4旧地址释放。it仍指向1000。失效。11.2 vector删除导致失效vectorint v{1,2,3}; auto itv.begin(); v.erase(it);删除后2 3原来的it失效。11.3 list迭代器失效listnode1 - node2 - node3删除node2node1 - node3只有删除节点的迭代器失效。其他迭代器仍有效。12. erase正确使用方式错误for(auto itv.begin(); it!v.end(); it) { if(*it3) v.erase(it); }原因erase后it失效。正确for(auto itv.begin(); it!v.end();) { if(*it3) { itv.erase(it); } else { it; } }因为vector/list的erase会返回删除位置后的迭代器。13. 迭代器和指针区别很多人认为迭代器就是指针。不完全正确。指针直接操作地址int* p;只能访问内存。迭代器是一种抽象。可能是指针是类对象例如vectoriterator ≈ T*listiterator: { Node* node; }14. 迭代器和算法STL算法sort find copy reverse都使用迭代器。例如排序vectorint v{3,1,2}; sort(v.begin(), v.end());sort不知道vector是什么数据在哪里它只认识begin() end() *15. 迭代器底层思想STL采用泛型编程算法templateclass Iterator void sort(Iterator first, Iterator last)不关心类型。只要求这个Iterator满足随机访问能力。这就是面向接口编程。16. 常用迭代器接口总结函数作用begin()返回头迭代器end()返回尾后迭代器rbegin()返回反向头rend()返回反向尾cbegin()const开始cend()const结束17. 迭代器总结什么是迭代器迭代器是STL中用于访问容器元素的一种对象本质是对指针的封装。为什么需要迭代器因为不同容器底层不同统一算法访问方式核心使用auto itcontainer.begin(); while(it!container.end()) { cout*it; it; }必须掌握begin/enditeratorconst_iteratorreverse_iterator五种迭代器分类迭代器失效STL算法与迭代器关系
1. 什么是迭代器在C STLStandard Template Library标准模板库中迭代器iterator是连接容器和算法的桥梁。简单来说迭代器是一种类似指针的对象它可以访问容器中的元素并且能够遍历容器。例如vectorint v {1,2,3,4,5}; for(auto e : v) { cout e ; }这是C11提供的范围for本质上编译器帮我们使用了迭代器。实际上for(auto e : v)大致等价于auto begin v.begin(); auto end v.end(); while(begin ! end) { cout *begin ; begin; }这里begin()返回第一个元素的位置end()返回最后一个元素的下一个位置*begin获取元素begin移动到下一个元素2. 为什么需要迭代器2.1 不同容器底层结构不同STL中有很多容器容器底层结构vector动态数组list双向链表deque双端队列map红黑树unordered_map哈希表访问方式完全不同。例如vector内存连续------------ |10 |20 |30 |40 | ------------ 地址: 100 104 108 112可以通过指针移动ptr;list链表10 | v 20 | v 30 | v 40节点地址可能完全不连续1000 - 5000 - 2000无法ptr;因为下一个节点不一定在下一个地址。2.2 迭代器统一访问方式有了迭代器vectorvectorint::iterator it;listlistint::iterator it;mapmapint,int::iterator it;虽然底层完全不同但是遍历方式一样for(auto itcontainer.begin(); it!container.end(); it) { cout*it; }这就是STL设计思想不关心容器底层只通过迭代器访问元素。3. 迭代器的本质迭代器本质是一种类对象。例如vectorint::iterator it;实际上iterator是vector内部定义的一个类型。简单模拟templateclass T class VectorIterator { public: T* ptr; T operator*() { return *ptr; } VectorIterator operator() { ptr; return *this; } };这个类实现*!于是它就像指针一样使用。4. 迭代器的基本使用4.1 begin()返回第一个元素的位置vectorint v{1,2,3}; auto itv.begin(); cout*it;输出1结构begin() | v --------- | 1 | 2 | 3 | --------- ^ it4.2 end()返回最后一个元素后面的位置auto itv.end();注意end不是最后一个元素。而是------------- | 1 | 2 | 3 | | ------------- ^ end所以错误cout*v.end();这是非法访问。5. 使用迭代器遍历容器vector遍历#includeiostream #includevector using namespace std; int main() { vectorint v{1,2,3,4}; vectorint::iterator itv.begin(); while(it!v.end()) { cout*it ; it; } return 0; }输出1 2 3 46. auto简化迭代器以前vectorint::iterator it;非常长。C11auto itv.begin();编译器自动推导类型。推荐for(auto itv.begin(); it!v.end(); it) { cout*it; }7. const_iterator普通迭代器iterator可以修改元素。例如vectorint v{1,2,3}; auto itv.begin(); *it100;结果100 2 3但是如果只想读取使用const_iterator例如vectorint::const_iterator it; itv.begin();此时*it100;错误。原因不能通过const迭代器修改数据。8. reverse_iterator反向迭代器普通迭代器方向begin() | v 1 2 3 4反向迭代器rbegin() 4 3 2 1使用vectorint v{1,2,3,4}; auto itv.rbegin(); while(it!v.rend()) { cout*it ; it; }输出4 3 2 19. 五种迭代器类型STL根据功能不同把迭代器分为五类。9.1 输入迭代器Input Iterator特点只能读取。支持* !例如读取文件istream_iterator9.2 输出迭代器Output Iterator只能写。例如ostream_iterator用于输出copy(v.begin(), v.end(), ostream_iteratorint(cout, ));9.3 前向迭代器Forward Iterator支持读取写入移动例如forward_list9.4 双向迭代器Bidirectional Iterator支持向前向后--例如list map set9.5 随机访问迭代器Random Access Iterator功能最强。支持 - [] 例如vectorit5dequeit-2迭代器能力关系Random Access | Bidirectional | Forward Iterator | Input Iterator能力越往上越强。10. 不同容器迭代器类型容器迭代器类型vector随机访问deque随机访问array随机访问list双向map双向set双向forward_list前向unordered_map前向11. 迭代器失效问题重点这是面试高频问题。所谓迭代器失效迭代器仍然保存地址但是这个地址已经不是有效元素。11.1 vector插入导致失效例如vectorint v{1,2,3}; auto itv.begin(); v.push_back(4); cout*it;可能错误。原因vector扩容原空间1000: 1 2 3扩容5000: 1 2 3 4旧地址释放。it仍指向1000。失效。11.2 vector删除导致失效vectorint v{1,2,3}; auto itv.begin(); v.erase(it);删除后2 3原来的it失效。11.3 list迭代器失效listnode1 - node2 - node3删除node2node1 - node3只有删除节点的迭代器失效。其他迭代器仍有效。12. erase正确使用方式错误for(auto itv.begin(); it!v.end(); it) { if(*it3) v.erase(it); }原因erase后it失效。正确for(auto itv.begin(); it!v.end();) { if(*it3) { itv.erase(it); } else { it; } }因为vector/list的erase会返回删除位置后的迭代器。13. 迭代器和指针区别很多人认为迭代器就是指针。不完全正确。指针直接操作地址int* p;只能访问内存。迭代器是一种抽象。可能是指针是类对象例如vectoriterator ≈ T*listiterator: { Node* node; }14. 迭代器和算法STL算法sort find copy reverse都使用迭代器。例如排序vectorint v{3,1,2}; sort(v.begin(), v.end());sort不知道vector是什么数据在哪里它只认识begin() end() *15. 迭代器底层思想STL采用泛型编程算法templateclass Iterator void sort(Iterator first, Iterator last)不关心类型。只要求这个Iterator满足随机访问能力。这就是面向接口编程。16. 常用迭代器接口总结函数作用begin()返回头迭代器end()返回尾后迭代器rbegin()返回反向头rend()返回反向尾cbegin()const开始cend()const结束17. 迭代器总结什么是迭代器迭代器是STL中用于访问容器元素的一种对象本质是对指针的封装。为什么需要迭代器因为不同容器底层不同统一算法访问方式核心使用auto itcontainer.begin(); while(it!container.end()) { cout*it; it; }必须掌握begin/enditeratorconst_iteratorreverse_iterator五种迭代器分类迭代器失效STL算法与迭代器关系
