首页 > 代码库 > C++ 迭代器原理、失效和实现
C++ 迭代器原理、失效和实现
目录
- 迭代器的使用
- 迭代器的种类
- 迭代器的失效
- 迭代器的实现
1.迭代器的使用
为了提高C++编程的效率，STL中提供了许多容器，包括vector、list、map、set等。有些容器例如vector可以通过脚标索引的方式访问容器里面的数据，但是大部分的容器不能使用这种方式，例如list、map、set。STL中每种容器在实现的时候设计了一个内嵌的iterator类，不同的容器有自己专属的迭代器，使用迭代器来访问容器中的数据。除此之外，通过迭代器，可以将容器和通用算法结合在一起，只要给予算法不同的迭代器，就可以对不同容器执行相同的操作，例如find查找函数。迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的数据结构，所有迭代的使用和指针的使用非常相似。通过begin，end函数获取容器的头部和尾部迭代器，end 迭代器不包含在容器之内，当begin和end返回的迭代器相同时表示容器为空。
template<typename InputIterator, typename T>InputIterator find(InputIterator first, InputIterator last, const T &value){ while (first != last && *frist != value) ++first; return first;}
#include <iostream>#include <vector>#include <list>#include <algorithm>using namespace std;int main(int argc, const char *argv[]){ int arr[5] = { 1, 2, 3, 4, 5}; vector<int> iVec(arr, arr + 5);//定义容器vector list<int> iList(arr, arr + 5);//定义容器list //在容器iVec的头部和尾部之间寻找整形数3 vector<int>::iterator iter1 = find(iVec.begin(), iVec.end(), 3); if (iter1 == iVec.end()) cout<<"3 not found"<<endl; else cout<<"3 found"<<endl; //在容器iList的头部和尾部之间寻找整形数4 list<int>::iterator iter2 = find(iList.begin(), iList.end(), 4); if (iter2 == iList.end()) cout<<"4 not found"<<endl; else cout<<"4 found"<<endl; return 0;}
2.迭代器的种类
根据迭代器所支持的操作，可以把迭代器分为5类。
1) 输入迭代器：是只读迭代器，在每个被遍历的位置上只能读取一次。例如上面find函数参数就是输入迭代器。
2) 输出迭代器：是只写迭代器，在每个被遍历的位置上只能被写一次。
3) 前向迭代器：兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。但它不支持operator--，所以只能向前移动。
4) 双向迭代器：很像前向迭代器，只是它向后移动和向前移动同样容易。
5) 随机访问迭代器：有双向迭代器的所有功能。而且，它还提供了“迭代器算术”，即在一步内可以向前或向后跳跃任意位置， 包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。
STL每种容器类型都定义了 const_iterator，只能读取容器的值，不能修改所指向容器范围内元素的值。vector、string、Deque随机存取迭代器；List、Set、map、mutiset、multimap双向迭代器。
3.迭代器失效
容器的插入insert和erase操作可能导致迭代器失效，对于erase操作不要使用操作之前的迭代器，因为erase的那个迭代器一定失效了，正确的做法是返回删除操作时候的那个迭代器。
#include <vector>using namespace std;int main(int argc, const char *argv[]) { int arr[5] = { 1, 2, 3, 4, 5 }; vector<int> iVec(arr, arr + 5); //定义容器vector //迭代器失效// for (vector<int>::iterator it = iVec.begin(); it != iVec.end();) {// iVec.erase(it);// } //返回erase操作之后的迭代器 for (vector<int>::iterator it = iVec.begin();it != iVec.end();) { it = iVec.erase(it); } return 0;}
4.迭代器的实现
STL中每个容器都有自己的迭代器，各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念，下面在单链表类中内嵌入一个iterator的类来实现单链表的迭代
1 #include <iostream> 2 3 template<typename T> 4 struct ListNode { 5 T value; 6 ListNode* next; 7 ListNode() { 8 next = 0; 9 } 10 ListNode(T val, ListNode *p = nullptr) : 11 value(val), next(p) { 12 } 13 }; 14 15 template<typename T> 16 class List { 17 private: 18 ListNode<T> *m_pHead; 19 ListNode<T> *m_pTail; 20 int m_nSize; 21 public: 22 List() { 23 m_pHead = nullptr; 24 m_pTail = nullptr; 25 m_nSize = 0; 26 } 27 //从链表尾部插入元素 28 void push_back(T value) { 29 if (m_pHead == nullptr) { 30 m_pHead = new ListNode<T>(value); 31 m_pTail = m_pHead; 32 } else { 33 m_pTail->next = new ListNode<T>(value); 34 m_pTail = m_pTail->next; 35 } 36 37 } 38 39 //打印链表元素 40 void print(std::ostream &os = std::cout) const { 41 for (ListNode<T> *ptr = m_pHead; ptr != m_pTail->next ; ptr = ptr->next) 42 std::cout << ptr->value << " "; 43 os << std::endl; 44 } 45 46 //内置迭代器 47 class iterator { 48 private: 49 ListNode<T> *m_ptr; 50 public: 51 iterator(ListNode<T>* p = nullptr) : 52 m_ptr(p) { 53 } 54 55 T operator*() const { 56 return m_ptr->value; 57 } 58 ListNode<T>* operator->() const { 59 return m_ptr; 60 } 61 iterator& operator++() { 62 m_ptr = m_ptr->next; 63 return *this; 64 } 65 iterator operator++(int) { 66 ListNode<T>* tmp = m_ptr; 67 m_ptr = m_ptr->next; 68 return iterator(tmp); 69 } 70 71 bool operator==(const iterator &arg) const { 72 return arg.m_ptr == this->m_ptr; 73 } 74 75 bool operator!=(const iterator &arg) const { 76 return arg.m_ptr != this->m_ptr; 77 } 78 79 }; 80 81 //返回链表头部指针 82 iterator begin() const { 83 return iterator(m_pHead); 84 } 85 86 //返回链表尾部指针 87 iterator end() const { 88 return iterator(m_pTail->next); 89 } 90 91 //其它成员函数 92 93 }; 94 95 int main() { 96 List<int> l; 97 l.push_back(1); 98 l.push_back(2); 99 l.print();100 for (List<int>::iterator it = l.begin(); it != l.end(); ++it) {101 std::cout << *it << " ";102 }103 std::cout << std::endl;104 return 0;105 }
参考： http://blog.csdn.net/shudou/article/details/11099931
C++ 迭代器原理、失效和实现