【C++】vector的模拟实现

个人主页<—请点击
C++专栏<—请点击

一、vector的基本框架

了解过vector的朋友都知道，它可以实现很多种类型的结构，如vector<int>、vector<char>等等，这是因为它是使用模板来实现的，所以我们要模拟实现vector，我们也需要使用模板来模拟实现。

要使用模板进行模拟实现vector，我们需要注意模板的声明和定义不能分离，所以我们不能分成vector.h和vector.cpp来管理，我们必须将它们合并成一个文件vector.h，不然会引发链接错误。我们实现的vector的所有接口的名称都和STL库中的是相同的，所以为了避免冲突我们要将实现的模板放入自定义的命名空间中，我们起名叫VEC。

STL库中的vector是这样的：

其中class Alloc = allocator<T> 是空间分配器，是模板声明中默认分配器的指定方式，这里大家作一下了解即可，在模拟实现时并不会用到。

为了更好的管理空间，我们的成员函数将会用到三个指针，分别是_start、_finish、_endofstorage，具体作用如下图所示：

代码：

namespace VEC
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;
	};
}

注意：这里我们在声明三个指针的时候赋予了它们缺省值nullptr，这样在实现构造函数的实现时会省很多事情。

二、vector的模拟实现

2.1 vector的基本成员函数

构造函数

vector()
{ }

我们之前已经给了成员变量缺省值，所以这里只需要写这样就可以走初始化列表进行初始化，其实在当前代码的基础上不写构造函数，编译器会默认生成的，但我们以后少不了写拷贝构造。当程序中存在构造函数的时候（拷贝构造也是构造），编译器就不会在自动生成默认构造函数，此时如果你不写构造函数时，程序就会出问题，当你使用这段代码vector<int> v;时就会报出没有合适的构造函数可用的错误。

在编译器生成的默认构造函数可以完成任务的情况下，我们也可以强制编译器生成默认构造函数：

//强制编译器生成默认构造
vector() = default;

析构函数

析构函数没有值得注意的地方，释放空间，然后将三个指针置空就好。

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

size和capacity函数

size()：

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

capacity()：

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

加上const之后无论是普通对象还是const对象都可以调用。

reserve函数

reserve函数一般是只扩不缩的，在进行扩容前我们可以检查n是否大于capacity()，如果大于我们再进行扩容。

void reverse(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		//将旧空间数据拷贝到新空间
		if (_start)//不为空再进行
		{
			memcpy(tmp, _start, sizeof(T) * size());
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + size();
		_endofstorage = _start + n;
	}
}

在函数中，我们首先动态申请n个大小的空间，我们挪动数据用到了memcpy，然后我们将旧空间释放。

这是我们初步实现的reserve函数，其实此时已经出现错误了。在_finish进行更改的位置，进行更改时我们再次调用了size()，此时_start是新空间的地址，而_finish是旧空间的地址，此时计算出的size()绝对是错误的，这就导致了，我们_finish无法正确修改，这里更正也很简单，我们要的是旧空间的size()，我们只需要提前储存它就好了。

再次更改后的reserve函数：

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);
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + old_size;
		_endofstorage = _start + n;
	}
}

注意：此时的函数基本上功能已经齐全了，但它在某些场景下还是不能胜任，由于我们目前没有合适的场景，所以我们会在后面进行讲解。

push_back函数

在实现这个函数时，我们需要考虑空间是否足够的问题，如果空间不够(_finish == _endofstorage)时，我们就要进行扩容操作。

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

pop_back函数

我们需要考虑是不是为空，为空就不能进行删除了。我们可以再单独实现一个empty函数。

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

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

operator[]

为了能够更方便的读数据我们要将operator[]实现一下。

我们要判断要访问的数据位置是否合法，所以可以使用assert断言，同时包含<assert.h>头文件。

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

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

begin和end

为了能够使用范围for，我们需要提供begin和end函数。同时为了能够适用普通对象和const对象，我们需要分别用普通迭代器和const迭代器实现两种。

typedef T* iterator;
typedef const T* const_iterator;

begin:

iterator begin()
{
	return _start;
}

const_iterator begin() const
{
	return _start;
}

end：

iterator end()
{
	return _finish;
}

const_iterator end() const
{
	return _finish;
}

测试

如此一来我们的基本成员函数就实现完成了，我们来测试一下。

