vector 的模拟实现

1. vector 的核心框架

2. size 和 capacity 以及 empty

3. reserve 和 push_back

4. insert

5. erase

6. copy constructor

6.1. 第一个版本

6.2. 第二个版本

6.3. 第三个版本

7. operator=

7.1. 第一个版本

7.2. 第二个版本

7.3. 第三个版本

8. constructor

8.1. 无参构造 - default

8.2. 用n个val构造 - fill

8.3. 利用一段区间构造 - range

9. resize

10. 关于vector使用memcpy()拷贝的问题

11. vector的模拟实现整体代码

12. vector 的练习题

12.1. 第一题

12.2. 第二题

12.3. 第三题

12.4. 第四题

1. vector 的核心框架

template<class T>
class vector
{
public:
	typedef T* iterator;
	//...
private:
	iterator _start;
	iterator _finish;
	iterator _end_of_storage;
};

vector 的底层分布：

2. size 和 capacity 以及 empty

这三个函数的实现非常简单，就放到一起了。

size 实现如下：

size_t size()
{
	return _finish - _start;
}

const size_t size() const 
{
	return _finish - _start;
}

capacity 实现如下：

size_t capacity()
{
	return _end_of_storage - _start;
}

const size_t capacity() const
{
	return _end_of_storage - _start;
}

empty() 实现如下：

const bool empty() const
{
	return _start == _finish;
}

3. reserve 和 push_back

reserve 实现如下 (此实现有问题，分析后，有正确实现)：

void reserve(size_t n) 
{
	// 只考虑扩容, 不考虑缩容.
    // 扩容有两种情况, a. 空vector；b. 非空vector(需要拷贝数据)
	if (n > capacity())
	{
		// 1. 开新空间
		T* tmp = new T[n];
		// 2. 拷贝数据
		if (!empty())
		{	
			for (size_t i = 0; i < size(); ++i)
			{
				tmp[i] = _start[i];
			}
		}
		// 3. 释放旧空间
		delete[] _start;
        // 4. 更新
		_start = tmp;
		_finish = _start + size();
		_end_of_storage = _start + n;
	}
}

push_back 实现如下：

void push_back(const T& val)
{
	// 1. 检查容量
	if (_end_of_storage == _finish)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
    // 2. 添加元素
	*_finish = val;
    // 3. 更新 _finish
	++_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);
}

测试代码如下：

void Test1(void)
{
	Xq::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)
	{
		std::cout << v[i] << " ";
	}
}

但是我们运行代码时，进程崩溃了，如下：

遇到问题，可以选择调试：

我们发现问题了，size() 的结果出现问题了，我们的size() 是如何实现的呢？

const size_t size() const
{
	return _finish - _start;
}

那么 _finish = _start + size()；执行之前，_start 已经发生了改变 (因为是开辟新空间，此时的 _finish 和 _start 就不是一段连续的空间两个地址了，相减就失去意义了) ，即原因出现在 _start 提前发生了改变；因此我们的解决方案是：

void reserve(size_t n) 
{
	//只考虑扩容，不考虑缩容，扩容有两种情况，a.空表；b.非空表(需要拷贝数据)
	if (n > capacity())
	{
		// 1. 开新空间
		T* tmp = new T[n];
		// 2. 拷贝数据
		if (!empty())
		{	
			for (size_t i = 0; i < size(); ++i)
			{
				tmp[i] = _start[i];
			}
		}
		// 3. 释放旧空间
		delete[] _start;
        // a. 第一种方案
        // 调换_finish和_start的顺序，但因为它是依赖顺序的，有局限性；
        // _finish = _tmp + size();
		// _start = tmp;
		// _end_of_storage = _start + n;
    
        // b.更好的是第二种方案:
        // 提前算好size()，避免了_start更新影响了size()的结果
        size_t sz = size();
        _start = tmp;
        _finish = tmp + sz;
        _end_of_storage = tmp + n;
	}
}

4. insert

void insert(iterator pos, const T& val)
{

	// 1. 检查pos的合法性
	assert(pos >= _start && pos <= _finish);
	// 2. 检查容量
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
    // 3. 移动数据
	iterator end = _finish;
	while (end > pos)
	{
		*end = *(end - 1);
		--end;
	}
    // 4. 插入数据
	*end = val;
    // 5. 更新 _finish
	++_finish;
}

测试如下：

void Test3(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.insert((v.begin() + 1), 10);
	for (auto e : v)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}

