C++ vector 的模拟实现

 

目录

1. vector 类的成员变量

2. 无参构造

3. 析构函数 

4.  size_t capacity()

5. size_t size()

6. void reserve(size_t n)

 7. 迭代器

8. void push_back(const T& x) 

9. T& operator[](size_t pos) 

10. iterator insert(iterator pos, const T& val)

11.  iterator erase(iterator pos)

12. void pop_back()

13. void resize(size_t n, const T& val = T()) 

14. void swap(vector& v)

15. 拷贝构造 

16. 赋值运算符重载 

17. vector(size_t n, const T& val = T()) 

18. vector(InputIterator first, InpuIterator last) 

---

1. vector 类的成员变量

在上一讲我们学习了如何使用vector，我们很可能会认为：vector类的成员变量是和 string 类的成员变量差不多：T* _data，size_t size，size_t _capacity。这样来实现当然没有什么问题，这不就是和顺序表的实现差不多嘛！但是我们会参考库里面 vector 的实现来模拟实现 vector。

我们可以参考 STL_30 中 vector 的源码：

 我们可以看到库里面关于 vector 的实现是维护三个迭代器变量，用这三个迭代器变量来控制成员函数的实现逻辑。根据变量名，我们可以盲猜出这三个变量的含义：

恭喜你，猜对了！库里面的三个迭代器变量就是这么一个意思。在 vector 的使用哪一节，我们已经知道了vector 的迭代器就是 T*。那我们就能够定义出 vector 的基本结构啦！但这里有个问题就是维护三个迭代器变量来实现 vector 有什么好处呢？我们在实现的过程中再来细谈！

namespace Tchey
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
 
	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	}
}

2. 无参构造

无参构造不需要做什么事儿，只需要将我们的三个迭代器初始化为 nullptr 就行啦！

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

3. 析构函数 

析构函数就是释放 vector 维护的空间，只有当 _start 不为 nullptr 才需要释放。当然 delete nullptr也没啥问题，但是为了严谨嘛！

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

4.  size_t capacity()

这个函数比较简单呢！vector 的实际容量就是 _endofstorage - _finish 啊！可以结合三个变量的意义来看：

size_t capacity()
{
	return _endofstorage - _start;
}

5. size_t size()

size 的求法和 capacity 的求法是一样的哇！size = _finish - _start。请参照上图。

size_t size()
{
	return _finish - _start;
}

6. void reserve(size_t n)

1：判断是否需要扩容！只有当 n > capacity() 的时候才需要扩容！为什么要有这一步检查呢？因为这个 reserve 不仅仅是给其他成员函数使用的，还有可能直接被用户使用！因此还是需要有合法性检查。

2：开辟新空间，拷贝原数据，释放旧空间。

3：更新 _start，_finish，_endofstorage。

void reserve(size_t n)
{
	if (n > capacity())
	{
        size_t sz = size();
		T* tmp = new T[n];
		if (_start) //有数据才拷贝
		{
			memcpy(tmp, _start, sz * sizeof(T));
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_endofstorage = _start + n;
	}
}

注意：更新 _finish 的时候不能直接写：_start + size()，因为size() 的计算依赖于 _start 和 _finish，因为 _start 已经被修改了，因此不可以直接用size()，需要提前保存 size()。 

但是这样写真的没问题嘛？我们经过测试发现这样的代码会使程序崩掉的：

 

这是为啥呢？我们来看看图解：

 

string 维护的三个成员变量管理着堆区的空间，当我们需要扩容的时候，拷贝 vector 中原来的数据，因为我们用的是 memcpy 知识单纯的赋值，因此拷贝后的数据同样也是指向原先 vector 中的 string 指向的空间，在我们 delete 掉原空间之后，实际上新的 vector 中的 string 指向的空间已经被释放了！等函数调用结束，势必会出现二次析构的问题！

解决的办法很简单，直接 for 循环赋值就行了！

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start) //有数据才拷贝
		{
			for (int i = 0; i < sz; i++)
				tmp[i] = _start[i];
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_endofstorage = _start + n;
	}
}

对于内置类型，= 赋值会调用赋值运算符重载，这样就没问题啦！ 

 7. 迭代器

维护三个迭代器变量 begin() 函数，end() 函数的实现就比较简单啦！

iterator begin()
{
	return _start;
}
 
iterator end()
{
	return _finish;
}
 
const_iterator begin() const
{
	return _start;
}
 
const_iterator end() const
{
	return _finish;
}

8. void push_back(const T& x) 

1：检查是否需要扩容。

2：插入数据。

3：更新 _finish。

void push_back(const T& x)
{
	if (_finish == _endofstorage) //扩容逻辑
	{
		size_t newCapaciy = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapaciy);
	}
 
	*_finish = x;
	_finish++;
}

9. T& operator[](size_t pos) 

1：检查 pos 的合法性。

2：找到 pos 位置对应的迭代器，返回其解引用的值就 OK。可以这么写：*(_start + pos)，定睛一看不就等于：_start[pos] 嘛！

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

10. iterator insert(iterator pos, const T& val)

1：检查 pos 合法性。

2：扩容逻辑的判断。

3：挪动数据。我们可以发现维护三个迭代器变量的好处就来了，在 string 的模拟实现中，我们移动数据的时候可能会发生死循环的问题，就是当 end == 0 的时候，减一之后变成 -1，因为 pos 是 size_t 类型的，end 会被整形提升，导致陷入死循环。但是使用迭代器之后完全没有这种问题！

于是你写出来了这样的代码：

