精通C++ STL（四）：vector的模拟实现

目录

vector各函数接口总览

vector当中的成员变量介绍

默认成员函数 

        构造函数1

        构造函数2

        构造函数3

        拷贝构造函数

        赋值运算符重载函数

        析构函数

迭代器相关函数

        begin和end

容量和大小相关函数

        size和capacity

        reserve

        resize

        empty

修改容器内容相关函数

        push_back

        pop_back

        insert

        erase

        swap

访问容器相关函数

        operator[ ]

vector各函数接口总览

namespace Russ_Leo
{
	//模拟实现vector
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		//默认成员函数
		vector();                                           //构造函数
		vector(size_t n, const T& val);                     //构造函数
		template<class InputIterator>                      
		vector(InputIterator first, InputIterator last);    //构造函数
		vector(const vector<T>& v);                         //拷贝构造函数
		vector<T>& operator=(const vector<T>& v);           //赋值运算符重载函数
		~vector();                                          //析构函数

		//迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;

		//容量和大小相关函数
		size_t size()const;
		size_t capacity()const;
		void reserve(size_t n);
		void resize(size_t n, const T& val = T());
		bool empty()const;

		//修改容器内容相关函数
		void push_back(const T& x);
		void pop_back();
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void swap(vector<T>& v);

		//访问容器相关函数
		T& operator[](size_t i);
		const T& operator[](size_t i)const;

	private:
		iterator _start;        //指向容器的头
		iterator _finish;       //指向有效数据的尾
		iterator _endofstorage; //指向容器的尾
	};
}

vector当中的成员变量介绍

        在 vector 中有三个成员变量：_start、_finish 和 _endofstorage。

        _start指向容器的头，_finish指向容器当中有效数据的尾，_endofstorage指向整个容器的尾。 

默认成员函数 

        构造函数1

        vector 首先支持一个无参的构造函数。对于这个构造函数，我们可以直接将对象的三个成员变量都初始化为 空指针。

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

        构造函数2

        此外，vector 还支持使用一段迭代器区间来构造对象。由于这个迭代器区间可以是其他容器的迭代器区间，也就是说，该函数接收到的迭代器类型是不确定的，因此我们需要将该构造函数设计为一个函数模板。在函数体内，我们只需将该迭代器区间的数据逐个尾插到容器中即可。

//构造函数2
template<class InputIterator> //模板函数
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	//将迭代器区间在[first,last)的数据一个个尾插到容器当中
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

        构造函数3

        另外，vector 还支持构造包含n个值为val的容器。对于这个构造函数，我们可以先使用 reserve 函数将容器的容量设置为 n，然后使用 push_back 函数尾插 n 个值为 val 的数据到容器中。

//构造函数3
vector(size_t n, const T& val)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(n); //调用reserve函数将容器容量设置为n
	for (size_t i = 0; i < n; i++) //尾插n个值为val的数据到容器当中
	{
		push_back(val);
	}
}

注意：

1. 该构造函数知道需要存储 n 个数据的空间，因此最好使用 reserve 函数一次性开辟足够的空间，避免在调用 push_back 函数时多次增容，从而降低效率。
2. 该构造函数还需要实现两个重载函数。

vector(long n, const T& val)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(n); //调用reserve函数将容器容量设置为n
	for (size_t i = 0; i < n; i++) //尾插n个值为val的数据到容器当中
	{
		push_back(val);
	}
}
vector(int n, const T& val)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(n); //调用reserve函数将容器容量设置为n
	for (int i = 0; i < n; i++) //尾插n个值为val的数据到容器当中
	{
		push_back(val);
	}
}

        可以看到，这两个重载函数的区别在于参数 n 的类型不同，但这是必要的。否则，当我们使用以下代码时，编译器会优先匹配构造函数2。 

vector<int> v(5, 7); //调用构造函数3 ？？？

        并且，由于构造函数2中对参数 first 和 last 进行了解引用操作，而 int 类型无法进行解引用操作，这会导致报错。 

        拷贝构造函数

        vector 的构造函数涉及深拷贝问题，这里提供两种深拷贝的写法：

写法一：传统写法

        传统的拷贝构造方法思想最为直观：首先开辟一块与该容器大小相同的空间，然后将容器中的数据逐个拷贝过来，最后更新 _finish 和 _endofstorage 的值。

//传统写法
vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
	for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
	{
		_start[i] = v[i];
	}
	_finish = _start + v.size(); //容器有效数据的尾
	_endofstorage = _start + v.capacity(); //整个容器的尾
}

