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（重要部分有注释说明）

//
// created by wengle on 2020-03-14.
//

#ifndef cpp_primer_my_list_h
#define cpp_primer_my_list_h

#include <iostream>

template<typename t>
class node {
public:
    t value;
    node *next;
    node() : next(nullptr) {}
    node(t val, node *p = nullptr) : value(val), next(p) {}
};

template<typename t>
class my_list {
private:
    node<t> *head;
    node<t> *tail;
    int size;

private:
    class list_iterator {
    private:
        node<t> *ptr; //指向list容器中的某个元素的指针

    public:
        list_iterator(node<t> *p = nullptr) : ptr(p) {}
        
        //重载++、--、*、->等基本操作
        //返回引用，方便通过*it来修改对象
        t &operator*() const {
            return ptr->value;
        }

        node<t> *operator->() const {
            return ptr;
        }

        list_iterator &operator++() {
            ptr = ptr->next;
            return *this;
        }

        list_iterator operator++(int) {
            node<t> *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<t>(value);
            tail = head;
        } else {
            tail->next = new node<t>(value);
            tail = tail->next;
        }
        size++;
    }

    //打印链表元素
    void print(std::ostream &os = std::cout) const {
        for (node<t> *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

//
// created by wengle on 2020-03-14.
//

#include <string>
#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<student> 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<student>::iterator it = l.begin(); it != l.end(); it++) {
        std::cout << *it << std::endl;
        *it = student("wengle", 18);
    }
    return 0;
}

4. 迭代器失效

// inserting into a vector
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector (3,100);
  std::vector<int>::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<int>::iterator it2=myvector.begin(); it2<myvector.end(); it2++)
    std::cout << ' ' << *it2;
  std::cout << '\n';

  return 0;
}

上面的代码很好地展示了什么是迭代器失效？迭代器失效会导致什么样的问题？
当执行完myvector.insert (it,200,300);这条语句后，实际上myvector已经申请了一块新的内存空间来存放之前已保存的数据和本次要插入的数据，由于it迭代器内部的指针还是指向旧内存空间的元素，一旦旧内存空间被释放，当执行myvector.insert (it,5,500);时就会crash（ps：因为你通过iterator的指针正在操作一块已经被释放的内存，大多数情况下都会crash)。迭代器失效就是指：迭代器内部的指针没有及时更新，依然指向旧内存空间的元素。

上图展示了stl源码中vector容器insert方法的实现方式。当插入的元素个数超过当前容器的剩余容量时，就会导致迭代器失效。这也是测试代码中myvector.insert (it,200,300);插入200个元素的原因，为了模拟超过当前容器剩余容量的场景，如果你的测试环境没有crash，可以将插入元素设置的更多一些。

5. 参考资料

1. iterator invalidation rules