C++ --- vector的简单实现

引言

本次vector的成员属性是三个指针，分别是_start，_finish，_end_of_storage，如下图所示：

这是一个vector对象，_start指向顺序表表头，_finish指向容器实际空间大小，_end_of_storage指向容器的容量大小。
对比string类的的成员属性，_str，_size，_capacity，在vector中_start就是_str，_size就是_finish 减去 _start，_capacity就是_end_of_storage 减去 _start，本质上没有什么区别。

并且此容器使用模板类（模板不能声明定义分离），以满足任意类型。

一、默认成员函数

1.构造函数

1.1 默认构造函数

由于本次实现vector所定义的成员属性都是指针，所以直接赋值为空指针即可。

// 构造函数
vector()
	:_start(nullptr)
	,_finish(nullptr)
	,_end_of_storage(nullptr)
{}

对于上述代码还能简化，在属性声明处直接给定缺省值nullptr，因为不管是什么属性，都会走一遍初始化列表，有显式写就如上述代码一样，就用括号内给定的值进行初始化，若没有显式写则会使用缺省值进行初始化，若连缺省值都没有，那么编译器就会默认初始化了，可能是给定nullptr，也可能是给定随机值。

class vector
{
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;
};

// 构造函数
vector()
{}

// 也可以这样写
// 这是强制编译器生成默认构造
vector() = default;

1.2 初始化列表构造

使用initializer_list进行构造，即对象可以像这样：对象名 = { val1,val2,…… }，如此构造。

// 初始化列表构造
vector(initializer_list<T> il)
{
	reserve(il.size());
	for (auto& e : il)
	{
		push_back(e);
	}
}

1.3 迭代器区间构造

此构造也是写成一个模板，以满足使用不同类型的迭代器区间进行构造，例如string对象的迭代器区间去构造一个vector对象。

// 迭代器区间构造
// 为何要使用模板，因为可以使用不同类型的迭代器区间去构造vector对象
// 可以不局限于一种类型
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

1.4 n个val构造

// n个val进行构造
vector(size_t n, T val = T())
{
	resize(n, val);
}

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

n个val构造会和上面迭代器区间构造进行重合，若只想使用n个val构造则需要明确类型，要么都是size_t，要么都是int，否则都会调到迭代器区间构造去，并且n个val构造的参数都是整数，被调入迭代器区间构造还会报错：非法的间接寻址。

2.拷贝构造函数

// 拷贝构造 --- v2(v1)
vector(const vector<T>& v)
	// 要先初始化一下，要不然reserve开同样大小的空间的时候会出问题 --- 即这三个指针在不同编译器的默认初始化是给nullptr还是随机值
	// 初始化操作已经被缺省值代替了 
{
	reserve(v.capacity());
	for (auto& e : v)
	{
		push_back(e);
	}
}

3.析构函数

// 析构函数
~vector()
{
	// 当_start不为空时
	if (_start)
	{
		delete[] _start;
		_start = _finish = _end_of_storage = nullptr;
	}
}

4.运算符重载

4.1 operator=

// 赋值运算符重载
// 现代写法
vector& operator=(const vector<T>& v)
{
	// 对this和v进行交换，同样达到赋值效果
	swap(v);  
	return *this;
}

4.2 operator[ ]

两个版本，针对const和非const对象。

T& operator[](size_t i)
{
	// i位置要合法
	assert(i < size());
	return _start[i];
}

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

二、遍历方式

1.下标 + [ ]

由于vector底层是用一个数组来存储数据的，所以可以使用下标＋[ ]来遍历对象。

// 下标 + [ ]
for (size_t i = 0; i < v.size(); i++)
{
	cout << v[i] << " ";
}

2.迭代器

此迭代器由原生指针实现，也是由于底层是数组，可以使用指针来实现迭代器，解引用迭代器就是该位置上的元素，并且只实现四个版本，const正向迭代器和非const正向迭代器，反向迭代器不在这里实现，因为其后可以使用适配器直接由正向迭代器适配出反向迭代器。

typedef T* iterator;
typedef const T* const_iterator;

// 非const正向迭代器
iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

// const正向迭代器
const_iterator begin() const
{
	return _start;
}

const_iterator end() const
{
	return _finish;
}

// 使用
// 迭代器
dyj::vector<int>::iterator it1 = v.begin();
dyj::vector<int>::iterator it2 = v.end();
for (it1; it1 != it2; it1++)
{
	cout << *it1 << " ";
}

3.范围for

范围for是基于迭代器实现的，实现了迭代器就能使用范围for。

// 范围for
// 这里v是vector对象
for (auto e : v)
{
	cout << e << " ";
}

三、增删改查

1.reserve()

扩容方法。

