前言

前面介绍了【C++】STL容器–vector的使用详情请点击，本文将在学习了vector的使用的基础上继续介绍vector的模拟实现

一、基本框架

我们使用模板来实现vector，因此声明和定义不能分离，我们创建两个文件：test.cpp和vector.h

• test.cpp：main函数，测试vector代码
• vector.h：vector相关声明和定义实现

1. vector是类模板，allocator< T >是空间配置器，内存池，用于避免在堆上频繁的申请空间，提高效率，暂不作深入了解
2. 在使用类模板的时候要使用类型进行显示实例化
3. vector实际上就是一个可以存放T类型的顺序表，在实现顺序表的时候，我们是有一个指针指向堆上的空间（数组），描述该数组实际存储数据大小和数组容量；现在我们实现vector使用3个指针来实现
   
4. vetor底层时数组，因此iterator的实现可以通过指针来实现，将T* typedef 为 iterator，因此vector的模板框架如下：

namespace gy
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;

	private:
		iterator _start = nullptr;// T* _start
		iterator _finish = nullptr;// T* _finish
		iterator _endofstorage = nullptr; // T* _endofstorage
	};
}

二、vector的模拟实现

1. 构造函数

1. 在声明部分已经给了缺省值初始化，所以构造函数不需要再初始化。虽然构造没有初始化，但是构造函数不能省略，因为构造函数如果类中没有显式定义构造函数，则C++编译器会自动生成⼀个无参的默认构造函数，⼀旦用户显式定义编译器将不再生成。但是我们还会有拷贝构造（也是构造），因此编译器不会自动生成⼀个无参的默认构造函数

vector()
{}

2. 使用花括号进行初始化，可以使用initializer_list< T > 来进行初始化

vector(initializer_list<T> il)
{
	reserve(il.size());
	for (auto& e : il)
	{
		push_back(e);
	}
}

3. 使用迭代器区间构造，由于vector中可以保存vector、int、char、string各种类型数据，因此在使用迭代器区间来构造时，所以得保证任何类型的迭代器都能进行初始化，所以我们设计成模板，模板参数类型是迭代器，这样就可以接受任意类型的迭代器区间来进行初始化

//只能传入vector迭代器区间
vector(iterator start, iterator end)
{
	while (start != end)
	{

		push_back(*start);
		++start;
	}
}

//任意类型容器迭代器
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{

		push_back(*first);
		++first;
	}
}

4. n个val的构造，由于T为int类型时会和迭代器区间构造调用产生歧义，编译器会去调用和自己类型最匹配的，如果没有最匹配的，就回去调用模板，比如：gy::vector v5(10, 7)，由于size_t 是无符号类型，但是T为int类型，n传入的时候需要转换为无符号类型；但是迭代器区间构造是一个函数模板，它就会去生成两个int，int，此时模板生成的更匹配
5. 所以为了能调用到正确的构造函数，我们还需要单独为int类型提供给一个构造函数

vector(size_t n, T val = T())
{
	resize(n, val);

}

vector(int n, T val = T())
{
	resize(n, val);

}

2. 析构函数

当_start == nullptr时，说明_start并没有资源需要清理，如果不为空则需要调用析构函数

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

3. size/capacity

由于size和capacity函数只是获得对应的大小，不用修改它，因此可以加入const修饰this指针，让普通对象和const修饰对象都能调用

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

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

4. reserve

1. 针对reserve我们只考虑扩容，不考虑缩容情况，因此我们只在n > capacity()时扩容
2. 在使用reserve扩容都是使用异地扩容，将_start 的数据copy给tmp，然后delete[] _start，再_start = tmp，如果_finish = _start + size()，那么会出现一个问题，_start更新后，_start + size() = _start + _finish - _start = _finish(还是原来的_finish)，因此为了得到扩容后的_finish，我们要在扩容前记录有效元素个数 size_t old_size = size()，然后得到_finish = _start + old_size
3. 扩容将_start 的数据copy给tmp时，我们不能使用memcpy，当拷贝的数据是内置类型时，我们使用memcpy进行字节拷贝是没有问题，当我们的数据是string等自定义类型时，我们不能使用浅拷贝。解决这个问题我们使用赋值（自定义类型的赋值重载是深拷贝）
   

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t old_size = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T*) * old_size);
			for (size_t i = 0; i < old_size; i++)
			{
			    tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + old_size;
		_endofstorage = _start + n;
	}
}

