目录

1. vector的基本框架

1.1 构造析构和容量

1.2 push_back，reserve和operator[ ]

2. vector的迭代器

2.1 四个基本迭代器

2.2 迭代器区间初始化

2.3 迭代器的分类

3. vector的其它接口函数

3.1 修改后的reserve

3.2 resize

3.3 pop_back

4.  insert和erase迭代器失效问题

4.1 insert

4.2 erase

5. vector 深拷贝

5.1 拷贝构造

5.2 赋值 operator=

6. 两道选择题

6.1 下面程序的输出结果正确的是( )

6.2 下面关于迭代器失效的描述哪个是错误的（ ）（多选）

完整代码：

vector.h

Test.c

本篇完。

---

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 reserve(size_t n){if (n > capacity){size_t sz = size();T* tmp = new T[n];if(_strat){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_strat = tmp;_finish = tmp + sz;_end_of_storage = tmp + n;}}

为了方便测试尾插的效果，我们先来实现一下 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）
<forward_list>         （C++11）
<unordered_map>  （C++11）
<unordered_set>    （C++11）

③ 双向迭代器：bidirectional_iterator
特点：满足以上功能，并且能 ++，还能 - -
<list>
<map>
<set>

④ 随机迭代器：randomaccess_iterator
特点：满足以上所有功能，能 ++ 能 - -，还能 + 和 -  
<vector>
<deque>

它们本质上是一个继承关系：下面是子类，上面是父类。

子类都是一个父类，因为它满足父类的所有特征。

也就是说，虽然在语法上它是个模板，允许你传任意类型的迭代器，

但是在更深层次上存在着更进一步的限制 ——

 它要求你传随机迭代器，你就不能用双向迭代器。因为只有随机迭代器才能满足随机迭代器的所有操作。换言之，你不能用功能比它指定的迭代器少的迭代器。（可以理解为权限的放大）

它要求你用双向迭代器，你就不能用单向迭代器，因为单项迭代器不能满足所有双向迭代器的操作。但是你可以用比它功能多的迭代器，比如随机迭代器，因为随机迭代器也能满足双向迭代器的操作。因为随机迭代器是双向迭代器的子类，它满足父类（双向迭代器）的所有功能。（可以理解为权限的缩小） 

我们弄明白了这些，我们再回到刚才提的问题 —为什么这里要叫 InputIterator？

首先，InputIterator 是输入迭代器，这么写是为了满足命名规范。

可以不用，我们可以传单向迭代器、双向迭代器，也可以传随机迭代器。

因为这些迭代器都满足输入迭代器的所有功能。
 

3. vector的其它接口函数

3.1 修改后的reserve

我们刚才实现了 reserve，reserve 搬元素的时候也是 memcpy去进行拷贝的，又让 push_back 复用了 reserve， 其实这里存在一个非常严重的问题！

现在给出一个测试用例：

	void Test3(){vector<string> v;      // 在vector里放stringv.push_back("1");v.push_back("2");v.push_back("3");v.push_back("4");v.push_back("5");v.push_back("6");v.push_back("7");v.push_back("8");v.push_back("9");for (const auto& e : v){cout << e << " ";}cout << endl;}

 这里发现程序崩掉了。

为什么会这样？原因在于我们在扩容和深拷贝时，用了一个 memcpy！

push_back 调用 reserve 扩容时就会出问题，根本原因是 memcpy 是浅拷贝。

问题分析：

memcpy 是内存的二进制格式拷贝，

将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。

如果拷贝的是自定义类型的元素，memcpy 既高效又不会出错，

但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，

就会出错，因为memcpy的拷贝实际是浅拷贝。

（这里新的三个指针还是指向原来的空间，然后原来的空间又被释放了）

所以：如果对象中涉及到资源管理时，不能使用 memcpy 进行对象之间的拷贝，我们手动去拷：

修改后的 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); 浅拷贝，不行for (size_t i = 0; i < sz; i++)// 如果T是int，一个一个拷贝没问题{tmp[i] = _start[i];// 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。}delete[] _start;}_start = tmp;_finish = tmp + sz;_end_of_storage = tmp + n;}}

 成功运行：

3.2 resize

 vector 的 resize 如果不给第二个参数，默认给的是其对应类型的缺省值作为 "填充值"。

由于这里我们不知道具体类型是什么，这里缺省值我们使用匿名对象 T() ，

此外因为匿名对象的生命周期仅在当前一行，这里必须要用 const 引用匿名对象，

可以理解为延长其生命周期：

		void resize(size_t n, const T& val = T()){if (n > capacity()){reserve(n);}if (n > size()){while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}

3.3 pop_back

pop_back 很简单，只需要 - -finish 就可以了。

 但是需要考虑删完的情况，我们这里采用暴力的处理方式 —— 断言。

		void pop_back() {assert(_finish > _start);--_finish;}

测试一下上面的函数：

	void Test3(){vector<string> v;      // 在vector里放stringv.push_back("1");v.push_back("2");v.push_back("3");v.push_back("4");v.push_back("5");v.push_back("6");v.push_back("7");v.push_back("8");v.push_back("9");for (const auto& e : v){cout << e << " ";}cout << endl;cout << v.size() << " " << v.capacity() << endl;v.resize(50,"x");cout << v.size() << " " << v.capacity() << endl;v.pop_back();v.pop_back();v.pop_back();for (const auto& e : v){cout << e << " ";}cout << endl;cout << v.size() << " " << v.capacity() << endl;}
}

4.  insert和erase迭代器失效问题

什么是迭代器失效？

" 迭代器失效是一种现象，由特定操作引发，这些特定操作对容器进行操作，使得迭代器不指向容器内的任何元素，或者使得迭代器指向的容器元素发生了改变。"

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，

或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T* 。

因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，

而使用一块已经被释放的空间，造成的后果是程序崩溃，

即，如果继续使用已经失效的迭代器，程序可能会出现崩溃。

4.1 insert

插入可分为四个步骤：① 检查 pos 是否越界   ② 检查是否需要扩容  ③ 移动数据   ④ 插入数据

		void insert(iterator pos, const T& val){assert(pos >= _start);// ①检查pos是否越界assert(pos <= _finish);if (_finish == _end_of_storage)// ②检查是否需要扩容{reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator right = _finish - 1;// ③移动数据while (right >= pos){*(right + 1) = *right;--right;}*pos = val;// ④插入数据++_finish;}

测试：在2的位置前插入一个20

	void Test4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);vector<int>::iterator pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()) {v1.insert(pos, 20);}for (const auto& e : v1){cout << e << " "; }cout << endl;}

 继续在2的位置前插入一个20：

    void Test4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);vector<int>::iterator pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()) {v1.insert(pos, 20);}for (const auto& e : v1){cout << e << " "; }cout << endl;pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()){v1.insert(pos, 20);}for (const auto& e : v1){cout << e << " "; }cout << endl;}

 是什么问题出现了随机值？机智的童鞋已经想到：

