迭代器简介

STL为每种容器在实现的时候设计了一个内嵌的iterator类，不同的容器有自己专属的迭代器（专属迭代器负责实现对应容器访问元素的具体细节），使用迭代器来访问容器中的数据。

迭代器的实现原理

  1. //
  2. // Created by wengle on 2020-03-14.
  3. //
  5. #ifndef CPP_PRIMER_MY_LIST_H
  6. #define CPP_PRIMER_MY_LIST_H
  8. #include <iostream>
  10. template<typename T>
  11. class node {
  12. public:
  13.     T value;
  14.     node *next;
  15.     node() : next(nullptr) {}
  16.     node(T val, node *p = nullptr) : value(val), next(p) {}
  17. };
  19. template<typename T>
  20. class my_list {
  21. private:
  22.     node<T> *head;
  23.     node<T> *tail;
  24.     int size;
  26. private:
  27.     class list_iterator {
  28.     private:
  29.         node<T> *ptr; //指向list容器中的某个元素的指针
  31.     public:
  32.         list_iterator(node<T> *p = nullptr) : ptr(p) {}
  34.         //重载++、--、*、->等基本操作
  35.         //返回引用，方便通过*it来修改对象
  36.         T &operator*() const {
  37.             return ptr->value;
  38.         }
  40.         node<T> *operator->() const {
  41.             return ptr;
  42.         }
  44.         list_iterator &operator++() {
  45.             ptr = ptr->next;
  46.             return *this;
  47.         }
  49.         list_iterator operator++(int) {
  50.             node<T> *tmp = ptr;
  51.             // this 是指向list_iterator的常量指针，因此*this就是list_iterator对象，前置++已经被重载过
  52.             ++(*this);
  53.             return list_iterator(tmp);
  54.         }
  56.         bool operator==(const list_iterator &t) const {
  57.             return t.ptr == this->ptr;
  58.         }
  60.         bool operator!=(const list_iterator &t) const {
  61.             return t.ptr != this->ptr;
  62.         }
  63.     };
  65. public:
  66.     typedef list_iterator iterator; //类型别名
  68.     my_list() {
  69.         head = nullptr;
  70.         tail = nullptr;
  71.         size = 0;
  72.     }
  74.     //从链表尾部插入元素
  75.     void push_back(const T &value) {
  76.         if (head == nullptr) {
  77.             head = new node<T>(value);
  78.             tail = head;
  79.         } else {
  80.             tail->next = new node<T>(value);
  81.             tail = tail->next;
  82.         }
  83.         size++;
  84.     }
  86.     //打印链表元素
  87.     void print(std::ostream &os = std::cout) const {
  88.         for (node<T> *ptr = head; ptr != tail->next; ptr = ptr->next)
  89.             os << ptr->value << std::endl;
  90.     }
  92. public:
  93.     //操作迭代器的方法
  94.     //返回链表头部指针
  95.     iterator begin() const {
  96.         return list_iterator(head);
  97.     }
  99.     //返回链表尾部指针
  100.     iterator end() const {
  101.         return list_iterator(tail->next);
  102.     }
  104.     //其它成员函数 insert/erase/emplace
  105. };
  107. #endif //CPP_PRIMER_MY_LIST_H
  1. for (my_list<student>::iterator it = l.begin(); it != l.end(); it++) {
  2.     std::cout << *it << std::endl;
  3.     *it = student("wengle", 18);
  4. }

迭代器存储的是一个指向list容器中的某个元素的指针，我们将各种操作符重载来达到迭代的目的，另 end 指向的是最后一个元素之后的位置。

迭代器失效

  1. #include <iostream>
  2. #include <vector>
  4. int main ()
  5. {
  6.   std::vector<int> myvector (3,100);
  7.   std::vector<int>::iterator it;
  9.   it = myvector.begin();
  10.   it = myvector.insert ( it , 200 );
  12.   myvector.insert (it,200,300);
  13.   //it = myvector.insert (it,200,300);
  14.   myvector.insert (it,5,500); //当程序执行到这里时，大概率会crash
  15.   for (std::vector<int>::iterator it2=myvector.begin(); it2<myvector.end(); it2++)
  16.     std::cout << ' ' << *it2;
  17.   std::cout << '\n';
  19.   return 0;
  20. }

当执行完myvector.insert (it,200,300);这条语句后，实际上myvector已经申请了一块新的内存空间来存放之前已保存的数据和本次要插入的数据，由于it迭代器内部的指针还是指向旧内存空间的元素，一旦旧内存空间被释放，当执行myvector.insert (it,5,500);时就会crash.