void test1()
{
	VEC::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);

	for (auto i = 0;i < v.size();i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.pop_back();
	v.pop_back();
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

测试结果：

测试结果正确，和我们的预期一致。

2.打印函数

由于我们之后要频繁的打印所以我们可以实现一个打印函数Print，这样就方便许多。

由于我们可能会使用std里面的vector和VEC里面的vector，所以我们可以使用函数模板来实现这个打印函数，这样可以适配所有的场景，不用重载过多的打印函数。

//泛型 函数模板
template<class Container>
void Print(const Container& v)
{
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

这样Container可以是std::vector<T>和VEC::vector<T>，适配所有场景。

2.2 insert函数

我们的insert主要实现第一个。函数的主要目的是在pos位置插入一个数据x。

• 我们首先要保证pos是合法的，可以使用断言判断。
• 我们要考虑扩容问题，如果空间不够，我们就需要调用reserve进行扩容。
• 如果进行扩容了，就会产生新的问题，此时pos所处的位置仍旧是扩容之前的位置，如果不更改pos后续挪动数据的操作就无法进行，所以我们要在扩容后更改pos，如何更改呢？我们可以在扩容之前就记录pos相对于_start的距离len，然后在扩容后，进行pos = _start + len即可。

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

	return pos;
}

这就是我们实现的insert函数。

测试

我们既然已经实现了insert函数，我们可以测试一下它。

void test2()
{
	VEC::vector<int> v;
	v.push_back(3);
	v.push_back(7);
	v.push_back(5);
	v.push_back(2);
	Print(v);
	v.insert(v.begin() + 2, 100);
	Print(v);
}

测试结果：

可以看出是正确的。

迭代器失效问题

迭代器失效是一个很重要的问题，我们通过一段代码来引入问题。

假设我们要在值为x的地方插入数据，我们知道C++标准库中有find函数，我们可以通过它来找到位置。

void test3()
{
	VEC::vector<int> v;
	v.push_back(3);
	v.push_back(7);
	v.push_back(5);
	v.push_back(2);
	Print(v);
	int x; cin >> x;
	auto it = find(v.begin(), v.end(), x);
	if (it != v.end())
	{
		v.insert(it, x * 10);
		//这时it还能继续使用吗？
		*it = 5000;
	}
	Print(v);
}

大家可以仔细研究一下上面的这段代码。

结果：

其实观察结果我们也知道it失效了，因为20没有更改成为5000，在我们的程序中当是4个字符时，就一定会扩容，所以地址一更换，it就会失效，此时如果你在进行使用，就会导致很多未知、严重的问题，如果这个it它和余额沾边，你后续又继续使用了，那将会非常严重。

注意：C++标准中没有规定vector的扩容规则，不同编译器它所实现的扩容规则也不同，所以我们不知道它会在什么时候扩容，所以我们要认为insert之后，it一定失效，不能再使用了。如果要使用你可以更新it的位置，insert的返回值就是it的最新位置。

2.3 erase函数

我们只实现第一个erase函数。

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

	return pos;
}

测试：

void test4()
{
	VEC::vector<int> v;
	v.push_back(3);
	v.push_back(7);
	v.push_back(5);
	v.push_back(2);
	Print(v);
	v.erase(v.begin());
	Print(v);
	v.erase(v.begin() + 2);
	Print(v);
}

测试结果：

测试结果没有问题。

迭代器失效问题

erase之后会涉及到会发生元素挪动，由于元素位置发生了变动，原本指向被删除元素以及其后元素的迭代器，所指向的内存位置就不再正确，从而导致迭代器失效，所以我们要认为erase之后迭代器就失效了，因此正确的使用方法是使用erase返回的有效迭代器。

2.4 resize函数

resize函数的内部实现分为n大于size和n小于等于size两种，前者扩容，后者缩容或不变。

我们观察上面图片就可以发现第二个参数是给了缺省值的，我们也可以使用匿名对象T()来给缺省值。有人会疑问，那内置类型(如int、double等等)还能使用吗？

注意：C++为了适配，已经将内置类型做了升级，内置类型也有了构造函数、析构函数。

内置类型有构造函数之后，就可以进行这些操作：

int k=0;
int a=int();
int b(1);

resize:

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

测试

void test5()
{
	VEC::vector<int> v;
	v.push_back(3);
	v.push_back(7);
	v.push_back(5);
	v.push_back(2);
	Print(v);
	v.resize(6, 1);
	Print(v);
	v.resize(10, 10);
	Print(v);
	v.resize(5);
	Print(v);
}

测试结果：

和预期结果一致。

2.5 拷贝构造函数

拷贝构造函数就比较简单了，我们只需要获取和v一样大的空间，一样的值就好了。

vector(const vector<T>& v)
{
	//获得和v一样大的空间一样多的值
	reserve(v.capacity());
	for (auto& e : v)
	{
		push_back(e);
	}
}

2.6 initializer_list

我们在平常使用vector的时候经常会这样使用：

std::vector<int> v1 = { 1,2,3,4 };
std::vector<int> v2 = { 2,5,6,7,8,1,2,3,9,10 };

这就涉及到了initializer_list，包含在<initializer_list>头文件中：

initializer_list相当于来了一块空间将数组中的数据存储了起来，从上图中我们可以看到，它有size、begin和end函数，所以可以支持范围for。

那我们为了支持这样的写法我们可以实现一个这样的构造函数。

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

这样我们就支持开头那样的初始化了。

2.7 赋值重载函数

赋值重载函数我们就和string的模拟实现一样，使用现代写法实现。

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

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

这里的过程就是首先进行拷贝构造构造出目标v，然后将v的三个指针变量交换过来即可。