迭代器失效问题。扩容导致的 pos 失效，我们的 insert 没有去处理这个问题。

如果发生扩容，我们的 pos 是不是应该去更新一下？：

		void insert(interator pos, const T& val){assert(pos >= _start);// ①检查pos是否越界assert(pos <= _finish);if (_finish == _end_of_storage)// ②检查是否需要扩容{size_t len = pos - _start;// 记录一下pos到_start的距离reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos，}interator right = _finish - 1;// ③移动数据while (right >= pos){*(right + 1) = *right;--right;}*pos = val;// ④插入数据++_finish;}

但是外面的 pos（实参） 还是失效的，这里是传值，pos（形参） 是 pos（实参） 的临时拷贝。 

如果 insert 中发生了扩容，那么会导致 pos（实参）指向空间被释放。

pos（实参） 本身就是一个野指针，这种问题我们称之为 —— 迭代器失效 

如何解决这里的迭代器失效问题？传引用？

传引用当然时不好的，如果我传给你一个begin呢，传引用不能彻底解决所有问题。

我们来看看巨佬是如何解决这一问题的：

是通过返回值去拿的，返回新插入的迭代器。

如果迭代器失效了，你想拿另一个迭代器去代替，就可以通过返回值去拿一下：

		iterator insert(iterator pos, const T& val){assert(pos >= _start);// ①检查pos是否越界assert(pos <= _finish);if (_finish == _end_of_storage)// ②检查是否需要扩容{size_t len = pos - _start;// 记录一下pos到_start的距离reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos，//而且形参不会影响实参，传引用的话begin等就传不了，所以用返回解决}iterator right = _finish - 1;// ③移动数据while (right >= pos){*(right + 1) = *right;--right;}*pos = val;// ④插入数据++_finish;return pos;}

	void Test4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);vector<int>::iterator pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()) {v1.insert(pos, 20);}for (const auto& e : v1){cout << e << " "; }cout << endl;pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()){v1.insert(pos, 20);}for (const auto& e : v1){cout << e << " "; }cout << endl;}