现象如下：

1 10 2 3

此时结果是正确的。但是我在更改一下测试代码 (多插入一个数据) ，这个进程就会crash

void Test3(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);   // 多插了一个数据
	v.insert((v.begin() + 1), 10);
	for (auto e : v)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}

现象如下：

为什么有这样的情况呢？一会儿正常插入，一会儿进程 crash，我们对比上面的两种情况：

其差异就在于第一种情况没有发生扩容，正常运行，第二种情况发生了扩容，导致进程直接挂掉；遇到这种情况，我们进行调试；

扩容之前的信息：

扩容之后的信息：

经过对比我们得知，造成这种问题的愿意就是因为发生扩容后，_start、_finish、_end_of_storage的值发生了改变 (因为是新空间)，而pos还是在扩容之前的位置上，那么接下来的while循环也就没有意义了，进程崩溃也就可以理解了；因此，我们的解决方案就是当发生扩容时，更新 pos：

void insert(iterator pos, const T& val)
{

	// 1. 检查pos的合法性
	assert(pos >= _start && pos <= _finish);
	// 2. 检查容量
	if (_finish == _end_of_storage)
	{
		// 3. 提前算好pos的位置
		size_t n = pos - _start;  
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		// 4. 更新 pos
		pos = _start + n;
	}
    // 5. 移动数据
	iterator end = _finish;
	while (end > pos)
	{
		*end = *(end - 1);
		--end;
	}
    // 6. 赋值
	*end = val;
    // 7. 更新
	++_finish;
}

此时再调用，得到运行结果：

1 10 2 3 4

但是这样真的就没有问题了吗？我们再更改一下测试用例：

void Test4(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	Xq::vector<int>::iterator pos = std::find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		std::cout << *pos << std::endl;
		v.insert(pos, 100);
		for (auto e : v)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
		std::cout << *pos << std::endl;
	}
}

运行结果：

3
1 2 100 3 4
-572662307

其实我们现在也能理解，造成这种结果的原因就是因为 pos 没有更新即 pos 失效了，哎，你不是在 insert() 里面更新了pos吗，为啥这又没更新呢？

原因是因为这是值传递，形参的改变不影响实参，因此在这里的 pos 依旧是失效的(当发生扩容时)，因此我们得出的结论就是当插入了数据，不要再访问这个pos了，因为我们不能万无一失确保pos的有效性；那有人又说了，那如果我传引用呢？我就可以更新pos了，如下：

void insert(iterator& pos, const T& val)
{

	// 1. 检查pos的合法性
	assert(pos >= _start && pos <= _finish);
	// 2. 检查容量
	if (_finish == _end_of_storage)
	{
		// 3. 提前算好pos的位置
		size_t n = pos - _start;  
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		// 4. 更新 pos
		pos = _start + n;
	}
    // 5. 移动数据
	iterator end = _finish;
	while (end > pos)
	{
		*end = *(end - 1);
		--end;
	}
    // 6. 赋值
	*end = val;
    // 7. 更新
	++_finish;
}

运行结果：

3
1 2 100 3 4
100

诶，好像可以，但是这会带来新的问题，例如我有时候想这样用insert()；

v.insert(v.begin(), 100);

但是此时编译会不通过，因为v.begin()是一个函数调用：

iterator begin()
{
	return _start;
}

它是一个传值返回的函数调用，函数返回会生成一个临时变量，临时变量具有常性，传递给 iterator& pos属于权限的放大，因此编译报错。

那有人又说改成const_iterator& pos不就行了吗，可是如果你是一个 const 对象你又如何修改呢？因此对于上面的insert的实现，insert 后就不要再访问这个pos了。

如果用户一定要访问这个pos呢？可以通过这个返回值来实现。

