【C++】—— vector 的模拟实现
0 前言1 vector 的成员变量1.1 stl 库中的 vector 成员变量1.2 模拟实现 vector 成员变量 2 迭代器3 size、capacity、empty4 opreator[ ]5 reserve5.1 初版 reserve5.2 _finish 的处理5.3 深拷贝5.4 终版 6 push_back 与 pop_back7 打印函数7.1 初写打印7.2 typename 关键字7.3 打印函数进阶 8 insert8.1 insert 初版8.2 迭代器失效8.2.1 情况一：类似野指针8.2.2 algorithm 库中的查找函数8.2.3 情况二：insert 后再对 pos 进行访问8.2.3.1 不扩容的情况8.2.3.1 扩容的情况 8.2.4、解决方法8.2.4.1、想法一8.2.4.2、想法二 8.3 总结 9 erase10 resize11 构造函数系列11.1 默认构造11.2 拷贝构造11.3 迭代器区间构造 与 n 个 value 构造11.3.1 迭代器区间构造11.3.2 n 个value构造11.3.3 注意事项 12 赋值运算符重载12.1 传统写法12.2 现代写法 13 源码
0 前言
前面，我们学习了 s t r i n g string string，并模拟实现了它，下面我们来学习 v e c t o r vector vector
v e c t o r vector vector 的底层即我们前面曾经学过的顺序表，它属于 STL库，为了让我们更加深入理解 v e c t o r vector vector，接下来我们将模拟实现 v e c t o r vector vector
1 vector 的成员变量
1.1 stl 库中的 vector 成员变量
我们学习数据结构时，曾经模拟实现过顺序表。当时我们用一个指针 a a a 管理从堆开辟的空间， s i z e size size 表示当前有效数据的个数， c a p a c i t y capacity capacity 表示当前空间的大小。
但是， s t l stl stl库 中的 v e c t o r vector vector 的成员变量有所差别：它的成员变量是三个迭代器
我们知道，迭代器全部都是 t y p e d e f typedef typedef 出来的，那 v e c t o r vector vector 的迭代器是什么呢？
可以看到，其迭代器就是 原生指针！
那start、finish、end_of_storage 变量又是什么意思呢？面对未知的东西，我们应大胆假设，小心求证。
不管他底层如何， v e c t o r vector vector 终究逃不过扩容，那我们不难猜想：start 肯定是一个指针指向一个开始，finish指向某个结束，至于end_of_storage， s t o r a g e storage storage 是存储的意思，所以我们大胆猜测end_of_storage与空间相关，可能就是空间结束位置；那这样的话finish 可能表示数据的结束
那我们怎么取求证呢？我们可以通过一些我们熟悉功能的函数来确认
可以看到， b e g i n begin begin 返回的是第一个有效数据位置，这里是start；而 e n d end end 返回的是最后一个有效数据的下一个位置，这里返回的是finish； c a p a c i t y capacity capacity 表示空间的大小，这里返回的是end_of_storage - begin()。
因此我们的猜测是正确的，那么 v e c t o r vector vector 的底层结构如下：
注：finish 指向的是有效空间的下一个位置
1.2 模拟实现 vector 成员变量
我们模拟实现的 v e c t o r vector vector 的成员变量，也学习库中的形式
namespace my_vector{template<class T>class vector{public://···private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};} 这里，为了与库中的 v e c t o r vector vector 区别开，我们使用命名空间
同时，因为顺序表应满足不同数据类型的存储，我们实现的不是某个具体类型的类，而是类模板。既然是模板，那么函数的声明与定义就不能放在不同的文件中，因此声明和定义全在vector.h文件中，不再需要vector.cpp文件。
2 迭代器
因为 v e c t o r vector vector 的迭代器是一个原生指针，与 s t r i n g string string 类似，很简单，我们直接看代码
typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;} 因为 _ f i n i s h finish finish 本就就是只想最后一个有效数据的下一位，因此我们end()我们直接返回 _finish 即可
3 size、capacity、empty
这三个函数都很简单，我们直接看代码
size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty() const{return _start == _finish;}
4 opreator[ ]
v e c t o r vector vector 中的 o p r e a t o r opreator opreator[] 与 s t r i n g string string 中的 o p e r a t o r operator operator[] 类似，都是访问第 i i i 个数据的元素。同样， v e c t o r vector vector 的 o p e r a t o r operator operator[] 也要用 a s s e r t assert assert 断言来判断下标是否合法
T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}
这里顺便提一下， v e c t o r vector vector 还提供了 at 函数 接口。
a t at at 函数与 o p e r a t o operato operato[] 功能相同，但他们检查越界的方式不同
a t at at 函数是抛异常，而 o p e r a t o r operator operator[] 是断言
5 reserve
5.1 初版 reserve
void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;_finish = _start + size();_end_of_storage = _start + n;}}在 s t r i n g string string 中，我们已经模拟实现 r e s e r v e reserve reserve 了， v e c t o r vector vector 中也是需要我们手动释放和拷贝的数据的，代码细节就不再细讲了。
那上面代码有问题吗？
有的
5.2 _finish 的处理
首先是对 _ f i n i s h finish finish 的处理上
这里我们更新_finish的方式是_start + size()，可是 size() 是怎么计算出来的？是通过_finish - _start计算出的，可是此时 _ s t a r t start start已经更新了，而_ f i n i s h finish finish还未更新 ，此时他们相减会出大问题。
怎么解决呢？也很好办，那就是提前记录 s i z e size size() 的值
void reserve(size_t n){if (n > capacity()){//记下size()的值size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}}
5.3 深拷贝
还有一点，上述代码用 m e m c p y memcpy memcpy 拷贝是浅拷贝，而我们需要的是深拷贝
用 m e m c p y memcpy memcpy 拷贝有什么问题呢？
void test7(){vector<string> v1;v1.push_back("11111");v1.push_back("11111");v1.push_back("11111");v1.push_back("11111");print_container(v1);v1.push_back("11111");print_container(v1);}运行结果：
程序崩溃了！
为什么呢？问题出现在了扩容！
我们知道 v e c t o r vector vector< s t r i n g string string> 中，每个 s t r i n g string string 都指向一块堆空间。
虽然 v e c t o r vector vector 是深拷贝，但是 v e c t o r vector vector 中的每个 s t r i n g string string 都是浅拷贝，而每个string都指向一块资源。这意味着新开辟的 t m p tmp tmp 中，每个 string 都是与对应旧空间的 string 指向同一块空间， d e l e t e delete delete 后，会调用析构函数，将旧空间指向的资源全部释放掉，此时新空间的每个 s t r i n g string string 都是指向一块已经被释放的空间，自然会出现问题。
那如何解决呢？那就是对vector中的每个成员都进行深拷贝。我们不能再使用 m e m c p y memcpy memcpy，而是要自己赋值
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; ++i){_tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}} _tmp[i] = _start[i];是赋值，本质是调用自定义类型的赋值重载函数，实现了每个成员的深拷贝，而[ ]，则是前面实现的operator[]重载函数
5.4 终版
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; ++i){_tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}}
6 push_back 与 pop_back
p u s h push push_ b a c k back back 直接往尾部放数据即可，但要注意空间不够要扩容
void push_back(const T& x){if (_finish == _end_of_storage){size_t n = size() == 0 ? 4 : 2 * size();reserve(n);}*_finish = x;++_finish;}
p o p pop pop_ b a c k back back 也很简单，但要注意判断是否为空。
void pop_back(){assert(!empty());--_finish;}
7 打印函数
STL库 中， v e c t o r vector vector 是没有重载 o p e r a t o r operator operator<< 的。
为什么呢？因为库事先并不知道你要以什么形式打印：是连续打印，还是每打印一个数据就空格还是每打印一个就换行？而且自己实现一个打印函数并不困难。因此库就交给程序员自己实现。
7.1 初写打印
那么我们就自己实现一个打印函数吧。
打印函数是一个全局函数
template<class T>void print_vector(const vector<T>& v){vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;}但上述函数写的是有问题的
7.2 typename 关键字
为什么呢？
问题出现在vector<T>::const_iterator it;中
可以直接突破类域，用类名::方式去类中取东西，能取到两种：一种是 静态成员变量，另一种是在 类中 t y p e d e f typedef typedef 的类型。
C++规定：类模板没有被实例化之前，编译器是不会往里面去取东西的。
编译器走到 p r i n t print print_ v e c t o r vector vector 时， v e c t o r vector vector 模板还没被实例化出来。而因为不敢去模板中取，编译器不知道 c o n s t const const_ i t e r a t o r iterator iterator 是 类型 还是 静态成员变量，如果取到静态成员变量，后面还跟着变量 it 就会出大问题。因此编译器报错。
要解决上述问题，需在前面加上 t y p e n a m e typename typename 关键字。加上 t y p e n a m e typename typename，即明确告诉编译器 c o n s t const const_ i t e r a t o r iterator iterator 是类型。（可以看做编译器的甩锅。编译器：你说了是类型的啦，我给你过了，如果他是成员变量的话那也是你的问题，不怪我）
但如果是取静态成员变量，前面什么都不用加，因为如果真是静态成员变量，你不会像vector<T>::const_iterator it这样用的，直接就vector<T>::const_iterator;这样
template<class T>void print_vector(const vector<T>& v){//没有实例化的类模板里面取东西，编译器不能区分const_iterator是类型还是静态成员变量typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;} 这样就可以啦
当然，这还有一种更简单的方式，用 a u t o auto auto 就没有那么麻烦，因为 a u t o auto auto 直接是由v.begin()推导而来
template<class T>void print_vector(const vector<T>& v){auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;}
7.3 打印函数进阶
但上述打印函数，稍稍改进一下，就可以变成所有类型容器的打印函数，而不仅仅是 v e c t o r vector vector 类型的
template<class Container>void print_container(const Container& v){auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;} 需要注意的是判断条件while (it != v.end())只能是 !=，有些小伙伴可能会写while (it < v.end())。对于 s t r i n g string string 与 v e c t o vecto vector 来说是没问题，因为他们本来就是原生指针；但对其他容器就不行了，比例 l i s t list list 链表，它的 i t e r a t o r iterator iterator 是一个类，不存在比较大小的概念。
8 insert
8.1 insert 初版
void insert(iterator pos, const T& x){assert(pos >= begin() && pos <= end());if (_finish == _end_of_storage){size_t n = size() == 0 ? 4 : 2 * size();reserve(n);}iterator i = end();while (pos != i){*i = *(i - 1);--i;}*pos = x;++_finish;} 上述代码其实是有问题的
我们一起来看看
8.2 迭代器失效
8.2.1 情况一：类似野指针
上述代码其实是有问题的
我们先来测试一个不需要扩容的
void test1(){vector<int> v1;v1.reserve(10);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin() + 1, 10);print_vector(v1);}运行结果：
没有问题
那再来一个需要扩容的
void test1(){vector<int> v1;v1.reserve(4);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin() + 1, 10);print_vector(v1);}运行结果：
可以看到，报错了
为什么呢？这是因为 p o s pos pos 迭代器失效了
我们结合图来看就很容易看懂了。扩容后，pos 依然指向旧空间，此时旧空间已经被释放了， p o s pos pos 迭代器就是一个野指针，同时while (pos != i)判断语句永远也不会成立，造成死循环。
怎么办呢？我们应记录 pos 迭代器与 _start 的相对位置，再将 pos 映射到新空间中
void insert(iterator pos, const T& x){assert(pos >= begin() && pos <= end());if (_finish == _end_of_storage){size_t len = pos - _start;size_t n = size() == 0 ? 4 : 2 * size();reserve(n);pos = _start + len;}iterator i = end();while (pos != i){*i = *(i - 1);--i;}*pos = x;++_finish;}
8.2.2 algorithm 库中的查找函数
这里，介绍 a l g o r i t h m algorithm algorithm 库中的查找函数， f i n d find find 函数模板适用于所有的容器，只需要传一个迭代器区间给它，就能帮你查找
库中的 f i n d find find函数 是一个模板：
需要注意的是，传值要传左闭右开区间
8.2.3 情况二：insert 后再对 pos 进行访问
8.2.3.1 不扩容的情况
我们知道， i n s e r t insert insert 函数的 p o s pos pos 形参是一个迭代器，如果我们想在指定数据之前插入数据，就可以用 find 模板找到相应数据的迭代器
现在，我用 f i n d find find函数 找到 p p p 为 5 的位置，在之前插入数据 100，并将 5 ∗ * ∗ 10
void test2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);int x = 5;auto p = std::find(v1.begin(), v1.end(), x);if (p != v1.end()){v1.insert(p, 40);*(p) *= 10;}print_container(v1);}运行结果：
为什么是100 * 10 呢？
这是因为迭代器失效了，在 i n s e r t insert insert 以后，我们可以认为迭代器 p 就已经失效了。我们结合图来理解
用 i n s e r t insert insert 插入数据后， p p p 指向的位置已经变了。你以为它指向的还是 5，但实际上他已经变了
8.2.3.1 扩容的情况
上述情况还不是最恐怖的，最恐怖的是扩容的情况
void test3(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int x = 2;auto p = std::find(v1.begin(), v1.end(), x);if (p != v1.end()){v1.insert(p, 100);*(p) *= 10;}print_container(v1);}运行结果：
现在连100 都不乘10了，为什么呢？还是迭代器失效的问题，我们来看图
p o s pos pos 的位置还是指向旧空间，这时再对 p o s pos pos 访问，就是类似于野指针的访问。
8.2.4、解决方法
8.2.4.1、想法一
那应该怎么解决上述问题呢？
在解决完第一种情况的代码中，我们在函数内是对 p o s pos pos 进行了更新的
但是形参的改变并不影响实参，那我们可不可以用引用呢？
void insert(iterator& pos, const T& x) 这样， p o s pos pos 是引用，就能改变函数外的 p p p 了。
但这样是不行的，因为会影响传参
vector<int> v;v1.insert(v1.begin(), 10); 像这样，我们传递第一个迭代器，但这样传参，v1.begin()的返回值中间会产生一个临时变量，实际传递的就是这个临时变量。临时变量是常性，必须用 c o n s t const const 引用，普通的引用是传不进去的。
那如果我加 c o n s t const const 呢？
void insert(const iterator& pos, const T& x) 加了 c o n s t const const，里面的 p o s pos pos 就无法改变了，所以还是不行
8.2.4.2、想法二
我们来看一下库中的 i n s e r t insert insert 是怎么处理的
库中给了一个返回值，返回的是更新之后的 p o s pos pos。
iterator insert(iterator pos, const T& x){assert(pos >= begin() && pos <= end());if (_finish == _end_of_storage){size_t len = pos - _start;size_t n = size() == 0 ? 4 : 2 * size();reserve(n);pos = _start + len;}iterator i = end();while (pos != i){*i = *(i - 1);--i;}*pos = x;++_finish;return pos;}所以如果真要 i n s e r t insert insert 后继续访问 p p p，一定要更新 p p p 再访问
void test4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int x = 2;auto p = std::find(v1.begin(), v1.end(), x);if (p != v1.end()){ p = v1.insert(p, 100); *(p + 1) *= 10;}print_container(v1);}运行结果：
8.3 总结
用 i n s e r t insert insert 后，迭代器 p 就失效了，最好的办法就是不再用 p p p 去访问。如果非要访问，一定要更新一下迭代器 p p p 再去访问
9 erase
iterator erase(iterator pos){assert(pos < end() && pos >= begin());iterator i = pos;while (i != end() - 1){*(i) = *(i + 1);++i;}--_finish;return pos;} 同样， e r a s e erase erase 也存在迭代器失效的问题。我们使用的时候一定要注意！ e r a s e erase erase之后就不要再访问迭代器，一定要访问也要先更新再访问，更新后的迭代器指向要删除数据的下一个位置
10 resize
void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}r e s i z e resize resize 的功能与实现这里就不再过多解释，这里大家直接看代码即可。
这里我们重点讲一下 const T& val = T()的写法
这是自定义类型给缺省值的方法。因为 v e c t o r vector vector 是模板，给缺省值时不能再像 const T& val = 0 这样给，因为是模板，你不知道 T 是什么类型，像前面给 0 就表示 T 一定是 0 了，肯定是不合适的。T 可能是 i n t int int，可能是 d o u b l e double double、也可能是自定义类型。
如果是自定义类型的对象，我们就调用它的默认构造。上述给缺省值的方法就是给 T 的一个匿名对象并调用它的默认构造。
那如果 T 是内置类型： i n t int int、 d o u b l e double double怎么办？他们没有默认构造这一概念啊
在此之前，我们确实是认为默认函数是没有构造函数这一概念的，但是为了兼容像模板这样的场景，内置类型也有了构造函数的概念(还有析构函数的概念)。
void test5(){int i = int();int j(1);cout << i << endl;cout << j << endl;cout << int(2) << endl;}运行结果：
11 构造函数系列
11.1 默认构造
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){} 但实际上，并不需要这么麻烦，因为我们在成员变量声明时，结了缺省值，我们这样就可以了
vector() {} 学习类与对象时，我们知道：所有成员都会走初始化列表。如果我们没有显式写在初始化列表，对于内置类型：没有缺省值不做任何处理，但现在我们在成员变量声明时，结了缺省值，则用缺省值初始化。
在C++11中，给了一个方式可以 强制生成默认构造：
vector() = default; 因为编译器只有在程序员没有自己实现任何构造函数（拷贝构造也是构造）时才会生成默认构造，如果我们自己实现了带参的构造，又想编译器生成默认构造，就可以用上述语法
11.2 拷贝构造
vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}} 拷贝构造，就是遍历 对象 v v v，将 v v v 的值全部 p u s h push push_ b a c k back back 进 t h i s this this 中。这里范围for用了引用，是为了减少拷贝，而为了避免频繁的扩容，使用 r e s e r v e reserve reserve 提前开辟空间。
11.3 迭代器区间构造 与 n 个 value 构造
11.3.1 迭代器区间构造
在stl库中，还提供了一个构造方法：迭代器区间构造
这里讲一个新的知识点：类模板里面的成员函数可以是函数模板
为什么要用模板呢？这样不行吗？
vector(iterator first, iterator last) 如果是这样的话，那么迭代器构造只能用 v e c t o r vector vector 迭代器构造，如果是函数模板的话可以用任意的迭代器进行构造
代码如下：
template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}测试：
void test6(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);l1.push_back(6);vector<int> v1(++l1.begin(), --l1.end());print_vector(v1);}运行结果：
可见，迭代器区间可以用任意容器迭代器进行初始化，但它要求类型是匹配的
11.3.2 n 个value构造
n n n 个 v a l u e value value 的构造很简单，不断 p u s h push push_ b a c k back back 就行
vector(size_t n, const T& val = T()){reserve(n);while (n--){push_back(val);}}
11.3.3 注意事项
调用 n n n 个 v a l u e value value 的构造函数时，会出现一个很奇怪的报错
void test7(){vector<int> v(10, 1);print_vector(v);}
为什么我调用的时 n n n 个 v a l u e value value 的构造，结果报错报到迭代器区间的构造了呢？
这是因为编译器把vector<int> v(10, 1);中的 10 和 1 识别成两个迭代器了。
为什么会这样呢？编译器有一个原则，那就是匹配最匹配的
我们先来看 n n n 个 v a l u e value value 的构造
vector(size_t n, const T& val = T())对 10 和 1 来说，T 是 i n t int int 是确定的
但是 n n n 是 s i z e size size_ t t t， i n t int int 要进行类型转换
再看迭代器区间构造
vector(InputIterator first, InputIterator last)，它实例化出来是两个 i n t int int，不用类型转换，所以编译器选择迭代器区间构造
那怎么解决呢？
stl库中选择重载多个 n n n 个 v a l u e value value 的构造函数，让你永远有更好的选择
vector(size_t n, const T& value = T()) { reserve(n); while (n--) { push_back(value); } } vector(int n, const T& value = T()) { reserve(n); while (n--) { push_back(value); } } vector(long long n, const T& value = T()) { reserve(n); while (n--) { push_back(value); } }
12 赋值运算符重载
赋值运算符重载分为现代写法与传统写法，这在 s t r i n g string string 的模拟实现中讲过类似的，这里就不再细讲了，我们直接看代码
12.1 传统写法
void clear(){_finish = _start;}vector<T>& operator=(const vector<T>& v){clear();if (this != &v){reserve(v.capacity());const_iterator it = v.begin();while (it != v.end()){push_back(*it);++it;}}return *this;}
12.2 现代写法
void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}
注：类里面可以用类名替代类型，类外面不行
比如这样：用 类名vector 替代 类型vector<int>
void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector tmp){swap(tmp);return *this;} 不过并不推荐这种写法，因为对新手来说不友好。
13 源码
//vector.h#pragma once#include<iostream>#include<assert.h>#include<vector>namespace my_vector{ template<class T> class vector { public: // Vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() { return _start == _finish; } void clear() { _finish = _start; } vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} // C++11 前置生成默认构造vector() = default; vector(size_t n, const T& value = T()) { reserve(n); while (n--) { push_back(value); } } vector(int n, const T& value = T()) { reserve(n); while (n--) { push_back(value); } } vector(long long n, const T& value = T()) { reserve(n); while (n--) { push_back(value); } } vector(const vector<T>& v) { reserve(v.capacity()); const_iterator it = v.begin(); while (it != v.end()) { push_back(*it); it++; } } template<class InputIterator> vector(InputIterator first, InputIterator last) { InputIterator tmp = first; //不能是< , list那些就不行 while (tmp != last) { push_back(*tmp); tmp++; } } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } vector<T>& operator=(vector<T> tmp) { swap(tmp); return *this; } ~vector() { if(_start) { delete[] _start; _start = _finish = _end_of_storage; } } T& operator[](size_t n) { assert(n < size()); return *(_start + n); } const T& operator[](size_t n) const { assert(n < size()); return *(_start + n); } void reserve(size_t n); void push_back(const T& x); void resize(size_t n, const T& value = T()); void pop_back(); iterator insert(iterator pos, const T& x); iterator erase(iterator pos); private: iterator _start = nullptr; // 指向数据块的开始 iterator _finish = nullptr; // 指向有效数据的尾 iterator _end_of_storage = nullptr; // 指向存储容量的尾 }; template<class T> void vector<T>::push_back(const T& x) { if (size() == capacity()) { size_t new_capacity = capacity() ? 2 * capacity() : 4; reserve(new_capacity); } *_finish = x; _finish++; } template<class T> void vector<T>::reserve(size_t n) { if (n > capacity()) { iterator tmp = new T[n]; size_t preserve_size = size(); int m = 0; iterator it = begin(); while (it != end()) { *(tmp + m) = *it; ++m; ++it; } //memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; _start = tmp; _finish = _start + preserve_size; _end_of_storage = _start + n; } } template<class T> void vector<T>::resize(size_t n, const T& value) { if (n <= size()) { _finish = _start + n; } else { reserve(n); int m = n - size(); while (m--) { *_finish = value; ++_finish; } } } template<class T> void vector<T>::pop_back() { assert(!empty()); _finish; } / template<class T> typename vector<T>::iterator vector<T>::insert(typename vector<T>::iterator pos, const T& x) { assert(pos <= _finish && pos >= _start); /*if (size() == capacity()) { size_t new_capacity = capacity() ? 2 * capacity() : 4; reserve(new_capacity); }*/ //相对位置 if (size() == capacity()) { size_t len = pos - _start; reserve(capacity() ? 2 * capacity() : 4); pos = _start + len; } iterator it = end(); while (it > pos) { *it = *(it - 1); it--; } *pos = x; ++_finish; return pos; } template<class T> typename vector<T>::iterator vector<T>::erase(typename vector<T>::iterator pos) { assert(pos < end() && pos >= begin()); iterator it = pos + 1; while (it != end()) { *(it - 1) = *it; ++it; } --_finish; return pos; } template<class T> void print_vector(const vector<T>& v) { typename vector<T>::const_iterator it = v.begin(); while (it != v.end()) { std::cout << *it << " "; ++it; } std::cout << std::endl; } template<class Container> void print_container(const Container& v) { auto it = v.begin(); while (it != v.end()) { std::cout << *it << " "; ++it; } std::cout << std::endl; }}