C++ STL迭代器原理和简单实现

### 1. 迭代器简介 为了提高C++编程的效率，STL（Standard Template Library）中提供了许多容器，包括vector、list、map、set等。然而有些容器（vector）可以通过下标索引的方式访问容器里面的数据，但是大部分的容器（list、map、set）不能使用这种方式访问容器中的元素。**为了统一访问不同容器时的访问方式**，STL为每种容器在实现的时候设计了一个内嵌的**iterator类**，不同的容器有自己专属的迭代器（专属迭代器负责实现对应容器访问元素的具体细节），使用迭代器来访问容器中的数据。除此之外，**通过迭代器可以将容器和通用算法结合在一起**，只要给予算法不同的迭代器，就可以对不同容器执行相同的操作，例如find查找函数（因为迭代器提供了统一的访问方式，这是使用迭代器带来的好处）。迭代器对一些基本操作如\*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的容器，所有迭代器的使用和指针的使用非常相似。通过begin，end函数获取容器的头部和尾部迭代器，**end迭代器**不包含在容器之内，**当begin和end返回的迭代器相同时表示容器为空。** > STL主要由 **容器、迭代器、算法、函数对象、和内存分配器** 五大部分构成。 ### 2. 迭代器的实现原理 首先，看看STL中迭代器的实现思路：  从上图中可以看出，STL通过类型别名的方式实现了对外统一；在不同的容器中类型别名的真实迭代器类型是不一样的，而且真实迭代器类型对于++、--、\*、->等基本操作的实现方式也是不同的。（PS：迭代器很好地诠释了接口与实现分离的意义） 既然我们已经知道了迭代器的实现思路，现在如果让我们自己设计一个list容器的简单迭代器，应该如何实现呢？ 1. list类需要有操作迭代器的方法 1. begin/end 2. insert/erase/emplace 2. list类有一个内部类list_iterator 1. 有一个成员变量ptr指向list容器中的某个元素 2. iterator负责重载++、--、\*、->等基本操作 3. list类定义内部类list_iterator的类型别名 以上就是实现一个list容器的简单迭代器需要考虑的具体细节。 ### 3. 迭代器的简单实现 my_list.h（**重要部分有注释说明**） ```C++ // // Created by wengle on 2020-03-14. // #ifndef CPP_PRIMER_MY_LIST_H #define CPP_PRIMER_MY_LIST_H #include template class node { public: T value; node *next; node() : next(nullptr) {} node(T val, node *p = nullptr) : value(val), next(p) {} }; template class my_list { private: node *head; node *tail; int size; private: class list_iterator { private: node *ptr; //指向list容器中的某个元素的指针 public: list_iterator(node *p = nullptr) : ptr(p) {} //重载++、--、*、->等基本操作 //返回引用，方便通过*it来修改对象 T &operator*() const { return ptr->value; } node *operator->() const { return ptr; } list_iterator &operator++() { ptr = ptr->next; return *this; } list_iterator operator++(int) { node *tmp = ptr; // this 是指向list_iterator的常量指针，因此*this就是list_iterator对象，前置++已经被重载过 ++(*this); return list_iterator(tmp); } bool operator==(const list_iterator &t) const { return t.ptr == this->ptr; } bool operator!=(const list_iterator &t) const { return t.ptr != this->ptr; } }; public: typedef list_iterator iterator; //类型别名 my_list() { head = nullptr; tail = nullptr; size = 0; } //从链表尾部插入元素 void push_back(const T &value) { if (head == nullptr) { head = new node(value); tail = head; } else { tail->next = new node(value); tail = tail->next; } size++; } //打印链表元素 void print(std::ostream &os = std::cout) const { for (node *ptr = head; ptr != tail->next; ptr = ptr->next) os << ptr->value << std::endl; } public: //操作迭代器的方法 //返回链表头部指针 iterator begin() const { return list_iterator(head); } //返回链表尾部指针 iterator end() const { return list_iterator(tail->next); } //其它成员函数 insert/erase/emplace }; #endif //CPP_PRIMER_MY_LIST_H ``` test.cpp ```C++ // // Created by wengle on 2020-03-14. // #include #include "my_list.h" struct student { std::string name; int age; student(std::string n, int a) : name(n), age(a) {} //重载输出操作符 friend std::ostream &operator<<(std::ostream &os, const student &stu) { os << stu.name << " " << stu.age; return os; } }; int main() { my_list l; l.push_back(student("bob", 1)); //临时量作为实参传递给push_back方法 l.push_back(student("allen", 2)); l.push_back(student("anna", 3)); l.print(); for (my_list::iterator it = l.begin(); it != l.end(); it++) { std::cout << *it << std::endl; *it = student("wengle", 18); } return 0; } ``` ### 4. 迭代器失效 ```C++ // inserting into a vector #include #include int main () { std::vector myvector (3,100); std::vector::iterator it; it = myvector.begin(); it = myvector.insert ( it , 200 ); myvector.insert (it,200,300); //it = myvector.insert (it,200,300); myvector.insert (it,5,500); //当程序执行到这里时，大概率会crash for (std::vector::iterator it2=myvector.begin(); it2