void Test7(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	Xq::vector<int>::iterator pos = v.begin();
	while (pos != v.end())
	{
		if (*pos % 2 == 0)
        {
            v.insert(pos, 20);
        }
		++pos;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

现象如下：

进程直接崩溃了，现在我们可以理解了，首先这里是因为扩容会导致 pos 失效，因此我们需要通过返回值来更新pos，insert 实现如下：

iterator insert(iterator pos, const T& val)
{

	// 1. 检查pos的合法性
	assert(pos >= _start && pos <= _finish);
	// 2. 检查容量
	if (_finish == _end_of_storage)
	{
		// 提前算好pos的位置
		size_t n = pos - _start;  
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		// 更新 pos
		pos = _start + n;
	}
	iterator end = _finish;
	while (end > pos)
	{
		*end = *(end - 1);
		--end;
	}
	*end = val;
	++_finish;
    // 返回插入数据的迭代器
	return pos;
}

测试用力如下：

void Test7(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	Xq::vector<int>::iterator pos = v.begin();
	while (pos != v.end())
	{
		if (*pos % 2 == 0)
            v.insert(pos, 20);
        else	
    	    ++pos;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

但是此时进程还是会挂掉，那是因为插入的时候返回的是插入数据的迭代器，此时会一直循环插入，进程会挂掉；因此需要插入后跳过两个数据(一个是已经判断的数据，一个是插入的数据)；即：

void Test7(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	Xq::vector<int>::iterator pos = v.begin();
	while (pos != v.end())
	{
		if (*pos % 2 == 0)
		{
            //更新pos
			pos = v.insert(pos, 20);
            //跳过两个数据
            pos += 2;
		}
		else
		{
			++pos;
		}
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果如下：

1 20 2 3 20 4

5. erase

void erase(iterator pos)
{
	//1. 确保pos的有效性
	assert(pos >= _start && pos < _finish);
	//2. 确保非空表
	assert(!empty());
	iterator begin = pos;
	while (begin < _finish - 1)
	{
		*begin = *(begin + 1);
		++begin;
	}
	--_finish;
}

测试用例如下：

void Test5(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.erase(v.begin());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.erase(v.begin());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果如下：

1 2 3 4
2 3 4
3 4

在这种情况下的实现，是没有迭代器失效的问题，因为没有涉及到空间的变化；但是我们不能确保所有的实现都没有涉及到空间的变化，如果有些实现当删除一定的数据会缩容，那么就会导致迭代器的失效的问题；

接下来有一个有意思的问题：删除所有的偶数：

测试用例一如下：

void Test6(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	Xq::vector<int>::iterator pos = v.begin();
	while (pos != v.end())
	{
		if (*pos % 2 == 0)
			v.erase(pos);
		++pos;
	}
	for (auto e : v)
		cout << e << " ";
	cout << endl;
}

结果：

1 3 5

结果正确

测试用例二如下：

void Test6(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	Xq::vector<int>::iterator pos = v.begin();
	while (pos != v.end())
	{
		if (*pos % 2 == 0)
			v.erase(pos);
		++pos;
	}
	for (auto e : v)
		cout << e << " ";
	cout << endl;
}

现象如下：

进程崩溃。

测试用例三如下：

void Test6(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(6);
	v.push_back(5);
	Xq::vector<int>::iterator pos = v.begin();
	while (pos != v.end())
	{
		if (*pos % 2 == 0)
			v.erase(pos);
		++pos;
	}
	for (auto e : v)
		cout << e << " ";
	cout << endl;
}

结果如下：

1 3 6 5

虽然进程没有崩溃，但是结果错误。

咋回事，怎么得出的结果千奇百怪的，我们通过下图来分析一下：

对于这三种情况：g++和vs的处理方式不一样，g++和上面一样，vs每个都会报错，vs会强制检查，只要erase()后，它就不让你++了；SLT只是一个规范，不同的版本实现是不同的；

因此这里的解决方案就是利用返回值更新pos，实现如下：

// STL 规定 erase()返回删除位置的下一个位置的迭代器
// 返回删除后元素的下一个元素的位置
// 即便此时有些实现缩容也会符合需求
iterator erase(iterator pos)
{
	//1. 确保pos的有效性
	assert(pos >= _start && pos < _finish);
	//2. 确保非空表
	assert(!empty());
	iterator begin = pos;
	size_t n = pos - _start;
	while (begin < _finish - 1)
	{
		*begin = *(begin + 1);
		++begin;
	}
	--_finish;
	pos = _start + n;
	return pos;
}

测试代码如下：

void Test6(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	Xq::vector<int>::iterator pos = v.begin();
	while (pos != v.end())
	{
        //更新pos
		if (*pos % 2 == 0)
			pos = v.erase(pos);
		else
			++pos;
	}
	for (auto e : v)
		cout << e << " ";
	cout << endl;
}

结果：

1 3

这样在g++(SGI STL)和vs(PJ STL)都可以正常通过；

在这里有一个结论：insert()和erase() 的pos位置，不要直接访问pos，一定要更新pos，如果直接访问可能会带来很多问题；这就是迭代器的失效问题；可以简单地理解，只要insert和erase我们都认为pos失效了，不要访问pos；

6. copy constructor

对于一个类来说，如果这个类没有显式定义copy constructor，编译器会自动生成一份，自动生成的copy constructor对内置类型处理(以值拷贝方式进行处理)，对自定义类型会去调用它的copy constructor；但是对于某些类来说，编译器默认生成的拷贝构造是不符合需求的；例如：

void Test8(void)
{
	Xq::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	Xq::vector<int> copy(v);
	for (auto e : v)
		cout << e << " ";
	cout << endl;
	for (auto e : copy)
		cout << e << " ";
	cout << endl;
}

在这里调用的是编译器默认生成的拷贝构造，现象如下：

原因是因为当这两个对象生命周期结束时，会调用析构函数，清理对象中的资源，在这里同一空间被析构两次，进程crash；不仅存在这个问题，如果其中一个对象发生修改，另一个对象也会发生改变，这显然是不符合需求的，因此在这里我们必须自己以深拷贝的方式实现对应的copy constructor：

6.1. 第一个版本

vector(const vector<T>& copy)
{
	// 1. 开空间
	_start = new T[copy.capacity()];
	// 2. 拷贝数据
	for (size_t i = 0; i < copy.size(); ++i)
		_start[i] = copy[i];
	// 3. 更新值
	_finish = _start + copy.size();
	_end_of_storage = _start + copy.capacity();
}

6.2. 第二个版本

vector(const vector<T>& copy)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	// 1. 开空间
	reserve(copy.capacity());
	// 2. 复用push_back()，更新数据
	for (const auto& e : copy)
		push_back(e);
}

6.3. 第三个版本

//第三种写法：依赖于一个构造函数
void swap(vector<T>& tmp)
{
	std::swap(_start, tmp._start);
	std::swap(_finish, tmp._finish);
	std::swap(_end_of_storage, tmp._end_of_storage);
}

template <class InputIterator>
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first != last)
	{
		//复用push_back，更新数据
		push_back(*first);
		++first;
	}
}

vector(const vector<T>& copy)
    //这里需要初始化，因为交换后的tmp需要调用析构，不能对未知空间进行delete，结果不明确
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	//利用迭代器区间构造一个临时对象
	vector<T> tmp(copy.begin(), copy.end());
    //交换this和tmp这个临时对象
	swap(tmp);
}

7. operator=

对于赋值运算符重载，我们不显式定义，编译器会显示生成一份，它对内置类型会处理(以值拷贝的方式)，对自定义类型同样会处理(调用自定义类型的operator=)；但是它也面临着和copy constructor 一样的问题，对于一些类来说编译器默认生成的operator= 是不符合需求的，因此我们的解决方案就是自己以深拷贝的方式实现operator=：

7.1. 第一个版本

vector<T>& operator=(const vector<T>& copy)
{
	// 1. 检测是否给自己赋值
	if (this != &copy)
	{
		// 2. 开新空间
		T* tmp = new T[copy.capacity()];
		// 3. 拷贝数据
		for (size_t i = 0; i < copy.size(); ++i)
			tmp[i] = copy[i];
		// 4.释放旧空间
		delete[] _start;
		// 5. 更新数据
		_start = tmp;
		_finish = tmp + copy.size();
		_end_of_storage = tmp + copy.capacity();
	}
    // 返回对象
	return *this;
}

7.2. 第二个版本

void swap(vector<T>& tmp)
{
	std::swap(_start, tmp._start);
	std::swap(_finish, tmp._finish);
	std::swap(_end_of_storage, tmp._end_of_storage);
}

vector<T>& operator=(const vector<T>& copy)
{
	if (this != &copy)
	{
		//创建一个临时对象
		vector<T> tmp(copy.begin(), copy.end());
		//直接交换
		swap(tmp);
	}
	return *this;
}

7.3. 第三个版本

void swap(vector<T>& tmp)
{
	std::swap(_start, tmp._start);
	std::swap(_finish, tmp._finish);
	std::swap(_end_of_storage, tmp._end_of_storage);
}
//利用传值传参会拷贝构造的性质
vector<T>& operator=(vector<T> tmp)
{
	swap(tmp);
	return *this;
}

8. constructor

一般的类都是需要显示提供默认构造函数的：

8.1. 无参构造 - default

// default
vector() 
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{}

8.2. 用n个val构造 - fill

// fill
// 用T的匿名对象给val缺省值
vector(size_t n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	//1. 预先开好空间
	reserve(n);
	//2. 插入数据
	for (size_t i = 0; i < n; ++i)
		push_back(val);
}

8.3. 利用一段区间构造 - range

// 利用一段区间构造  range
template <class InputIterator>
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first != last)
	{
		//复用push_back，更新数据
		push_back(*first);
		++first;
	}
}

但是这里存在一个问题：

void Test10(void)
{
	Xq::vector<int> v(10);
	for (auto e : v)
		cout << e << " ";
	cout << endl;
}

结果：

0 0 0 0 0 0 0 0 0 0

正常运行，可是改一下代码，问题就出来了：

void Test10(void)
{
	Xq::vector<int> v(10,1);
	for (auto e : v)
		cout << e << " ";
	cout << endl;
}

现象如下：

出现这种情况的原因是因为编译器认为这Xq::vector<int> v(10,1)与fill这个构造函数不是最匹配的，它认为与range这个构造函数是最匹配的；。

对一个int类型数据解引用自然会报错；

那如何解决这个问题呢？

第一种解决方案：把size_t 改成int，如下：

//  用n个val构造  fill
// 用T的匿名对象给val缺省值
vector(int n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	//1. 预先开好空间
	reserve(n);
	//2. 插入数据
	for (int i = 0; i < n; ++i)
		push_back(val);
}

结果：

1 1 1 1 1 1 1 1 1 1

正常运行，但是这有点不太好，因为STL标准库里面用的是size_t，那如果就想用size_t，那如何解决这个问题呢？其实非常简单，利用函数重载解决这个问题，如下：

//利用参数类型不同可以构成函数重载
vector(int n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	//1. 预先开好空间
	reserve(n);
	//2. 插入数据
	for (int i = 0; i < n; ++i)
		push_back(val);
}

vector(size_t n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	//1. 预先开好空间
	reserve(n);
	//2. 插入数据
	for (size_t i = 0; i < n; ++i)
		push_back(val);
}

结果：

1 1 1 1 1 1 1 1 1 1

也是正常运行。

9. resize

resize 和 reserve 的区别就是：reserve只影响空间，resize是空间 + 初始化数据。

resize 的实现如下：

void resize(size_t n, const T& val = T())
{    
    // 扩容
	if (n > capacity())
	{
		// 开空间
		reserve(n);
	}		
    // 复用 push_back 即可
	if (n > size())
	{
		// 插入数据
		size_t count = n - size();
		while (count--)
			push_back(val);
	}
    // 不用更改数据，直接更改_finish即可
	else
	{	
		_finish = _start + n;
	}
}

10. 关于vector使用memcpy()拷贝的问题

我们在模拟实现vector的时候，第一次写拷贝构造有可能是这样写的：

//v(copy)
vector(const vector<T>& copy)
{
	//1. 开空间
	_start = new T[copy.capacity()];
	//2. 拷贝数据
	memcpy(_start,copy._start,sizeof(T)* copy.size());
	//3. 更新值
	_finish = _start + copy.size();
	_end_of_storage = _start + copy.capacity();
}

这样的拷贝构造有些情况下的确可以正常运行，但有些情况进程会直接怪掉，我们做过vector的一个练习题，叫杨辉三角，其代码如下：

class Solution {
public:
	void generate(size_t numRows)
	{
		Xq::vector<Xq::vector<int>> vv;
		vv.resize(numRows, Xq::vector<int>());
		//初始化工作
		for (size_t i = 0; i < numRows; ++i)
		{
			vv[i].resize(i + 1, 0);
			vv[i].front() = vv[i].back() = 1;
		}
		//修改值
		for (size_t i = 2; i < numRows; ++i)
		{
			for (size_t j = 1; j < vv[i].size() - 1; ++j)
			{
				if (vv[i][j] == 0)
				{
					// 2 1        1 1           1 0
					vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
				}
			}
		}
		for (size_t i = 0; i < 5; ++i)
		{
			for (size_t j = 0; j < vv[i].size(); ++j)
			{
				cout << vv[i][j] << " ";
			}
			cout << endl;
		}
		//调用拷贝构造
		Xq::vector<Xq::vector<int>> ret = vv;
	}
};

测试现象如下：

当我们运行时，发现函数调用完后 (在析构对象时) ，进程崩溃了；

函数调用完毕，潜台词就是这两个对象的生命周期结束，就会调用析构函数，在析构时崩溃，很可能出现了非法访问(在这里就是同一空间被析构两次)等问题；

可是我的copy constructor就是以深拷贝的方式实现的啊，为什么在这里会出现同一空间被析构两次的问题呢？

首先我们要明确的是memcpy是一种很简单的拷贝，memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中(浅拷贝)；那在这里会是memcpy()的问题吗？遇到这种情况，调试：

拷贝构造前：

拷贝构造后：

可以发现， vv 的每一个元素 (vector<int>) 是浅拷贝，当它们进行析构时，一个空间被析构两次，就会导致进程挂掉。

此时有两种vector，第一种 vector<vector>，第二种 vector<int>，如下图所示：

因此我们的解决方案是：对于vector的拷贝构造来说(还有reserve()拷贝数据时也要实现深拷贝) ，我们不仅要对vector<T>深拷贝，还要对vector<T>里面的每个数据也进行深拷贝，因为T有可能是内置类型，也有可能是自定义类型；即在这里应该这样做：

//v(copy)
vector(const vector<T>& copy)
{
	//1. 开空间
	_start = new T[copy.capacity()];
	//2. 拷贝数据
    //如果T是内置类型，直接赋值；
    //如果T是自定义类型，调用自定义类型的operator=
	for (size_t i = 0; i < copy.size(); ++i)
		_start[i] = copy[i];
	//3. 更新值
	_finish = _start + copy.size();
	_end_of_storage = _start + copy.capacity();
}

11. vector的模拟实现整体代码

namespace Xq
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{}

		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			//1. 预先开好空间
			reserve(n);
			//2. 插入数据
			for (int i = 0; i < n; ++i)
				push_back(val);
		}

		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			//1. 预先开好空间
			reserve(n);
			//2. 插入数据
			for (size_t i = 0; i < n; ++i)
				push_back(val);
		}
		//v(copy)
		vector(const vector<T>& copy)
		{
			//1. 开空间
			_start = new T[copy.capacity()];
			//2. 拷贝数据
			for (size_t i = 0; i < copy.size(); ++i)
				_start[i] = copy[i];
			//3. 更新值
			_finish = _start + copy.size();
			_end_of_storage = _start + copy.capacity();
		}

		v(copy)
		//vector(const vector<T>& copy)
		//	:_start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//{
		//	//1. 开空间
		//	reserve(copy.capacity());
		//	//2. 复用push_back()，更新数据
		//	for (const auto& e : copy)
		//		push_back(e);
		//}
		void swap(vector<T>& tmp)
		{
			std::swap(_start, tmp._start);
			std::swap(_finish, tmp._finish);
			std::swap(_end_of_storage, tmp._end_of_storage);
		}

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (first != last)
			{
				//复用push_back，更新数据
				push_back(*first);
				++first;
			}
		}
		//v(copy)
		//vector(const vector<T>& copy)
		//	:_start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//{
		//	//利用迭代器区间构造一个临时对象
		//	vector<T> tmp(copy.begin(), copy.end());
		//	swap(tmp);
		//}

		//copy = v
		//vector<T>& operator=(const vector<T>& copy)
		//{
		1. 检测是否给自己赋值
		//	if (this != &copy)
		//	{
		//		//2. 开新空间
		//		T* tmp = new T[copy.capacity()];
		//		//3. 拷贝数据
		//		for (size_t i = 0; i < copy.size(); ++i)
		//			tmp[i] = copy[i];
		//		//4.释放就空间
		//		delete[] _start;
		//		//5. 更新数据
		//		_start = tmp;
		//		_finish = tmp + copy.size();
		//		_end_of_storage = tmp + copy.capacity();
		//	}
		//return *this;
		//}

		//copy = v
		//vector<T>& operator=(const vector<T>& copy)
		//{
		//	if (this != &copy)
		//	{
		//		//创建一个临时对象
		//		vector<T> tmp(copy.begin(), copy.end());
		//		//直接交换
		//		swap(tmp);
		//	}
		//	return *this;
		//}

		//copy = v
		vector<T>& operator=(vector<T> tmp)
		{
			swap(tmp);
			return *this;
		}

		~vector()
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

		void resize(size_t n, const T& val = T())
		{
			if (n > capacity())
			{
				//开空间
				reserve(n);
			}
			
			if (n > size())
			{
				//插入数据
				size_t count = n - size();
				while (count--)
					push_back(val);
			}
			else
			{
				//不用更改数据，直接更改_finish即可
				_finish = _start + n;
			}
		}

		size_t capacity() const
		{
			return  _end_of_storage - _start;
		}

		size_t size() const
		{
			return _finish - _start;
		}

		bool empty() const
		{
			return _start == _finish;
		}

		void reserve(size_t n) 
		{
			//只考虑扩容，不考虑缩容，扩容有两种情况，a.空表；b.非空表(需要拷贝数据)
			if (n > capacity())
			{
				//1. 开新空间
				T* tmp = new T[n];
				//2. 拷贝数据
				if (!empty())
				{	
					for (size_t i = 0; i < size(); ++i)
					{
						tmp[i] = _start[i];
					}
				}
				//3.释放旧空间
				//size_t sz = size();
				delete[] _start;
				_finish = tmp + size();
				_start = tmp;
				_end_of_storage = _start + n;
			}
		}

		void push_back(const T& val)
		{
			//检查容量
			if (_end_of_storage == _finish)
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}
			*_finish = val;
			++_finish;
		}

		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 _start + size();
		} 

		const_iterator begin() const
		{
			return _start;
		}
		
		const_iterator end() const
		{
			return _start + size();
		}

		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

		iterator insert(iterator pos, const T& val)
		{

			//1. 检查pos的合法性
			assert(pos >= _start && pos <= _finish);
			//2. 检查容量
			if (_finish == _end_of_storage)
			{
				//提前算好pos的位置
				size_t n = pos - _start;  
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				//更新 pos
				pos = _start + n;
			}
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				--end;
			}
			*end = val;
			++_finish;
			return pos;
		}

		iterator erase(iterator pos)
		{
			//1. 确保pos的有效性
			assert(pos >= _start && pos < _finish);
			//2. 确保非空表
			assert(!empty());
			iterator begin = pos;
			size_t n = pos - _start;
			while (begin < _finish - 1)
			{
				*begin = *(begin + 1);
				++begin;
			}
			--_finish;
			pos = _start + n;
			return pos;
		}

		T& front()
		{
			assert(!empty());
			return *_start;
		}

		T& back()
		{
			assert(!empty());
			return *(_finish - 1);
		}

        const T& front() const
		{
			assert(!empty());
			return *_start;
		}

		const T& back() const
		{
			assert(!empty());
			return *(_finish - 1);
		}

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