注意：在将容器中的数据逐个拷贝时，不能使用 memcpy 函数。虽然当 vector 存储的数据是内置类型或无需深拷贝的自定义类型时，使用 memcpy 函数没有问题，但当 vector 存储的数据是需要进行深拷贝的自定义类型时，memcpy 的弊端就显现出来了。例如，当 vector 存储的数据是 string 类时。

        并且，vector 中存储的每一个 string 都指向其自身所存储的字符串。 

        如果此时我们使用 memcpy 函数进行拷贝构造，那么拷贝构造出来的 vector 中存储的每个 string 的成员变量值，将与被拷贝的 vector 中存储的每个 string 的成员变量值相同。这意味着，两个 vector 中每个对应的 string 成员都指向同一个字符串空间。 

        显然，这种情况不是我们期望的结果。那么给定的代码是如何解决这个问题的呢？ 

        代码中看似使用普通的 = 将容器中的数据逐个拷贝过来，但实际上是调用了存储元素的赋值运算符重载函数。对于 string 类，其赋值运算符重载函数实现了深拷贝，因此拷贝的结果如下： 

        总结一下：如果 vector 中存储的元素类型是内置类型（如 int）或浅拷贝的自定义类型（如 Date），使用 memcpy 函数进行拷贝构造是没问题的。然而，如果 vector 中存储的元素类型是深拷贝的自定义类型（如 string），则使用 memcpy 函数将无法达到预期效果。 

写法二：现代写法

        拷贝构造函数的现代写法相对简单，使用范围 for（或其他遍历方式）对容器 v 进行遍历，在遍历过程中将容器 v 中存储的数据逐个尾插到新容器中即可。

//现代写法
vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同
	for (auto e : v) //将容器v当中的数据一个个尾插过来
	{
		push_back(e);
	}
}

注意：在使用范围 for 对容器 v 进行遍历时，变量 e 就是每一个数据的拷贝，然后将 e 尾插到构造出来的容器中。即使容器 v 中存储的数据是 string 类，在 e 拷贝时也会自动调用 string 的拷贝构造函数（深拷贝），因此可以避免出现与使用 memcpy 时类似的问题。

        赋值运算符重载函数

        vector 的赋值运算符重载当然也涉及深拷贝问题，这里提供两种深拷贝的写法：

写法一：传统写法

        首先检查是否是给自己赋值，如果是，则无需进行操作。如果不是给自己赋值，则需先开辟一块与容器 v 大小相同的空间，然后将容器 v 中的数据逐个拷贝过来，最后更新 _finish 和 _endofstorage 的值。

//传统写法
vector<T>& operator=(const vector<T>& v)
{
	if (this != &v) //防止自己给自己赋值
	{
		delete[] _start; //释放原来的空间
		_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
		for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
		{
			_start[i] = v[i];
		}
		_finish = _start + v.size(); //容器有效数据的尾
		_endofstorage = _start + v.capacity(); //整个容器的尾
	}
	return *this; //支持连续赋值
}

注意：这里和拷贝构造函数的传统写法类似，不能使用 memcpy 函数进行拷贝。

写法二：现代写法

        赋值运算符重载的现代写法相当简洁。首先，在右值传参时没有使用引用传参，因为这样可以间接调用 vector 的拷贝构造函数。然后，将这个通过拷贝构造得到的容器 v 与左值进行交换。此时，相当于完成了赋值操作，而容器 v 会在函数调用结束时自动析构。

//现代写法
vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数
{
	swap(v); //交换这两个对象
	return *this; //支持连续赋值
}

注意：赋值运算符重载的现代写法也是进行的深拷贝，只不过是通过调用 vector 的拷贝构造函数来实现深拷贝。在赋值运算符重载函数中，仅仅是将深拷贝出来的对象与左值进行了交换。

        析构函数

        对容器进行析构时，首先判断该容器是否为空容器。如果为空，则无需进行析构操作；如果不为空，则需要先释放容器存储数据的空间，然后将容器的各个成员变量设置为空指针。

//析构函数
~vector()
{
	if (_start) //避免对空指针进行释放
	{
		delete[] _start; //释放容器存储数据的空间
		_start = nullptr; //_start置空
		_finish = nullptr; //_finish置空
		_endofstorage = nullptr; //_endofstorage置空
	}
}

迭代器相关函数

        vector 中的迭代器实际上就是容器中存储数据类型的指针。

typedef T* iterator;
typedef const T* const_iterator;

        begin和end

        vector 中的 begin 函数返回容器的首地址，而 end 函数返回容器中有效数据的下一个数据的地址。

iterator begin()
{
	return _start; //返回容器的首地址
}
iterator end()
{
	return _finish; //返回容器当中有效数据的下一个数据的地址
}

        我们还需要重载一对适用于 const 对象的 begin 和 end 函数，使得 const 对象调用 begin 和 end 函数时，所得到的迭代器只能对数据进行读操作，而不能进行修改。 