void reserve(size_t n)
{
	// 只实现扩容，缩容不实现
	if (n > capacity())
	{
		// 下面拷贝数据后因为_start先比_finish改变了，会导致size()计算错误，即不能使用拷贝后的size，要使用拷贝前的size
		size_t oldsize = size();

		// 需要扩容
		T* temp = new T[n];
		if (_start)
		{
			// 拷贝旧空间的数据到新空间
			// memcpy进行的是一个字节一个字节的拷贝，对于内置类型没有问题，但对于string这类的自定义类型就不行
			// 因为string的成员有一个_str，_str指向一个堆上开辟的空间，使用memcpy直接将旧的_str拷贝给新的_str
			// 导致新旧空间的_str都指向同一块空间，旧空间被释放，自然新空间指向的也就被释放，导致产生随机值。
			//memcpy(temp, _start, sizeof(T) * size());
			for (size_t i = 0; i < oldsize; i++)
			{
				temp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = temp;
		_finish = _start + oldsize;
		_end_of_storage = _start + n;
	}
}

本方法有两个需要注意的点：
（1）扩容完成之后在更新指针时，_finish的更新需要使用扩容之前的size大小，因为size是由_finish 减去 _start得来的，而_start最先修改，会导致计算出一个错误的size值，所以这里要使用旧的size大小。
（2）旧空间拷贝到新空间的时候，对于memcpy函数，内置类型没有问题，内存块的直接复制，而对于自定义类型，例如string，它的成员属性有一个指向数组的指针_str，使用memcpy会导致新旧空间的_str都指向同一块空间，后续有一步delete，旧空间被释放，自然新空间指向的也就被释放，导致产生随机值，所以进行赋值操作，直接连同指向的空间一起拷贝。

2.resize()

扩容或者缩容方法。
当给定的参数n(size_t类型)，大于容器size时，会扩容，并且填充给定的val值，大于容器的capacity时也是如此；当给定的参数n(size_t类型)，小于容器size时，会缩容，缩小到给定的n值处。

// 这里模板参数给定缺省值使用匿名对象，由于T可以是任意一种类型，导致缺省值不能是某一种类型
// 所以这里使用匿名对象，直接通过构造函数来给定缺省值，并且在C++里，内置类型也进行了升级
// 可以像创建对象一样使用其语法
// 例如：int i = 0;
//       int j(1);
//       int k = int();
//       int l = int(10);
void resize(size_t n, T val = T())
{
    // 扩容
	if (n > size())
	{
		reserve(n);
		while (_finish != _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
	// 缩容
	else
	{
		_finish = _start + n;
	}
}

需要注意泛型给定缺省值可以使用匿名对象，直接通过构造函数来给定缺省值。

3.push_back()

尾插方法。

void push_back(const T& x)
{
	// 先判断是否扩容
	if (_finish == _end_of_storage)
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}

	*_finish = x;
	++_finish;
}

4.pop_back()

尾删方法。

void pop_back()
{
	// 首先要判断是否能够尾删，即顺序表中还有元素 --- _start != _finish / !empty()
	//assert(_start != _finish);
	assert(!empty());
	--_finish;
}

5.insert()

任意位置插入方法。

iterator insert(iterator pos, const T& x)
{
	// 首先判断pos位置是否合法
	assert(pos >= _start && pos <= _finish);

	// 首先判断是否需要扩容
	if (_finish == _end_of_storage)
	{
		// 及时更新pos位置，避免迭代器失效
		size_t len = pos - _start;

		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);

		pos = _start + len;
	}

	// 挪动数据
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}

	// 插入数据
	*pos = x;
	++_finish;

	return pos;
}

这里需要注意扩容会导致迭代器失效，扩容的迭代器失效是因为扩容之后会更新成员指针，但是pos位置的指针没有更新，导致迭代器失效，从而无法正确插入数据，对于失效的迭代器，要么坚决不再使用，要么及时更新指针。

6.erase()

任意位置删除方法。

iterator erase(iterator pos)
{
	// 首先判断pos位置是否合法，即[_start,_finish)，右边为开区间是因为_finish是最后一个有效位置的下一个位置
	// 对于erase来说位置是非法的
	assert(pos >= _start && pos < _finish);

	iterator it = pos + 1;
	while (it != _finish)
	{
		*(it - 1) = *it;
		++it;
	}

	--_finish;

	return pos;
}

同样erase方法也会导致迭代器失效，不过和insert有些区别。
下面有一个删除容器中所有的偶数的示例，可以直观的感受erase的迭代器失效。

dyj::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
 v.push_back(4);

Print(v);

// 实现一个程序，用来删除顺序表中所有的偶数
auto it = v.begin();
while (it != v.end())
{
	if (*it % 2 == 0)
	{
		it = v.erase(it);
	}
	else
	{
		// 此时迭代器也是失效的，因为VS编译器下对于迭代器失效的检查是非常严格的
		// 当erase(it)之后，it位置就已经失效了，之后再对it进行操作则会引发崩溃等检查措施
		// 所以解决方法就是要么不再使用此迭代器了，要么更新it的位置，使得不再失效
		++it;
	}
}
Print(v);

同样还是那句话 对于失效的迭代器，要么坚决不再使用，要么及时更新指针。

7.empty()

判断容器是否为空的方法。

bool empty()
{
	// 判段顺序表是否为空 --- 为空（返回true）、不为空（返回false）
	return _start == _finish;
}

8.clear()

清空容器的方法。

void clear()
{
	_finish = _start;
}

四、其他

1.size()

计算容器的实际size大小。

// 实际空间大小
size_t size() const
{
	// 指针 - 指针
	return _finish - _start;
}

2.capacity()

计算容器的容量大小。

// 空间容量
size_t capacity() const
{
	return _end_of_storage - _start;
}

3.swap()

交换方法。

void swap(const vector<T>& v)
{
	_start = v._start;
	_finish = v._finish;
	_end_of_storage = v._end_of_storage;
}

五、总结

本次对于vector的简单实现，当中有两个注意点，一是迭代器失效（insert和erase），二是深层次的深浅拷贝问题（reserve中扩容），这都是非常需要注意的易错点。
对于迭代器失效要么坚决不再使用，要么及时更新指针**。
对于深层次的深浅拷贝问题，直接使用空间复制，连同指向的空间也一并复制过来，避免指向同一块空间，导致析构两次，程序崩溃。