【C++练级之路】【Lv.7】【STL】vector类的模拟实现

快乐的流畅：个人主页

个人专栏：《C语言》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

关于STL容器的学习，我们来到了运用最广泛、最常见的vector。有了之前关于string的学习，我们对容器设计有了一个大概的了解，而今天在熟悉的基础上去探求vector相比于string有哪些异同，同时迎来更多的新挑战……

一、成员变量

vector类中包含了

• _start（指向有效空间的头）
• _finish（指向有效空间的尾）
• _end_of_storage（指向可用空间的尾）

细节：

1. 三个成员变量均迭代器（此刻即指针）
2. 使用缺省值，不必写多份初始化列表

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;
};

二、默认成员函数

2.1 constructor

无参构造

vector()
{}

带参构造

细节：

1. 分别重载 size_t 和 int 类型，防止参数匹配时，匹配到迭代器区间构造，从而导致间接寻址错误
2. 初始化的val的缺省值，是匿名构造的对象

vector(size_t n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; ++i)
	{
		_start[i] = val;
	}
	_finish = _start + n;
}

vector(int n, const T& val = T())
{
	reserve(n);
	for (int i = 0; i < n; ++i)
	{
		_start[i] = val;
	}
	_finish = _start + n;
}

迭代器区间构造

细节：

1. 使用类模板，可以传任意类型的迭代器
2. 迭代器访问，条件最好使用不等于（！=）

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

2.2 destructor

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

2.3 copy constructor

近代写法

细节：

1. 先开辟一维空间
2. 再用赋值重载，进行深拷贝（不能用memcpy，它是浅拷贝）

vector(const vector<T>& x)
{
	_start = new T[x.capacity()];
	for (size_t i = 0; i < x.size(); ++i)
	{
		_start[i] = x._start[i];
	}
	_finish = _start + x.size();
	_end_of_storage = _start + x.capacity();
}

现代写法

细节：

1. 用迭代器区间构造，构造出临时对象
2. 再使用vector中的swap，交换*this和tmp的值，完成拷贝构造

vector(const vector<T>& x)
{
	vector<T> tmp(x.begin(), x.end());
	swap(tmp);
}

2.4 operator=

近代写法

细节：大体与拷贝构造相同

vector<T>& operator=(const vector<T>& x)
{
	if (this != &x)
	{
		_start = new T[x.capacity()];
		for (size_t i = 0; i < x.size(); ++i)
		{
			_start[i] = x._start[i];
		}
		_finish = _start + x.size();
		_end_of_storage = _start + x.capacity();
	}
	return *this;
}

现代写法

细节：

1. 传参变成传值，这样就会拷贝构造出一个临时对象
2. 再使用vector中的swap，交换*this和tmp的值，完成赋值重载

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

三、迭代器

3.1 begin

迭代器的实现和编译器有关，不同的编译器有不同的实现方式。这里用指针来实现迭代器。

同时，重载了普通迭代器和const迭代器。

iterator begin()
{
	return _start;
}

const_iterator begin() const
{
	return _start;
}

3.2 end

迭代器遵循左闭右开的原则，begin指向首元素，end指向末元素的下一位。

iterator end()
{
	return _finish;
}

const_iterator end() const
{
	return _finish;
}

悄悄告诉你：范围for的底层实现，就是运用了迭代器。

四、元素访问

4.1 operator[ ]

为了方便的访问元素，我们重载了[ ]运算符。同时，也分为普通版本和const版本，对应不同vector类的权限。

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

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

五、容量

5.1 size

获取当前有效数据个数

细节：const修饰，保证普通和const类型vector类都能访问

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

5.2 capacity

获取当前最大有效容量

细节：同上

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

看了上面size和capacity的实现，是不是就瞬间明白_start、_finish和_end_of_storage的含义了？

悄悄告诉你：其实当你不懂成员变量的含义时，可以先看看size和capacity的实现。

---

5.3 reserve

改变当前最大容量

细节：

1. 只扩容，不缩容
2. 用赋值重载，进行深拷贝
3. 更新成员变量时（如果按照顺序更新），先保存size的大小，防止_finish失效。因为如果为_finish = tmp + size()，等价于_finish = tmp + _finish - _start，而_start已经更新了，所以size()计算的大小失效，最终_finish并没有更新。

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)
		{
			for (size_t i = 0; i < size(); ++i)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}

		size_t sz = size();
		_start = tmp;
		_finish = tmp + sz;
		_end_of_storage = tmp + n;
	}
}

5.4 resize

改变当前有效数据个数

细节：

1. 如果n<size，则减少有效个数，如果n>size，则填充指定值，直至达到n个
2. 运用赋值重载，实现深拷贝

void resize(size_t n, T val = T())
{
	if (n > size())
	{
		reserve(n);
		for (size_t i = size(); i < n; ++i)
		{
			_start[i] = val;
		}
	}
	_finish = _start + n;
}

5.5 empty

判断是否为空

细节：const修饰，保证普通和const类型vector类都能访问

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

六、修改

6.1 push_back

尾插

细节：需要扩容时，判断容量是否为空

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

	*_finish = val;
	++_finish;
}

6.2 pop_back

尾删

细节：断言vector不为空，才进行删除

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

6.3 insert

指定位置插入

细节：

1. 断言判断pos的合法性
2. 扩容前，先保存pos的相对位置，扩容后，刷新pos，防止迭代器失效
3. 返回指向新插入元素的迭代器，防止迭代器失效

iterator insert(iterator pos, const T& val)
{
	assert(pos >= _start && pos <= _finish);

	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		pos = _start + len;
	}

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

	*pos = val;
	++_finish;
	return pos;
}

6.4 erase

指定位置删除

细节：

1. 断言判断pos的合法性
2. 返回指向删除元素的后一位的迭代器，防止迭代器失效

iterator erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);

	iterator start = pos + 1;
	while (start < _finish)
	{
		*(start - 1) = *start;
		++start;
	}

	--_finish;
	return pos;
}

---

上述有两种迭代器失效：

1. 野指针
2. 指向含义改变

关于迭代器失效，我们统一认为，进行过插入或删除操作的迭代器pos，已经失效，不能再使用。只有接收其返回值，刷新pos，才能重新使用。

---

6.5 swap

交换两个vector类的值

细节：使用std库中的swap函数，交换各个成员变量的值

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

总结

我们在有了学习string的基础后，学习vector的成本降低了不少，函数名和用法大体相同。但是，我们依旧遇到了新的问题与挑战，如多层深拷贝，迭代器失效等。我与C++的故事，仍在无声地诉说……

真诚点赞，手有余香