const_iterator begin()const
{
	return _start; //返回容器的首地址
}
const_iterator end()const
{
	return _finish; //返回容器当中有效数据的下一个数据的地址
}

        此时，再来看 vector 使用迭代器的代码，就会发现其实它就是在使用指针遍历容器。 

vector<int> v(5, 3);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
	cout << *it << " ";
	it++;
}
cout << endl;

        现在我们实现了迭代器，实际上也就可以使用范围 for 遍历容器了，因为编译器在编译时会自动将范围 for 替换为迭代器的形式。 

vector<int> v(5, 3);
//范围for进行遍历
for (auto e : v)
{
	cout << e << " ";
}
cout << endl;

容量和大小相关函数

        size和capacity

        对照 vector 中三个成员遍历各自的指向，我们可以很容易得出当前容器中的有效数据个数和最大容量。

        由于两个指针相减的结果就是这两个指针之间对应类型的数据个数，因此 size 可以通过 _finish - _start 得到，而 capacity 可以通过 _endofstorage - _start 得到。 

size_t size()const
{
	return _finish - _start; //返回容器当中有效数据的个数
}
size_t capacity()const
{
	return _endofstorage - _start; //返回当前容器的最大容量
}

        reserve

reserve 规则：

1. 当 n 大于对象当前的 capacity 时，将 capacity 扩大到 n 或更大。
2. 当 n 小于对象当前的 capacity 时，不执行任何操作。

        reserve 函数的实现思路也很简单：首先判断所给的 n 是否大于当前容器的最大容量（否则无需进行任何操作）。如果需要扩展容量，直接开辟一块可以容纳 n 个数据的空间，然后将原容器中的有效数据拷贝到该空间中。接着，释放原容器存储数据的空间，并将新开辟的空间交给该容器进行维护。最后，更新容器中各个成员变量的值即可。

void reserve(size_t n)
{
	if (n > capacity()) //判断是否需要进行操作
	{
		size_t sz = size(); //记录当前容器当中有效数据的个数
		T* tmp = new T[n]; //开辟一块可以容纳n个数据的空间
		if (_start) //判断是否为空容器
		{
			for (size_t i = 0; i < sz; i++) //将容器当中的数据一个个拷贝到tmp当中
			{
				tmp[i] = _start[i];
			}
			delete[] _start; //将容器本身存储数据的空间释放
		}
		_start = tmp; //将tmp所维护的数据交给_start进行维护
		_finish = _start + sz; //容器有效数据的尾
		_endofstorage = _start + n; //整个容器的尾
	}
}

在 reserve 函数的实现中，有两个地方需要特别注意：

• 在进行操作之前，需要提前记录当前容器中有效数据的个数。因为最后需要更新 _finish 指针的指向，而 _finish 指针的指向等于 _start 指针加上容器中有效数据的个数。如果 _start 指针的指向改变后再调用 size 函数，通过 _finish - _start 计算出的有效数据个数可能会得到一个随机值。

• 拷贝容器中的数据时，不能使用 memcpy 函数进行拷贝。你可能会认为，当 vector 中存储的是 string 时，虽然使用 memcpy 函数的 reserve 操作使得新容器与原容器中的每个对应的 string 成员都指向同一个字符串空间，但原容器存储数据的空间已经被释放，似乎只剩下一个容器维护这些字符串空间，这还会有什么影响。

        然而，不要忘了，当你释放原容器的空间时，原容器中的每个 string 在释放时会调用 string 的析构函数，从而释放其指向的字符串。因此，使用 memcpy 函数进行 reserve 操作的容器中的每个 string 所指向的字符串实际上是已经被释放的空间，访问该容器时会导致非法内存访问。

        因此，我们仍然需要使用 for 循环 将容器中的 string 一个个赋值过来，因为这样能够间接调用 string 的赋值运算符重载，实现 string 的深拷贝。 

        resize

resize 规则：

1. 当 n 大于当前的 size 时，将 size 扩大到 n，扩大的数据为 val，如果 val 未给出，则默认为容器所存储类型的默认构造函数所构造的值。
2. 当 n 小于当前的 size 时，将 size 缩小到 n。

        根据 resize 函数的规则，进入函数后，我们可以首先判断所给的 n 是否小于容器当前的 size。如果小于，则通过改变 _finish 的指向，直接将容器的 size 缩小到 n。否则，先判断容器是否需要增容，然后将扩大的数据赋值为 val。

