1. vector的基本框架
STL的源代码整体考虑的东西比较多，还要考虑和其他地方的结合，因此整体的设计是比较复杂的。基于这一系列原因，我们会以简单的形式去实现其核心框架接口，方便去学习 vector。我们可以先看一看STL源代码的整体框架，一些要实现的接口函数不会实现的时候才去看看细节。现在自己看源码还不太好，且看不懂，跟着这篇博客看就挺好的（自夸+1）
以下是基于《STL源码剖析》用到的vector的部分源码：
其中最重要的就是三个私有成员 start 、finish 和 end_of_storage。
想想模拟代码的实现，为了和库中的 vector 进行区分，这里依然用命名空间包含起来。
造一个 vector 的类模板去适应各种类型，用 typedef 将 T* 重命名为 iterator。
1.1 构造析构和容量
经过前面string的学习和上面的源码，直接放vector.h ：
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> class vector { public: typedef T* iterator; vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} ~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } private: iterator _start; iterator _fnish; iterator _end_of_storage; }; }
1.2 push_back，reserve和operator[ ]
我们这里先实现一个简单的 push_back，以便于我们能先把 vector 跑起来。我们的 push_back 没有空间配置器，我们就用 new 去替代它。
尾插需要做哪些事？
1：检查是否需要增容
需要增容，就先增容后再插入数据；不需要增容，就直接插入数据。
我们先去思考，如何判断是否需要增容 ——
我们之前的判断方式是 size == capacity 的时候需要增容问题是，这次我们没有定义 _size 和 _capacity，取而代之的是 _start 、 _finish 和_end_of_storage的形式。
想想： 当 _finish == _end_of_storage时，不就说明容量不够了吗？
2：如果需要增容
前面已经知道，vector是有reserve接口的，增容我们先实现reserve：
如果要增容：
① 开一块带有新容量的空间存到 tmp 中。
② 再把原空间的数据拷贝到新空间。（还能用memcpy吗，我们先用着）
③ 并释放原有的旧空间
④ 最后将 _start 、_finish 和 _end_of_storage指向新的空间。
值得注意的是，最后一步如果先将 _start 指向 tmp 后，再计算 _finish 时，
此时不能现场算 size() ，现场算会出问题，因为 _start 已经被更新成 tmp 了，
如果不想改变顺序，还是想按 _start、_finish 和 _eos 的顺序赋值，
我们可以提前把 size() 算好，存到一个变量中。
此外，真 vector 这里扩容是要调空间配置器的，开空间和初始化是分开的。
我们这里的实现也没有空间配置器，对于空间配置器的知识我们放到后面再说，
我们目前的重点不是空间配置器，重点是 vector。
至于新容量给多少，我们还是按照自己的习惯，首次给4默认扩2倍的方式去增容。
reserve代码：
void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if(_start) { memcpy(tmp, _start, sizeof(T) * sz); delete[] _start; } _start = tmp; _finish = tmp + sz; _end_of_storage = tmp + n; } }
3：插入数据
查增容和增容都已经分析完了，最后就只剩一个插入了，插入是最简单的，
因为_finish指向的是最后一个元素的下一个位置，我们直接让要插入的元素赋值给_finish，
然后++_finish就行了。push_back代码：
void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; }
为了方便测试尾插的效果，我们先来实现一下 operator[] ，利用 "下标+方括号" 的方式遍历。
这有两个接口，我们一起实现了：
T& operator[](size_t pos) { assert(pos < size()); return *(_start + pos); } const T& operator[](size_t pos) const { assert(pos < size()); return *(_start + pos); }
T：由于我们不知道返回值类型，所以给 T。
T&：引用返回减少拷贝。
const是给const对象用的：这里 cosnt 修饰 T 和 this，是为了限制写。
测试一下：（vector.h:）
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> class vector { public: typedef T* iterator; vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} ~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; } void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * sz); delete[] _start; } _start = tmp; _finish = tmp + sz; _end_of_storage = tmp + n; } } T& operator[](size_t pos) { assert(pos < size()); return *(_start + pos); } const T& operator[](size_t pos) const { assert(pos < size()); return *(_start + pos); } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }
Test.c:
#include "vector.h" namespace rtx { void Test1() { vector<int> v; cout << v.size() << " " << v.capacity() << endl; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout << v.size() << " " << v.capacity() << endl; v.push_back(5); cout << v.size() << " " << v.capacity() << endl; for (size_t i = 0; i < v.size();++i) { cout << v[i] << " "; } cout << endl; } } int main() { rtx::Test1(); return 0; }
2. vector的迭代器
2.1 四个基本迭代器
vector 的迭代器是一个原生指针：
template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator;
前面源码看到，begin() 和 end() ，直接分别返回 _start 和 _finish 即可，
const 类型的迭代器，即可读不可写。在实现的时候用 const 修饰即可：
测试迭代器的效果：（范围for也能用了）
void Test2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (size_t i = 0; i < v.size();++i) { ++v[i]; cout << v[i] << " "; } cout << endl; vector<int>::iterator it = v.begin(); while (it != v.end()) { --(*it); cout << *it << " "; ++it; } cout << endl; for (const auto& e : v) { cout << e << " "; } cout << endl; }
2.2 迭代器区间初始化
上一篇说到vector是支持迭代器区间初始化的：
拷贝构造放在后面再讲，先实现迭代器区间初始化：
因为传过来的迭代器可以是任意的，所以这又是一个模板：
（一个类模板的成员函数，又可以是一个函数模板）：
void Test2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (size_t i = 0; i < v.size();++i) { ++v[i]; cout << v[i] << " "; } cout << endl; vector<int>::iterator it = v.begin(); while (it != v.end()) { --(*it); cout << *it << " "; ++it; } cout << endl; for (const auto& e : v) { cout << e << " "; } cout << endl; string s("hello world"); vector<int> v1(s.begin(), s.end());// 存了ASCII码 for (const auto& e : v1) { cout << e << " "; } cout << endl; }
为什么这里要叫 InputIterator？不用它行不行？
想要知道这个问题，我们先讲解一下迭代器的分类。
2.3 迭代器的分类
迭代器可以分为这么几类：
① 输入 / 输出迭代器：input_iterator / output_iterator
特点：单步向前迭代，不可写 / 单步向前迭代，可写，无对应类型
② 单向迭代器：forward_iterator
特点：满足以上所有功能，并且能 ++
（不能 - -没有 rbegin / rend）
（C++11）
（C++11）
（C++11）
③ 双向迭代器：bidirectional_iterator
特点：满足以上功能，并且能 ++，还能 - -
④ 随机迭代器：randomaccess_iterator
特点：满足以上所有功能，能 ++ 能 - -，还能 + 和 -
它们本质上是一个继承关系：下面是子类，上面是父类。
子类都是一个父类，因为它满足父类的所有特征。
也就是说，虽然在语法上它是个模板，允许你传任意类型的迭代器，
但是在更深层次上存在着更进一步的限制 ——
它要求你传随机迭代器，你就不能用双向迭代器。因为只有随机迭代器才能满足随机迭代器的所有操作。换言之，你不能用功能比它指定的迭代器少的迭代器。（可以理解为权限的放大）
它要求你用双向迭代器，你就不能用单向迭代器，因为单项迭代器不能满足所有双向迭代器的操作。但是你可以用比它功能多的迭代器，比如随机迭代器，因为随机迭代器也能满足双向迭代器的操作。因为随机迭代器是双向迭代器的子类，它满足父类（双向迭代器）的所有功能。（可以理解为权限的缩小）
我们弄明白了这些，我们再回到刚才提的问题 —为什么这里要叫 InputIterator？
首先，InputIterator 是输入迭代器，这么写是为了满足命名规范。
可以不用，我们可以传单向迭代器、双向迭代器，也可以传随机迭代器。
因为这些迭代器都满足输入迭代器的所有功能。
从C语言到C++_15(vector的模拟实现)+迭代器失效问题（中）：https://developer.aliyun.com/article/1521294