4.2 erase

erase代码比insert简单，就是挪动数据，是这样写吗？：

		void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个iterator left = pos + 1;while (left < _finish){*(left - 1) = *left;++left;}--_finish;}

erase 有没有迭代器失效的问题？

删除会导致 pos 失效吗？

我们用三种场景去测试：①  1 2 3 4 5  （正常，是个巧合）

	void Test4_erase(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数while (pos != v1.end()) {if (*pos % 2 == 0) {v1.erase(pos);}pos++;}for (auto e : v1) {cout << e << " ";}cout << endl;}

②  1 2 3 4  （崩溃）

	void Test4_erase(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//v1.push_back(5);vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数while (pos != v1.end()) {if (*pos % 2 == 0) {v1.erase(pos);}pos++;}for (auto e : v1) {cout << e << " ";}cout << endl;}

 ③  1 2 4 5  （结果不对，没删除完）

	void Test4_erase(){vector<int> v1;v1.push_back(1);v1.push_back(2);//v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数while (pos != v1.end()) {if (*pos % 2 == 0) {v1.erase(pos);}pos++;}for (auto e : v1) {cout << e << " ";}cout << endl;}

 erase(pos) 以后，pos 指向的意义已经变了，直接 pos++ 可能会导致一些意料之外的结果。

对于情况 ③：比如连续的偶数，导致后一个偶数没有判断，导致没有删掉。

再其次，erase 的删除有些 vector 版本的实现，不排除它会缩容。

			//if (size() < capacity()/2)//{//	// 缩容 -- 以时间换空间（虽然基本不会这么用了）//}

如果是这样，erase(pos) 以后，pos 也可能会是野指针，跟 insert 类似。

（SGI 和 PJ 版本 vector 都不会缩容）

对于情况 ②：如果最后一个数据是偶数，会导致 erase 以后，pos 意义变了。

再 ++ 一下，导致 pos 和 end 错过结束判断，出现越界问题。

而情况 ①： 之所以没有翻车，是因为被删除的偶数后面恰巧跟的是奇数，运气好逃过了一劫。

导致上述三种问题的本质：erase(pos) 以后，pos 的意义变了，再去 pos++ 是不对的。

为了解决这个问题，erase 是这么说明的：

规定erase返回删除位置下一个位置迭代器，改进 erase：

		iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个iterator left = pos + 1;while (left < _finish){*(left - 1) = *left;++left;}--_finish;return pos;//此时pos就是删除位置下一个位置迭代器}

简单测一下第三个情况：（第二个情况也成功了）

	void Test4_erase(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数while (pos != v1.end()) {if (*pos % 2 == 0) {pos = v1.erase(pos);}else{pos++;}}for (auto e : v1) {cout << e << " ";}cout << endl;}

对于 vector 可能会导致其迭代器失效的操作有：

① 会引起其底层空间改变的操作，都有可能存在迭代器失效。

比如：resize、reverse、insert、assign、push_back 等。

② 指定位置元素的删除操作：erase

erase 删除 pos 位置元素后，pos 位置之后的元素就会往前搬移，

没有导致底层空间的改变，理论上讲迭代器不应该会失效。

但是 pos 刚好是最后一个元素，删完之后 pos 刚好在 end 的位置，

而 end 位置是没有元素的，那么 pos 就失效了。

因此删除 vector 中任意位置元素时，VS 就认为该位置迭代器失效了。

还有就是我们刚才讲解的奇偶数，删除 pos 位置的数据，导致 pos 迭代器失效。

当然，vector 迭代器的失效主要发生在 insert 和 erase。vector 的其他接口基本不碰迭代器，自然也就不涉及这些问题。

迭代器失效解决方法：在使用前，对迭代器重新赋值即可。

 string 的 insert 和 erase 迭代器是否会失效？string 有没有迭代器失效？

当然会，只要使用迭代器的容器，都可能会涉及迭代器失效。

只是 string 一般很少涉及迭代器失效，因为它 insert 和 erase 时主要用下标。

5. vector 深拷贝

5.1 拷贝构造

可以使用传统写法，也可以使用现代写法，看看传统写法：全都自己干，

		vector(const vector<T>& v){reserve(v.capacity());for (const auto& e : v){push_back(e);}}

老老实实开空间，老老实实拷数据。

因为我们已经实现好了 reserve，所以我们这里可以直接调用 reserve 去开空间。

注意这里不能使用 memcpy，这个我们前面已经强调过了。

现代写法：找工具人帮忙干活：— 让迭代器区间当工具人：

		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(const vector<T>& v)// 现代写法:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}

有感觉现代写法比传统写法难？还要写swap和迭代器区间初始化？

但是这两个接口本来就是vector里面的，只是顺便实现了现代写法，简单测下： 

	void Tess5() {vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2(v1);for (const auto& e : v2){cout << e << " ";}cout << endl;}

5.2 赋值 operator=

传统写法就是把 v2 赋值给 v1，自己把 v1 释放了，再去深拷贝出 v2 一样大的空间……

太麻烦了，直接用现代写法，只要有了拷贝构造，赋值都可以用现代写法。

并且，这里还可以利用 "传参调用拷贝构造" 这一特性，做到真正的 "压榨" 工具人。

所以我们去掉 const 和引用传参，为的是让形参去充当临时变量 tmp ——

		vector<T>& operator=(vector<T> v)// 现代写法{swap(v);return *this;}

想要 v1 跟 v3 有一样大的空间一样大的值，我们让传参的时候就顺便把这件事给办了。

现在 v 手上就有 v3 了，然后再用 swap 函数夺取 v 的劳动成果，最后返回 *this 就大功告成了。

这里 v1 不仅把 v 从 v3 得到的东西，还让 v 帮忙把垃圾丢了（释放空间） ——

简单测下：

		vector<T>& operator=(vector<T> v)// 现代写法{swap(v);return *this;}

6. 两道选择题

6.1 下面程序的输出结果正确的是( )

#include <iostream>
#include <vector>
using namespace std;int main()
{int ar[] = { 1,2,3,4,0,5,6,7,8,9 };int n = sizeof(ar) / sizeof(int);vector<int> v(ar, ar + n);vector<int>::iterator it = v.begin();while (it != v.end()){if (*it != 0)cout << *it;elsev.erase(it);it++;}return 0;
}

A.程序运行崩溃

B.1 2 3 4 5 0 6 7 8 9

C.1 2 3 4 5 6 7 8 9

D.1 2 3 4 6 7 8 9

6.2 下面关于迭代器失效的描述哪个是错误的（ ）（多选）

A.vector的插入操作一定会导致迭代器失效

B.vector的插入操作有可能不会导致迭代器失效

C.vector的删除操作只会导致指向被删除元素及后面的迭代器失效

D.vector的删除操作只会导致指向被删除元素的迭代器失效

答案：

6.1 A

分析:当迭代器的值为0时，此时会进行删除，删除后如果迭代器不重新赋值，会导致原来的迭代器失效，此时针对一个已经失效的迭代器在进行++,会导致程序崩溃>

6.2 AD

A.vector的插入操作如果导致底层空间重新开辟，则迭代器就会失效。如果空间足够，不扩容时，迭代器不一定失效，比如push_back尾插，元素插入到空间末尾，在不扩容时不会对迭代器产生影响

B.参考A的解释。

C.vector删除，当前元素肯定失效，后面元素会牵扯到移动数据，因此删除元素后面的迭代器也会失效

D. vector的删除操作不光会导致指向被删除元素的迭代器失效，删除元素后面的迭代器也会失效

完整代码：

vector.h

#pragma once#include<iostream>
#include<assert.h>
#include<string>
using namespace std;namespace rtx
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_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;insert(end(), x);}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); //浅拷贝，不行for (size_t i = 0; i < sz; i++)// 如果T是int，一个一个拷贝没问题{tmp[i] = _start[i];// 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。}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);}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}template<class InputInterator>vector(InputInterator first, InputInterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}void resize(size_t n, const T& val = T()){if (n > capacity()){reserve(n);}if (n > size()){while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}void pop_back() {assert(_finish > _start);--_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start);// ①检查pos是否越界assert(pos <= _finish);if (_finish == _end_of_storage)// ②检查是否需要扩容{size_t len = pos - _start;// 记录一下pos到_start的距离reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos，//而且形参不会影响实参，传引用的话begin等就传不了，所以用返回解决}iterator right = _finish - 1;// ③移动数据while (right >= pos){*(right + 1) = *right;--right;}*pos = val;// ④插入数据++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个iterator left = pos + 1;while (left < _finish){*(left - 1) = *left;++left;}--_finish;return pos;//此时pos就是删除位置下一个位置迭代器}//vector(const vector<T>& v)// 传统写法//{//	reserve(v.capacity());//	// memcpy(_start, v._start, v.size() * sizeof(T));  // 会翻车//	for (const auto& e : v)//	{//		push_back(e);//	}//}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(const vector<T>& v)// 现代写法:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}vector<T>& operator=(vector<T> v)// 现代写法{swap(v);return *this;}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;}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;}void Test3(){vector<string> v;      // 在vector里放stringv.push_back("1");v.push_back("2");v.push_back("3");v.push_back("4");v.push_back("5");v.push_back("6");v.push_back("7");v.push_back("8");v.push_back("9");for (const auto& e : v){cout << e << " ";}cout << endl;cout << v.size() << " " << v.capacity() << endl;v.resize(50,"x");cout << v.size() << " " << v.capacity() << endl;v.pop_back();v.pop_back();v.pop_back();for (const auto& e : v){cout << e << " ";}cout << endl;cout << v.size() << " " << v.capacity() << endl;}void Test4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);vector<int>::iterator pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()) {v1.insert(pos, 20);}for (const auto& e : v1){cout << e << " "; }cout << endl;pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()){v1.insert(pos, 20);}for (const auto& e : v1){cout << e << " "; }cout << endl;}void Test4_erase(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数while (pos != v1.end()) {if (*pos % 2 == 0) {pos = v1.erase(pos);}else{pos++;}}for (auto e : v1) {cout << e << " ";}cout << endl;}void Tess5() {vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2(v1);for (const auto& e : v2){cout << e << " ";}cout << endl;vector<int> v3;v3 = v2;for (auto e : v2){cout << e << " ";}cout << endl;}
}int main()
{rtx::Tess5();return 0;
}

本篇完。

下一部分：list的接口函数介绍，list模拟实现，再后面就是栈和队列。