void resize(size_t n, const T& val = T())
{
	if (n < size()) //当n小于当前的size时
	{
		_finish = _start + n; //将size缩小到n
	}
	else //当n大于当前的size时
	{
		if (n > capacity()) //判断是否需要增容
		{
			reserve(n);
		}
		while (_finish < _start + n) //将size扩大到n
		{
			*_finish = val;
			_finish++;
		}
	}
}

注意：在 C++ 中，内置类型也可以视作类，它们也有自己的默认构造函数。因此，在为 resize 函数的参数 val 设置缺省值时，可以设置为 T()。 

        empty

        empty 函数可以直接通过比较容器中的 _start 和 _finish 指针的指向来判断容器是否为空。如果这两个指针所指的位置相同，则该容器为空。函数可以直接通过比较容器中的 _start 和 _finish 指针的指向来判断容器是否为空。如果这两个指针所指的位置相同，则该容器为空。

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

修改容器内容相关函数

        push_back

        要进行尾插操作，首先需要判断容器是否已满。如果已满，则需要先进行增容，然后将数据尾插到 _finish 指向的位置，再将 _finish 递增。

//尾插数据
void push_back(const T& x)
{
	if (_finish == _endofstorage) //判断是否需要增容
	{
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍
		reserve(newcapacity); //增容
	}
	*_finish = x; //尾插数据
	_finish++; //_finish指针后移
}

        pop_back

        在进行尾删操作之前，也需要先判断容器是否为空。如果为空，则需要进行断言处理；如果不为空，则将 _finish 递减即可。

//尾删数据
void pop_back()
{
	assert(!empty()); //容器为空则断言
	_finish--; //_finish指针前移
}

        insert

        insert 函数可以在所给的迭代器 pos 位置插入数据。在插入数据之前，首先需要判断是否需要增容。如果需要增容，则先进行增容操作。接着，将 pos 位置及其之后的数据统一向后移动一位，以留出 pos 位置进行插入。最后，将数据插入到 pos 位置即可。

//在pos位置插入数据
void insert(iterator pos, const T& x)
{
	if (_finish == _endofstorage) //判断是否需要增容
	{
		size_t len = pos - _start; //记录pos与_start之间的间隔
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍
		reserve(newcapacity); //增容
		pos = _start + len; //通过len找到pos在增容后的容器当中的位置
	}
	//将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入
	iterator end = _finish;
	while (end >= pos + 1)
	{
		*end = *(end - 1);
		end--;
	}
	*pos = x; //将数据插入到pos位置
	_finish++; //数据个数增加一个，_finish后移
}

        注意：如果需要增容，则必须在增容前记录 pos 与 _start 之间的间隔。通过该间隔可以确定在增容后的容器中 pos 的新指向位置，否则 pos 可能仍指向原来已被释放的空间。 

        erase

        erase 函数可以删除所给迭代器 pos 位置的数据。在删除数据之前，需要判断容器是否为空。如果为空，则需要进行断言处理。删除数据时，直接将 pos 位置之后的数据统一向前移动一位，以覆盖 pos 位置的数据即可。

//删除pos位置的数据
iterator erase(iterator pos)
{
	assert(!empty()); //容器为空则断言
	//将pos位置之后的数据统一向前挪动一位，以覆盖pos位置的数据
	iterator it = pos + 1;
	while (it != _finish)
	{
		*(it - 1) = *it;
		it++;
	}
	_finish--; //数据个数减少一个，_finish前移
	return pos;
}

        swap

        swap 函数用于交换两个容器的数据。我们可以直接调用库中的 swap 函数，将两个容器中的各个成员变量进行交换即可。

//交换两个容器的数据
void swap(vector<T>& v)
{
	//交换容器当中的各个成员变量
	::swap(_start, v._start);
	::swap(_finish, v._finish);
	::swap(_endofstorage, v._endofstorage);
}

注意：在此处调用库中的 swap 函数时，需要在 swap 之前加上 ::（作用域限定符），以告诉编译器优先在全局范围寻找 swap 函数。否则，编译器可能会认为你调用的是你正在实现的 swap 函数（遵循就近原则）。 

访问容器相关函数

        operator[ ]

        vector 也支持使用 下标 [ ] 的方式对容器中的数据进行访问。实现时，直接返回对应位置的数据即可。

T& operator[](size_t i)
{
	assert(i < size()); //检测下标的合法性

	return _start[i]; //返回对应数据
}
const T& operator[](size_t i)const
{
	assert(i < size()); //检测下标的合法性

	return _start[i]; //返回对应数据
}

注意：重载运算符 [ ] 时，需要重载一个适用于 const 容器的版本，因为 const 容器通过 下标 [ ] 获取到的数据只允许进行读操作，不能对数据进行修改。