5. push_back

1. push_back尾插，插入的数据可能是内置类型也可能是自定义类型，所以我们使用传引用返回
2. 插入数据需要判断空间是否满了，如果_finish == _endofstorage则空间已满，需要调用reseve函数扩容

void push_back(const T& x)
{
	if (_finish == _endofstorage)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
	*_finish = x;
	++_finish;
}

6. pop_back

pop_back：在进行尾删的时候需判断有效数据个数，当有效数据个数为0时不能再删除

bool empty()const
{
	return _start == _finish;
}
void pop_back()
{
	//assert(_finish > _start);
	//assert(size() != 0);
	assert(!empty());
	--_finish;
}

7. begin/end

vector的迭代器是使用指针实现的，const_iterator和iterator迭代器分别用于const修饰对象和普通对象，const修饰的是T*即迭代器指向的数据不能修改，并不是修饰的迭代器本身，const_iterator是能够更改指向数据（迭代器本质就是用来遍历数据）

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;
}

8. operator[]

1. vector底层是数组，因此我们可以使用下标访问来遍历vector
2. 我们可以提供两个operator[]，一个是普通对象的operator[]，一个是const修饰的operator[]，const修饰的operator[]返回的对象不能修改

T& operator[](size_t i)
{
	assert(i < size());
	return _start[i];
}
const T& operator[](size_t i) const
{
	assert(i < size());
	return _start[i];
}

9. insert

1. insert在pos位置（迭代器表示的位置）插入T类型的值，涉及迭代器失效的问题
2. 插入位置pos范围是：pos >= _start && pos <= _finish
3. 只要是插入数据都要判断空间是否满了，如果满了就需要扩容，一旦扩容（异地扩容）就会涉及迭代器失效问题，新空间的位置和原来位置不同了，但是pos还是旧空间对应插入的位置，所以我们要实时更新pos位置
4. 更新pos位置，只需要在扩容前记录pos和_start之前相差多少数据len，然后根据新_start + len就可以得出新的pos

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos <= _finish);
	size_t len = pos - _start;
	if (_finish == _endofstorage)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());

		pos = _start + len;
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;
	++_finish;

	return pos;
}

10. erase

1. erase删除pos位置的数据时也会涉及迭代器失效问题
2. pos的范围是：pos >= _start && pos < _finish
3. 删除pos位置的元素后，后面的数据依次向前挪动，pos 位置原本的元素已经被 pos+1 的元素覆盖，pos 现在指向的是原来 pos+1 位置的元素，且如果删除的是最后一个元素，pos 可能指向容器之外

iterator erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);
	iterator it = pos + 1;
	while (it != _finish)
	{
		*(it - 1) = *it;
		++it;
	}
	--_finish;

	return pos;
}

11. resize

1. 将vector有效数据变为n个，如果n大于有效数据，n - 有效数据 将用val填补，如果n小于等于容量不需要扩容，大于容量则需要扩容，这里统一调用reserve函数（如果n > _capacity才会扩容）
2. 如果n小于有效数据，那么有效数据变为n，即_finish = _start + n
3. 对于传入的val值我们给了缺省参数，因为我们传入的val可能是整型、char、double、string、指针类型，那么怎么样写缺省参数好呢？C++内置类型编译器会默认生成构造函数，因此我们使用T()就能调用各种类型的构造函数来初始化（int类型初始化为：0；char初始化为：‘\0’；double类型初始化为：0.0）

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

12. 拷贝构造函数

首先将容量扩容到拷贝的容量，再将拷贝vector中的数据一个一个的尾插到当前vector中

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

13. swap

交换两个vector对象，这里需要传引用方式，交换两个对象的三个指针_start、_finish、_endofstorage，这样this就会指向v指向得分空间的数据，这样就实现了交换

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

14. operator=

1. 这里传入的参数v不需要传引用返回，因为我们不需要改变v指向的空间，只需要将形参的内容赋值给this，但是不能改变形参
2. 同时由于我们支持连续赋值，返回时我们需要传引用返回

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

三、完整代码

完整代码链接