vector与list的模拟实现，主要是在实现过程中体会模板在编程中的应用，了解C++中迭代器的底层实现机制，因此笔者会将重点内容放在模板应用，迭代器底层实现，反向迭代器，迭代器失效等方面，至于其他的增删查改的功能，大家早已经掌握，此篇文章不在赘述
vector
构造函数
学习vector的过程，我们要重视官方库给我们提供了哪些构造函数，这是很重要的，因为很多情况下，我们并不是要创建一个空的vector，而是要把已经有的值赋给这个刚创建的vector，如果我们不清楚有哪些构造函数，那可能要费挺大劲，还要写循环来一个一个赋值
所以在模拟实现vector时，先看一下vector如何使用
上图是vector中的构造函数，忽略参数 const allocator_type& alloc = allocator_type()，这个是空间配置器，不是本篇文章的内容，无视就好
那么第一个构造函数可以认为是无参的，那就是创建一个空的vector
第二个构造函数参数 size_type n 表示要创建数目n个元素，参数const value_type& val = value_type() 表示创建的这些元素被初始化为什么值，如果不传这个参数，那么会调用该元素的默认构造函数，如果该元素是基本类型，那么C++也提供了解决方C++中int()被初始化为0，float()被初始化为0.0，char()被初始化为'\0'等等
第三个构造函数就用到迭代器，假设你有一个vector A，你想再创建一个vector B，并将A中的某一段连续的值传给B，那么在创建B的时候将这段连续值的起始值的迭代器和末尾值的下一个值的迭代器作为参数就可以了，因为迭代器采用的是左闭右开的形式
第四个构造函数大家就比较熟悉了，拷贝构造函数嘛，还记得为什么拷贝构造函数的参数一定要传引用嘛？不记得了可以翻看笔者类与对象那几篇博客细看
int main() { vector<int> test; test.push_back(1); test.push_back(2); test.push_back(3); test.push_back(4); test.push_back(5); vector<int> tmp(test.begin(), test.end()); for (auto e : tmp) { cout << e << " "; } return 0; }
成员函数的代码实现和易错点
resize, reserve
需要注意的有resize, reserve
vector中有两个标记参数，一个用来标记当前vector中共有多少个元素，用size表示，另一个用来标记当前vector容器申请了多少个元素空间，用capacity表示，那么size肯定是小于等于capacity的，我们平时在使用时不需要关心capacity，因为在检测到capacity不够时，会自动扩充，但是自动开辟capacity难免导致内存空间的浪费，但vector给我们提供了相应的成员函数，由我们自行开辟
reserve是申请内存空间函数，也就是专门用来开辟capacity的，此时的size是没有变的。reserve只管空间的大小，你reserve多少空间，它就开多大的capacity，需要注意，如果你reserve的空间小于当前的capacity，那么程序是不做出操作的，也就是不会缩小容量
resize主要是用来扩充或缩小元素个数的，也就是用来控制size的，如果你当前的元素个数小于resize的个数，那么会扩充到resize的个数，反之也一样，如果你当前元素的个数大于resize的个数，那么会缩小到resize的个数。注意，在这个过程中，如果你扩充元素的个数超过了当前的容量capacity，那么会自动扩充，但是在缩小resize时，容量是不会改变的
template<class T> class vector { public: typedef T value_type; typedef T* iterator; typedef const T* const_iterator; //get value size_t capacity() const { return _end - _begin; } size_t size() const { return _finish - _begin; } void reserve(size_t n) { if (n > capacity()) { value_type* tmp = new value_type[n]; size_t len = size(); if (_begin) { //memcpy(tmp, _begin, sizeof(T) * capacity()); //memcpy这里不能用，自定义类型，会产生浅拷贝 for (int i = 0; i < size(); i++) { tmp[i] = _begin[i]; } delete[] _begin; } _begin = tmp; _finish = _begin + len; _end = _begin + n; } } void resize(size_t n, value_type val = value_type()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish < _begin + n) { *_finish = val; ++_finish; } } else { _finish = _begin + n; } } private: iterator _begin; iterator _finish; iterator _end; };
与我们用C语言实现可变长数组不同的是，vector的实现加入了模板，泛型化编程，同时不再设置变量来存放size，capacity，而是统一采用迭代器来维护。整个vector由三个迭代器来维护，_begin表示vector元素的起始位置，_finish指向当前vector已存放的元素中的最后一个元素的下一个位置，_end指向空间的末尾，因为指针的减法结果为元素个数差，所以由_end减去_begin就能得到capacity值，由_finish减去_begin就能得到size的值
需要注意的是，在实现reserve的过程中，如果要扩充容量，不能直接使用C语言中的memcpy函数来将旧空间的值拷贝到新空间的值里，因为这样会导致浅拷贝，如果旧空间里存放的是指针之类的，在释放旧空间时，指针指向的内容会被回收，如果此时新空间再次使用该指针就会导致内存越界
iterator
迭代器的实现，迭代器的实现是比较简单的，因为vector是由迭代器来维护的，所以我们只需要返回_begin和_finish就可以了，不过，这里要提醒一下，迭代器的底层实现可不一定是指针，大家不要看到vector迭代器的背后就是元素指针，就认为所有的迭代器背后都是指针，等到list，大家会体会到这种差别的
iterator begin() { return _begin; } iterator end() { return _finish; } const_iterator begin() const { return _begin; } const_iterator end() const { return _finish; }
[ ]与at
在引用vector中的某个位置时，我们可以使用重载的[ ]，也可以使用at，两者功能差不多
[ ]中有断言检查，但是release情况下断言是失效的，因此我们需要使用at，at在检查出越界时会抛出异常，这会被程序捕获到，从而报错
迭代器失效
迭代器失效顾名思义，就是迭代器不能正常工作了，整个vector就是靠迭代器来维护的，如果迭代器失效了，那vector就无法使用了，先看看导致迭代器失效的原因吧
迭代器失效的问题出在实现insert时，所以我们要看看insert的具体实现是如何的
void insert(iterator pos, const value_type& val) { assert(pos >= _begin); assert(pos < _finish); if (_finish == _end) { size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reserve(newcapacity); } iterator end = _finish; while (end >= pos) { *end = *(end - 1); end--; } *pos = val; ++_finish; }
上面就是insert的实现代码，大略看了一下这段代码，你可能会觉得挺正常的呀，容量不够就扩容，然后把要插入元素的位置及后面所有的元素都向后移动一位，最后把要插入的值插入到对应的位置中，怎么就会导致迭代器失效了呢？
上面说的那些逻辑当然没有错，问题不是出在实现insert的逻辑上，而是出在pos身上，想一想，在出现扩容的情况时，我们会new一块新的内存空间，这都没有问题，但是pos指向的还是原来的那个vector的位置呀。也就是说，在扩容的时候，我们什么都更新了，但是没有更新pos的指向， 这就导致我们引用了已经释放的空间，程序直接报错。这个问题还是挺隐蔽的，因为只有到遇到需要扩容的情况时这个问题才会浮出水面。
解决办法也很简单，就是在扩容后记得更新pos的指向，那么首先我们要记录一下原先的pos到_begin的元素个数差， 用变量len记录，然后在开辟新的空间后，让pos指向新的空间的_begin+len的值，就会指向新空间的pos的对应的位置，下面是解决之后的代码
void insert(iterator pos, const value_type& val) { assert(pos >= _begin); assert(pos < _finish); if (_finish == _end) { //扩容会导致迭代器失效 size_t len = pos - _begin; //这一步的目的是防止迭代器失效 size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reserve(newcapacity); pos = _begin + len; } iterator end = _finish; while (end >= pos) { *end = *(end - 1); end--; } *pos = val; ++_finish; }
除了这些容易出错的地方，其他的也没有什么好说的，大部分都是增删查改的内容，大家可以通过官方提供的函数接口，尝试自行实现这些函数
list
list的底层就是一个双向循环链表，双向循环链表在学习数据结构的过程中，我们就已经实现过，不过当时使用的是C语言，切换到C++对大家问题也不大，因此笔者不打算花费大量的力气讲解整个list的代码。我们先把list的整体框架讲一下，然后把目光聚焦到迭代器上，实现list对大家来说不是什么难事，难得是实现list的迭代器，list的迭代器设计是相当的精妙，又是仰慕大佬的一天呐，学完list的迭代器，会让你对泛型编程，封装有更深刻的体会
list的整体框架
list是一个双向循环链表，那么首先得定义一个链表结构
template<class T> struct list_node { list_node<T>* previ; list_node<T>* next; T val; list_node(const T& x) :previ(nullptr), next(nullptr), val(x) {} };
链表定义完成，那么我们看看list类，这里为了让大家更清晰的了解list类的整体设计，我把涉及增删查改的成员函数都去掉了，这些函数的实现是不急的，等到我们把迭代器讲完，大家可以尝试自行实现这些函数
template <class T> class list { public: typedef list_node<T> node; void initialize_list() { _head = new node(T()); _head->previ = _head; _head->next = _head; _size = 0; } /* constructor */ list() :_head(nullptr) { initialize_list(); } list(const list<T>& x) :_head(nullptr) { initialize_list(); list<T> tmp(x.begin(), x.end()); swap(tmp); } /* capacity */ bool empty() { return _size <= 0; } size_t size() { return _size; } private: node* _head; size_t _size = 0; };
list的迭代器
迭代器统一了各个容器访问其内部数据的方式，在vector中，我们可以利用连续空间的指针加减，来进行访问，但是list不行，list的空间并不是连续的，我们无法靠某个节点的指针加减来访问其他的节点。如果我们直接使用节点提供的上一个或下一个节点的指针，那么就导致迭代器形式不统一，但是我们想要从当前节点到其他的节点那里，也只能通过当前节点的上一个或下一个节点的指针。
这就要求我们利用当前节点的上一个或下一个节点的指针来实现迭代器的访问模式，也就要求我们重新封装一些接口，涉及到封装我们就能想到单独写一个list_iterator类
template<class T> struct list_iterator { typedef list_node<T> node; typedef list_iterator<T> iterator; node* it = nullptr; list_iterator(node* x) :it(x){} list_iterator(const iterator &x) :it(x.it){} T& operator*() { return it->val; } iterator& operator++() { it = it->next; return *this; } iterator& operator--() { it = it->previ; return *this; } bool operator!=(const iterator& x) const { return it != x.it; } };
如上面的代码，把迭代器封装成一个类，然后基于节点的指针提供了相应的重载函数，也就是把节点指针封装成迭代器的接口形式
上面的迭代器如果正常使用是没有什么问题的，但是如果要保证只能以只读的形式访问数据，那就出问题了，我们上面解引用操作符重载时返回的是T&，也就是可以修改数据成员的，或许你会想再写一个const版本的重载函数不就行了吗？类似下面的情况
const T& operator*() { return it->val; }
如果认为这种形式可行，那说明对重载函数的定义理解不够深刻，重载函数表现在参数类型和参数数目的不同上，并不会去检查函数的返回值，所以编译器会认为它和正常版本的解引用操作符重载是同一个函数
既然const放在后面无法构成函数重载，那我放在前面总可以构成函数重载了吧，类似于下面这种写法
T& operator*() const { return it->val; }
没错，这种写法，确实可以和正常的解引用操作符重载函数构成重载关系，但是该函数只能由const 对象来调用呀，既然都const对象了，那肯定没有办法修改数据成员的，也就是说对++，--的重载全部都会失效，所以这个办法同样不行
那该如何解决这个问题呢？重新封装一个const版本的迭代器是一种解决方案，如果我们要求仅以只读模式使用迭代器，那么就可以调用这个const版本的迭代器，如下面的操作
template<class T> struct list_iterator { typedef list_node<T> node; typedef list_iterator<T> iterator; node* it = nullptr; list_iterator(node* x) :it(x){} list_iterator(const iterator &x) :it(x.it){} T& operator*() { return it->val; } iterator& operator++() { it = it->next; return *this; } iterator& operator--() { it = it->previ; return *this; } bool operator!=(const iterator& x) const { return it != x.it; } }; template<class T> struct const_list_iterator { typedef list_node<T> node; typedef list_iterator<T> iterator; node* it = nullptr; const_list_iterator(node* x) :it(x){} const_list_iterator(const iterator &x) :it(x.it){} const T& operator*() { return it->val; } iterator& operator++() { it = it->next; return *this; } iterator& operator--() { it = it->previ; return *this; } bool operator!=(const iterator& x) const { return it != x.it; } };
这样我们就可以解决问题了，但是大家仔细看看这两个类，除了解引用操作符重载的返回值不一样，其他部分可以说是一模一样，就为了一个返回值的不同，我们还要重写一个类，大家心里可能都会觉得不爽，而这个时候，就到了模板出场的时候了
模板是泛型化编程的基础，模板就是为了提高代码的复用率，减少代码冗余而存在的，如今我们公然干着不利用代码的复用率，增加冗余的勾当，模板第一个不答应
那模板是如何解决这件事情的呢？我们来仔细分析，为什么要写两个类，因为解引用操作符的返回值是不确定的，有时候我们希望返回 T&，而有的时候我们希望返回 const T&， 也就是说我们不确定返回值的类型是什么，模板一听，这叫什么事？我模板就是吃类型不确定这碗饭的，既然你返回值的类型不确定，那么再增加一个模板参数不就搞定了嘛
解决方法如下面这段代码
//哈哈用幽默的形式调侃一下，这些解决方法是大佬们艰辛努力提出来并实施的，在这里向大佬们的付出和贡献致敬
template<class T, class ref> struct list_iterator { typedef list_node<T> node; typedef list_iterator<T, ref> iterator; node* it = nullptr; list_iterator(node* x) :it(x){} list_iterator(const iterator &x) :it(x.it){} ref operator*() { return it->val; } iterator& operator++() { it = it->next; return *this; } iterator& operator--() { it = it->previ; return *this; } bool operator!=(const iterator& x) const { return it != x.it; } };
上面只是解决了迭代器中的返回值的类型，我们还需要在list类中实现相应的函数，确保能够调用到自己想要的迭代器的类型，下面是list类中的关于调用迭代器的成员函数
template <class T> class list { public: typedef list_node<T> node; //这里将两个版本的迭代器换成易懂的名称 typedef list_iterator<T, T&> iterator; typedef list_iterator<T, const T&> const_iterator; void initialize_list() { _head = new node(T()); _head->previ = _head; _head->next = _head; _size = 0; } /* constructor */ list() :_head(nullptr) { initialize_list(); } list(const list<T>& x) :_head(nullptr) { initialize_list(); list<T> tmp(x.begin(), x.end()); swap(tmp); } /* iterator */ //调用const或非const迭代器函数，会实例化出对应的迭代器类 iterator begin() const{ return iterator(_head->next); } const_iterator cbegin() const { return const_iterator(_head->next); } iterator end() const{ return iterator(_head); } const_iterator cend() const { return const_iterator(_head); } /* capacity */ bool empty() { return _size <= 0; } size_t size() { return _size; } private: node* _head; size_t _size = 0; };
到这里，list的迭代器的功能似乎实现的差不多了，但是别急，我们还有一些功能没有实现，大家看下面这个场景
struct coor { int _x; int _y; coor(int x = 0, int y = 0) :_x(x), _y(y){} };
如果我的元素的类型是上面的结构体，那我会以这种形式访问元素数据
//假设已经包含了我们自己实现的头文件的类 //下面我调用的类是我们上面实现过的 int main() { list<coor> test; //假设已经实现过了push_back test.push_back(coor(1,1)); test.push_back(coor(2,2)); auto it = test.begin(); std::cout << (*it)._x << (*it)._y <<endl; return 0; }
这样访问确实可以的，不过结构体指针有两种访问形式，一种是解引用后用"."来访问成员，还有一种就是直接使用"->"来访问成员，因此我们迭代器也应该提供两种访问形式，一种就是已经实现过的"*"，我们还要实现 "->"
我们想要达到的效果就是在访问coor的_x时不再使用(*it)._x这种形式，而是直接使用->_x这种形式完成访问
那实现方式和重载*差不多嘛，我们重载一个->函数，不过我们不能像重载*一样返回T的引用，在这个例子中也就是返回coor&，我们需要返回一个指针，因为只有结构体指针才能以->这种形式访问，所以我们需要返回coor*，下面是该函数的实现
T* operator->() { return &(it->val); }
那么该函数又是如何使用的呢？如下面的代码
//假设已经包含了我们自己实现的头文件的类 //下面我调用的类是我们上面实现过的 int main() { list<coor> test; //假设已经实现过了push_back test.push_back(coor(1,1)); test.push_back(coor(2,2)); auto it = test.begin(); std::cout << it->_x << it->_y <<endl; return 0; }
可能一些同学会觉得不对劲，it->这是使用重载函数->，重载函数返回的是元素类型的指针，应该还要加一个->，才能够访问数据呀，正确形式应该是it->->_x
确实，如果按照语法逻辑上来说是这样的，但是这种写法非常的别扭，因此在实际的使用中，我们会省略掉一个->，编译器也不支持it->->_x这种写法
如果你非要突出第二个->，不加上第二个->，就难以入眠，那你可以用这种写法
it.operator->()->_x; 这种写法编译器是支持的
这里我们又要引出上面提到过的问题，提供了新的访问数据的形式->，就要考虑，不一定是以可读可写的形式访问，同样需要const版本，不过这次，相信大家心中已经有了解决问题的方法，那就是同解决重载*时一样，再加一个模板参数，大家可以自行完成，我把代码放到下面，大家可以对照一下
template<class T, class ref, class ptr> struct list_iterator { typedef list_node<T> node; typedef list_iterator<T, ref, ptr> iterator; node* it = nullptr; list_iterator(node* x) :it(x){} list_iterator(const iterator &x) :it(x.it){} ref operator*() { return it->val; } ptr operator->() { return &(it->val); } iterator& operator++() { it = it->next; return *this; } iterator& operator--() { it = it->previ; return *this; } bool operator!=(const iterator& x) const { return it != x.it; } }; template <class T> class list { public: typedef list_node<T> node; //这里将两个版本的迭代器换成易懂的名称 typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; void initialize_list() { _head = new node(T()); _head->previ = _head; _head->next = _head; _size = 0; } /* constructor */ list() :_head(nullptr) { initialize_list(); } list(const list<T>& x) :_head(nullptr) { initialize_list(); list<T> tmp(x.begin(), x.end()); swap(tmp); } /* iterator */ //调用const或非const迭代器函数，会实例化出对应的迭代器类 iterator begin() const{ return iterator(_head->next); } const_iterator cbegin() const { return const_iterator(_head->next); } iterator end() const{ return iterator(_head); } const_iterator cend() const { return const_iterator(_head); } /* capacity */ bool empty() { return _size <= 0; } size_t size() { return _size; } private: node* _head; size_t _size = 0; };
到这里，list的讲解基本就结束了，因为list的难点主要就是在迭代器的实现上，只要迭代器的实现了，很多成员函数都是基于迭代器的增删查改，大家自行实现。后面还有一个关于迭代器的小知识，如果感兴趣的话可以看一看，不感兴趣可以跳过这个，直接去看反向迭代器
无法将非const迭代器赋给const迭代器
我们都了解这么一个准则，在编程中，权限只能够缩小不能够放大。一个非const数据类型加上const意味着权限的缩小，从可读可写变成仅可读，同样我们可以将一个非const数据类型赋值给const数据类型，这是因为权限可以缩小，但是一个const数据类型不能够赋给非const数据类型，权限不能够放大
但是在我们实现的迭代器中出现了这样一个怪问题，非const迭代器不能赋给const迭代器
这是怎么一回事呢？我们是将非const迭代器赋值给const迭代器呀，这个过程没有涉及到权限的放大呀，而且还是权限的缩小呢，为什么编译器就报错了呢？
//下面为了简便，非const迭代器就用iterator来称呼，const迭代器用const_iterator来称呼
翻译一下报错结果就是不存在从iterator到const_iterator的适当转换，也就是在const_iterator中不存在拷贝构造可以将iterator转换成const_iterator
你可能会说我们确实没有在迭代器中实现拷贝构造，但是编译器不是会默认生成一个拷贝构造嘛，为什么就不可以呢？
确实，编译器会默认生成一个拷贝构造，但是我们忽略了iterator和const_iterator其实完全就是两个类，iterator的参数类型是，const_iterator的参数类型是 。对应到我们上面的例子中，t的迭代器的参数类型就是，it的迭代器的参数类型是，这是两种不同的参数类型，所以模板在实例化迭代器类时会实例化出两个，分别是iterator类，和const_iterator类
const_iterator固然会默认生成一个拷贝构造，但是是以自身为标准生成的，也就是说const_iterator的默认生成的拷贝构造的参数是const_iterator，是const_iterator类本身，在泛型编程模板的实例化过程中，编译器会完全把const_iterator，iterator当成两个类来处理，既然参数都不一样，那肯定就没有办法转化，这也就是为什么会报出没有适当转换的错误
我知道这段内容有些难以理解，不理解也是没有关系的。因为笔者表达能力有限，又不能面对面交流，如果真的很想搞懂，就要明白iterator和const_iterator表达的就是两个迭代器类，这两个类都没有实现拷贝构造，简单理解const_iterator的默认生成的拷贝构造是这样的const_iterator(const_iterator& x) { ... }
而我们传过去的参数是iterator，iterator和const_iterator不是同一个类，故而不能直接传，这就是报没有适当转化错误的原因
解决方法：
找到出问题的原因，我们就知道该如何解决了，既然const_iterator自己生成的默认拷贝构造没有办法使用，那么我们就自己写一个拷贝构造，这个拷贝构造的参数就是iterator
我们在迭代器类中实现这一个拷贝构造就行了，那为什么不实现const_iterator传给iterator的拷贝构造呢？因为权限不能被放大呀，const怎么能传给非const呢？这是不行滴
下面是代码
template<class T, class ref , class ptr> struct list_iterator { //这里一定要声明出iterator //不然我们在自己实现拷贝构造时编译器不认识 iterator typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; typedef list_iterator<T, ref, ptr> self; typedef list_node<T> node; node* it = nullptr; list_iterator(node* x) :it(x){} list_iterator(const iterator &x) :it(x.it){} ref operator*() { return it->val; } ptr operator->() { return &it->val; } self& operator++() { it = it->next; return *this; } self& operator--() { it = it->previ; return *this; } self& operator++(int) { self tmp = *this; it = it->next; return tmp; } self& operator--(int) { self tmp = *this; it = it->previ; return tmp; } bool operator!=(const self& x) const { return it != x.it; } };
反向迭代器
反向迭代器就是正向迭代器的逆过程，如使用begin实际上返回的是末尾位置，使用end则返回的是起始位置，然后++则是从末尾位置遍历到起始位置
我们要实现反向迭代器可以利用已经写好的正向迭代器，但是正向迭代器的功能与反向迭代器的功能不符怎么办，那么我们就基于正向迭代器提供的接口重新封装一套接口，比如，反向迭代器的begin就返回正向迭代器的end()-1，这让我想起了计算机界很有名的一句话，计算机的问题都可以靠加一个抽象层来解决
那么实践一下，首先就是重新写一个reverse_iterator类，然后重新封装正向迭代器提供的功能接口，下面是实现代码
template<class Iterator, class ref, class ptr> struct reverse_iterator { typedef reverse_iterator<Iterator, ref, ptr> self; reverse_iterator(const Iterator& x) :_con(x) {} reverse_iterator(const reverse_iterator& x) :_con(x._con) {} ref operator*() { Iterator tmp = _con; return *(--tmp); } ptr operator->() { return &(operator*()); } self& operator++() { --_con; return *this; } self& operator++(int) { self tmp = _con; --_con; return tmp; } self& operator--() { ++_con; return *this; } self& operator--(int) { self tmp = _con; ++_con; return tmp; } bool operator!=(const self& x) { return _con != x._con; } private: Iterator _con; };
因为是基于正向迭代器的封装，所以在类中我们要首先定义一个iterator，模板中的ref和ptr大家应该都明白，是返回值的数据类型。那为什么iterator也是一个模板参数呢？因为我们写的这个反向迭代器不仅适用于list，还可以适用于其他类型的容器，只要把迭代器传过来就可以了，不同容器的迭代器不一样，iterator自然要是一个不确定类型的模板参数了
这里要说一下，反向迭代器同样存在非const迭代器无法转向const迭代器的问题，解决方法与上面所说的类似，这里就不赘述了