12. vector 的练习题

12.1. 第一题

原题链接：136. 只出现一次的数字 - 力扣（LeetCode）

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //0 ^ 其他数字 = 其他数字
        int ret_val = 0;
        //通过 ^(二进制位相同为0，相异为1)，
        for(const auto& e : nums)  
        {
            ret_val ^= e;
        }
        return ret_val;
    }
};

12.2. 第二题

原题链接：118. 杨辉三角 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows,vector<int>());
        //初始化工作
        for(size_t i = 0; i < numRows; ++i)
        {
            vv[i].resize(i+1,0);
            //vv[i]中的首尾元素值是确定的
            vv[i].front() = vv[i].back() = 1;
        }
        //修改值
        for(size_t i = 2; i < numRows; ++i)
        {
            for(size_t j = 1; j < vv[i].size()-1; ++j)
            {
                if(0 == vv[i][j])
                {
                    // 2 1        1 1           1 0
                    vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
                }
            }
        }
        return vv;
    }
};

12.3. 第三题

原题链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0;
        int fast = 0;
        while(fast < nums.size())
        {
            //相等跳过
            if(nums[slow] == nums[fast])
                ++fast;
            //不相等去重
            else
                nums[++slow] = nums[fast++];
        }
        nums.resize(slow+1);
        return slow+1;
    }
};

12.4. 第四题

原题链接：17. 电话号码的字母组合 - 力扣（LeetCode）

class Solution {
    const char* num_to_str[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    void combine(string digits, int di, vector<string>& ret, string combine_str)
    {
        if(di == digits.size())
        {
            ret.push_back(combine_str);
            return;
        }
        //取数字字符映射字符串
        int num = digits[di] - '0';
        string str = num_to_str[num];
        for(auto ch : str)
        {
            combine(digits,di+1,ret,combine_str + ch);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> v;
        if(digits.empty())
            return v;
        string str;
        combine(digits,0,v,str);
        return v;
    }
};