void insert(iterator pos, const T& val)
{
	assert(pos >= _start && pos <= _finish);
 
	if (_finish == _endofstorage)
	{
		size_t newCapaciy = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapaciy);
	}
 
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
 
	*pos = val;
	++_finish;
}

这样做真的没有问题吗！我们来看看下面的这组测试用例：

 

为什么头插一个 0 的时候会出现随机值，并且 0 还没有插入进去呢？这里有一个严重的问题：迭代器失效的问题，我们现在书写的 insert 函数，在扩容的时候就会发生迭代器失效的问题。

我们来分析出现这种情况的原因哈：当我们的 vector 已经有 4 个元素了，在插入一个元素就会扩容，一旦扩容就会开辟新的空间并且会拷贝原空间的数据，那么实参的 begin() 指向的空间已经被释放了，这就造成了迭代器失效的问题！

 应该怎么解决这个问题呢？我们在扩容之前保存 pos 相对于 _start 的偏移量即可。

我们现在解决了 insert() 函数内部迭代器失效的情况，那么如何解决外部迭代器失效的情况呢？

什么是外部迭代器失效？来看下面的例子：

想必你也知道原因了：形参是实参的拷贝，形参的改变不影响实参，即使扩容的时候我们在函数内部修改了形参 pos 的，实参依然是不会改变的！上面的代码中让 *it-- 就发生了内存的非法访问，这是不被允许的！

你可能一下就想到了一个解决办法：把 insert() 函数的参数改为引用不就行啦？但是当我们这样调用 insert() 函数的时候编译就无法通过啦：

insert(a.begin(), 0);  // begin() 函数是值返回，是一个临时对象具有常性不可以被 iterator& 接收。

insert(a.begin() + 3, 0) // 这是一个表达式的计算，计算结果也是一个临时对象，同样不能被 iterator& 的形参接收。

那你可能会说：我用const iterator& 来做形参，那你在函数内部就无法修改形参 pos 了，怎么解决迭代器失效的问题呢？

因此正确的解决办法是参考库函数， 给 insert() 函数加上返回值。

iterator insert(iterator& pos, const T& val)
{
	assert(pos >= _start && pos <= _finish);
 
	if (_finish == _endofstorage)
	{
		size_t offset = pos - _start;
		size_t newCapaciy = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapaciy);
		pos = _start + offset;
	}
 
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
 
	*pos = val;
	++_finish;
	return pos;
}

11.  iterator erase(iterator pos)

1：检查 pos 位置的合法性。

2：挪动元素。

就很简单哇！但是我们需要考虑的问题是 erase 是否有迭代器失效的问题呢？

看下面的代码，我们删除 4 这个元素之后呢，再去访问 it 迭代器不就是越界访问了嘛。

当你在VS中使用 std::vector 使用 it 迭代器会直接报错，VS 认为无论是否越界访问，使用删除的迭代器就是不正确的。

但是在 Linux 下使用 g++ 编译器均不会报错呢！我们看到不同的编译器对此的处理结果也是不相同的嘞！

为了使得C++代码兼容 g++ 编译器和 VS 的编译器，我们必须让 erase 有返回值，返回删除位置的下一个位置的迭代器，这样就能做到 VS 下访问不报错了！

补充：VS 库中 vector 迭代器的实现其实是经过封装的，并不是原生指针。可见实现 vector 的方式真的很多哇！

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

12. void pop_back()

1：注意有元素才能删除嘛。std::vector 是直接断言检查的！

2：其实也可以复用 erase 函数。

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

13. void resize(size_t n, const T& val = T()) 

实现的思路和 string 的 resize 差不多：

1：当 n < size() 直接修改 _finish 即可。

2：其余情况我们都可以调用 reserve 把空间开好，因为 reserve 的实现做了检查，不需要扩容的时候是不会扩容的！空间好了之后填充 val 就可以啦！

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

14. void swap(vector& v)

这是交换两个 vector 对象，很简单只需要交换 vector 的成员变量就行了！

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

15. 拷贝构造 

类提供的默认拷贝构造会实现直接赋值的浅拷贝，导致析构的时候同一块堆区的空间会被释放两次。这就是经典的浅拷贝，因为我们的 vector 维护了堆区的数据，因此要实现类的深拷贝。

老老实实开空间拷贝数据。很简单的！

vector(const vector& v)
{
	_start = new T[capacity()];
	memcpy(_start, v._start, sizeof(T) * size());
	_finish = _start + v.size();
	_endofstorage = _start + v.capacity();
}

16. 赋值运算符重载 

传统写法很简单，这里就不写了。

我们的现代写法在 string 的模拟实现哪一节提到过。就是利用自定义类型函数传值调用会调用拷贝构造的特点，然后将拷贝构造出来的形参交换给自己，同时随着形参的销毁，形参右释放了原来的空间，简直就是一举两得！

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

17. vector(size_t n, const T& val = T()) 

这个构造函数直接调用 resize() 就可以啦！

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

18. vector(InputIterator first, InpuIterator last) 

这个构造函数是使用一段迭代器区间来初始化 vector ，区间：[first, lasr)，InpuIterator 是模板参数。

例如：

代码实现：

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

但是这么写的话，就会有一个问题：我们这样初始化 vector 就会报错：

vector<int> a(10, 1);

这是因为：参数 10 和 1 均会解析成 int 类型，从而构造函数走的是：迭代器初始化的版本。导致编译错误！为了解决这个问题，我们可以再提供一个构造函数：将 size_t 变成 int，这样就不会报错了。

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