2.8 用迭代器区间进行构造

这是库里面的做法，是使用模板函数进行实现的，这样操作的好处是可以适配各种场景，可以使用任意类型容器进行初始化，例如vector<int>可以使用string类型的迭代器区间进行初始化。

为了达成这样的目标我们也可以这样进行模拟实现。

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

2.5至2.8测试

void test6()
{
	VEC::vector<int> v1;
	v1.push_back(1);
	v1.push_back(3);
	v1.push_back(5);
	v1.push_back(2);
	v1.push_back(7);
	Print(v1);

	VEC::vector<int> v2(v1);
	Print(v2);
	VEC::vector<int> v3 = { 1,5,2,3,7,6,4 };
	VEC::vector<int> v4 = { 2,4,5,8,9,0,1,2,3,4,6,100,8,4,3,2,1 };
	Print(v3);
	Print(v4);

	string s("hello world!");
	VEC::vector<char> c(s.begin(), s.end());
	Print(s);
}

测试结果：

和我们的预期结果一致。

2.9 n个T类型的值进行构造

因为类型多样所以我们可以重载很多个这样的构造函数，这里重载两个进行举例，函数内部又可以调用resize进行快速实现功能。

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

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

测试

void test7()
{
	VEC::vector<int> v1(5, 1);
	Print(v1);
	VEC::vector<size_t> v2((size_t)10, (size_t)1);
	Print(v2);
}

测试结果：

如何处理乱调用造成的错误

当我们进行如下测试时，就会发生错误：

void test8()
{
	VEC::vector<size_t> v(10, 1);
	Print(v);
}

我们的T现在是size_t，这就使得我们之前写的两个构造函数中一个是(int,size_t)，另一个是(size_t,size_t)，而我们现在的需求是(int,int)，此时我们实现的两个函数都不够匹配，这就是一种乱调用，当你调试时你会发现它最终会调用用迭代器区间进行构造的构造函数，导致报出非法的间接寻址这一错误，最终调用到的函数如下图。

为了处理这种错误，vs使用了一种很小众且超纲的处理方法，它在函数模板中添加了一些东西，最终变成了这样：

template <class InputIterator
		, std::enable_if_t<std::_Is_iterator_v<InputIterator>, int> = 0>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

添加的std::enable_if_t<std::_Is_iterator_v<InputIterator>, int> = 0是判断传入的是不是迭代器类型，如果是就进行函数模板实例化，如果不是，就不再进行实例化，大家作为了解即可。

最终程序正常运行：

2.10 深层次的深拷贝问题

我们到此为止vector容器已经模拟实现的差不多了，在前面讲reserve的时候我曾说哪里还遗留了一个问题，就是这个问题，下面我们一起来看一下这段代码。

void test9()
{
	VEC::vector<string> v;
	v.push_back("xxxxxxxxxxxxxxxxxxxx");
	v.push_back("xxxxxxxxxxxxxxxxxxxx");
	v.push_back("xxxxxxxxxxxxxxxxxxxx");
	v.push_back("xxxxxxxxxxxxxxxxxxxx");
	Print(v);
}

在这个测试用例中我们使用了vector<string>，并且尾插了4个字符串，我们这时来看看结果。

这时的结果是符合我们的预期的。

那我们再来尾插一个看一下结果。

现在程序出问题了，非零返回。为什么前4个是一堆乱码呢？

我们来分析一下这段代码，比起尾插4个，尾插5个多了一个环节，就是扩容，我们可以大胆猜想就是扩容的环节导致代码出了问题，接下来我们来调试代码，重点关注扩容环节reserve。

我们调试到了扩容函数的关键环节挪动数据,删除原来的数据，我们发现在挪动数据之后，再执行删除操作，tmp数组和_start数组中的数据全都消失了。

从这幅图片中可以看出_start数组的第一个元素的地址和tmp数组中第一个元素的地址相同，也就是说它们指向同一块空间，我们再结合下面进行分析。

我们知道在string的模拟实现的过程中，一共有三个成员变量_str、_size、_capacity，其中_str是char类型的指针，而memcpy实现的是浅拷贝，也就是会将_start的这三个变量的值赋给tmp中的三个变量，这就导致_start和tmp中的_str指向的是同一块空间，这时再进行_start空间的delete[]操作，自然两个数组中的数据都会消失，之后打印操作又涉及到了空指针的解引用，导致程序发生错误，非零返回。

在这种情况下，只要执行delete[] _start;，tmp中的数据也会消失。关键原因还是在于执行了浅拷贝，而我们需要的是深拷贝，那该如何实现呢？

我们知道类类型中都有赋值重载，我们直接调用它的赋值重载(s1 = s2;)就可以完成深拷贝了，所以reserve函数可以这样修改：

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

再次执行测试：

这次结果和我们的预期相一致。

这样tmp[i] = _start[i];的修改对于int这样的内置类型可以完成浅拷贝，而对于string这样的类型，可以赋值调用operator=完成深拷贝。

至此，我们vector的模拟实现就完成了！

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～