从零开始：实现你的第一个 C++ Vector

码农世界 2024-06-14 后端 84 次浏览 0个评论

1.引言

我们要模拟实现vector首先要去看一看vector的底层长什么样子。

iterator _start;		// 指向数据块的开始
iterator _finish;		// 指向有效数据的尾
iterator _endOfStorage;  // 指向存储容量的尾

在string中我们通常都是用下标进行访问的，但是在vector中我们大多数成员函数都是用迭代器进行访问的，所以我们就用迭代器实现一个vector，从string中我们就可以看出迭代器很方便，在后面的list中迭代器就更常见了，上面的_start不难看出是指向首地址的迭代器，_finish是指向末尾的迭代器，而_endOfStorage是指向总容量的最后的迭代器。

用迭代器实现我们首先就要定义迭代器，在vector中迭代器也是用指针定义的。下面展示迭代器的定义。

typedef T* iterator;//迭代器
typedef const T* const_iterator;//const类型的迭代器

有了上面的知识铺垫我们就可以实现一个简单的vector了，接下来我们就来讲解vector中的成员函数。

2.构造函数和析构函数还有赋值拷贝

2.1无参构造

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

2.2有参构造（用一个value初始化n个空间）

vector(size_t n, const T& value = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _endOfStorage(nullptr)
{
	reserve(n);
	for (size_t i = 0;i < n;i++)
	{
		push_back(value);
	}
}

首先，第一个参数应该不难理解，第二个参数（const T& value = T()）这里解释一下，经过我们前面类和对象的学习，我们很容易知道T()是一个零时对象，并且它没有名字，这里就出现了一个问题，前面类和对象中讲到的，临时对象应该在同一个语句中进行的，为什么这里还能进行赋值操作呢？

原因：因为我们前面引用了一个value，后面的临时对象的生命周期得到了延续，临时对象的生命周期和value的生命周期相同，又因为临时对象具有常性，所以这里我们在参数中就应该用const修饰。

这里我并没有实现reserve，reserve是预扩容函数，我们后面实现，还有一个push_back也没有实现，后面我们也将实现这个函数，这里先复用。

这里我们还需要重载一个int类型的有参构造函数

//重载一个int类型的构造函数
vector(int n, const T& value = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _endOfStorage(nullptr)
{
	reserve(n);
	for (int i = 0;i < n;i++)
	{
		push_back(value);
	}
}

理论上将，提供了vector(size_t n, const T& value = T())之后，vector(int n, const T& value = T())就不需要提供了，但是对于：vector v(10, 5);

编译器在编译时，认为T已经被实例化为int，而10和5编译器会默认其为int类型就不会走vector(size_t n, const T& value = T())这个构造方法，最终选择的是：vector(InputIterator first, InputIterator last)因为编译器觉得区间构造两个参数类型一致，因此编译器就会将InputIterator实例化为int但是10和5根本不是一个区间，编译时就报错了故需要增加该构造方法。

2.3迭代区间构造

//迭代区间构造
template
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _endOfStorage(nullptr)
{
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

首先看到这个模版template为什么我们要实现成一个新的模版类的函数呢？

原因：因为我们实现成相同的上面的模版类型的话，就只能使用自己的迭代器，如果我们使用了另一个新的模版的话就可以使用别的自定义类型的迭代器了，比如string的迭代器，也可以使用string的迭代器进行迭代区间构造。

2.4拷贝构造

//拷贝构造函数
vector(const vector& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endOfStorage(nullptr)
{
	_start = new T[v.capacity()];
	for (size_t i = 0;i < v.size();i++)
	{
		_start[i] = v._start[i];
	}
	_finish = _start + v.size();
	_endOfStorage = _start + v.capacity();
}

拷贝构造函数和string类中的实现方式相似，只需要在起始位置也就是_start的位置开一个空间和v意向大小的空间即可，然后把v中的数据一个一个拷贝过去，为什么不能用memcpy呢，因为memcpy是浅拷贝，而浅拷贝只会拷贝值，对内置类型很友好，但是对于自定义类型，特别是我们手动开空

间的类型，我们就很难搞，所以只能自己写一个，自己写一个深拷贝。

2.5赋值拷贝

//赋值拷贝函数
vector& operator=(vector v)
{
	assign(v.begin(), v.end());
	return *this;
}

注意我们上面用的就是下面的迭代区间去赋值的。

std::vector 中的 assign 函数用于替换向量中的元素。它有几个重载版本，允许用不同的方法来指定新的内容。

下面我们来实现三个版本的assign函数

2.5.1int版本

void assign(int n, const T& val)
{
	T* tmp = new T[n];
	for (int i = 0;i < n;i++)
	{
		tmp[i] = val;
	}
	delete[] _start;
	_start = tmp;
	_finish = _endOfStorage = tmp + n;
}

2.5.2size_t版本

void assign(size_t n, const T& val)
{
	T* tmp = new T[n];
	for (size_t i = 0;i < n;i++)
	{
		tmp[i] = val;
	}
	delete[] _start;
	_start = tmp;
	_finish = _endOfStorage = tmp + n;
}

2.5.3迭代区间版本

void assign(InputIterator first, InputIterator last)
{
	size_t sz = last - first;
	T* tmp = new T[sz];
	for (int i = 0;i < sz;i++)
	{
		tmp[i] = *(first + i);
	}
	_start = tmp;
	_finish = _endOfStorage = _start + sz;
}

2.6析构函数

//析构函数
~vector()
{
	delete[] _start;
	_start = _finish = _endOfStorage = nullptr;
}

析构函数只需要释放开辟的空，然后把三个迭代器指向nullptr即可

3.成员函数

3.1迭代器

提供两个版本的迭代器，一个const版本的一个就是普通版本的迭代器

//迭代器
iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}
const_iterator cbegin() const
{
	return _start;
}
const_iterator cend() const
{
	return _finish;
}

3.2容量大小和空间大小

//返回有效数据大小
size_t size() const
{
	return _finish - _start;
}
//返回总容量大小
size_t capacity() const
{
	return _endOfStorage - _start;
}

3.3判空

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

3.4预开辟空间

//预开辟空间
void reserve(size_t n)
{
	size_t sz = size();
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)
		{
			for (size_t i = 0;i < sz;i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_endOfStorage = _start + n;
	}
}

在开辟之前我们要看看，是否需要开辟，如果预开辟的空间比实际空间小则不需要进行任何操作，如果比原本的空间大则开辟空间，由于C++没有像realloc一样的扩容的函数，所以我们直接手动开辟一个新的空间然后再拷贝原来的数据，更新成员变量即可。

3.5size大小的改变

//改变size的大小
void resize(size_t n, const T& value = T())
{
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		if (n > capacity())
		{
			reserve(n);
		}
		while (_finish != _endOfStorage)
		{
			*_finish = value;
			_finish++;
		}
	}
}

C++中resize可以缩容，所以当n比实际的有效数据小的时候，可以直接将后面的数据截取了，更新_finish，如果大于容量的话就需要开辟空间了，然后将后面的空的空间初始化为指定的值，更新_finish和另一个成员变量。

3.6operator[]重载

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

3.7返回首或者尾的元素

//返回第一个元素
T& front()
{
	return *_start;
}
const T& front()const
{
	return *_start;
}
//返回最后一个值
T& back()
{
	return _start[size() - 1];
}
const T& back()const
{
	return _start[size() - 1];
}

3.8尾插一个值和尾删一个值

//尾插一个值
void push_back(const T& x)
{
	if (_finish == _endOfStorage)
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}
	*_finish = x;
	_finish++;
}
//尾删一个值
void pop_back()
{
	assert(_finish != _start);
	_finish--;
}

3.9交换函数

考虑到效率我们直接交换成员变量间的指向即可

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

3.91指定位置的插入

//随机位置插入
iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	if (_finish == _endOfStorage)
	{
		size_t len = _start - pos;
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
		pos = _start + len;
	}
	iterator end = _finish;
	while (end != pos)
	{
		*end = *(end - 1);
		end--;
	}
	*pos = x;
	_finish++;
	return pos;
}

对于指定位置的插入，首先我们应该检查空间是否够用，然后我们还需要注意的是，万一我们扩容，对于pos还是指向以前的空间上的某个地址，但是我们的空间是新开的，所以这里我们必须在开辟空间的时候更新pos位置，这个明白之后，后面的插入还是正常的移动数据，然后在指定位置插入数据。

3.9.2指定位置的删除

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

3.9.3缩容

//缩容
void shrink_to_fit()
{
	size_t sz = size();
	T* tmp = new T[sz];
	for (size_t i = 0;i < sz;i++)
	{
		tmp[i] = _start[i];
	}
	delete[] _start;
	_start = tmp;
	_finish = _start + sz;
	_endOfStorage = _start + sz;
}

对于缩容我们只需要重新开辟空间，然后拷贝数据就可以了，把多出来的空间给删除了。

3.9.4清除

void clear()
{
	_finish = _start;
}

4.完整代码

#pragma once
#pragma once
#include 
using namespace std;
#include 
namespace lyrics
{
	template//模版
	class vector
	{
	public:
		typedef T* iterator;//迭代器
		typedef const T* const_iterator;//const类型的迭代器
		//构造函数
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{}
		//有参构造函数
		vector(size_t n, const T& value = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			reserve(n);
			for (size_t i = 0;i < n;i++)
			{
				push_back(value);
			}
		}
		//重载一个int类型的构造函数
		vector(int n, const T& value = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			reserve(n);
			for (int i = 0;i < n;i++)
			{
				push_back(value);
			}
		}
		//迭代区间构造
		template
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		//拷贝构造函数
		vector(const vector& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			_start = new T[v.capacity()];
			for (size_t i = 0;i < v.size();i++)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_endOfStorage = _start + v.capacity();
		}
		//赋值拷贝函数
		vector& operator=(vector v)
		{
			assign(v.begin(), v.end());
			return *this;
		}
		//析构函数
		~vector()
		{
			delete[] _start;
			_start = _finish = _endOfStorage = nullptr;
		}
		//迭代器
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const_iterator cbegin() const
		{
			return _start;
		}
		const_iterator cend() const
		{
			return _finish;
		}
		//返回有效数据大小
		size_t size() const
		{
			return _finish - _start;
		}
		//返回总容量大小
		size_t capacity() const
		{
			return _endOfStorage - _start;
		}
		//判空
		bool empty() const
		{
			return _finish == _start;
		}
		//预开辟空间
		void reserve(size_t n)
		{
			size_t sz = size();
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0;i < sz;i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + sz;
				_endOfStorage = _start + n;
			}
		}
		//改变size的大小
		void resize(size_t n, const T& value = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}
				while (_finish != _endOfStorage)
				{
					*_finish = value;
					_finish++;
				}
			}
		}
		//[]重载
		T& operator[](size_t pos)
		{
			return _start[pos];
		}
		const T& operator[](size_t pos)const
		{
			return _start[pos];
		}
		//返回第一个元素
		T& front()
		{
			return *_start;
		}
		const T& front()const
		{
			return *_start;
		}
		//返回最后一个值
		T& back()
		{
			return _start[size() - 1];
		}
		const T& back()const
		{
			return _start[size() - 1];
		}
		//尾插一个值
		void push_back(const T& x)
		{
			if (_finish == _endOfStorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = x;
			_finish++;
		}
		//尾删一个值
		void pop_back()
		{
			assert(_finish != _start);
			_finish--;
		}
		//vector之间的交换
		void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endOfStorage, v._endOfStorage);
		}
		//随机位置插入
		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _endOfStorage)
			{
				size_t len = _start - pos;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish;
			while (end != pos)
			{
				*end = *(end - 1);
				end--;
			}
			*pos = x;
			_finish++;
			return pos;
		}
		//随机位置的删除
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			iterator first = pos + 1;
			while (first != _finish)
			{
				*(first - 1) = *first;
				first++;
			}
			_finish--;
			return pos;
		}
		template
		void assign(InputIterator first, InputIterator last)
		{
			size_t sz = last - first;
			T* tmp = new T[sz];
			for (int i = 0;i < sz;i++)
			{
				tmp[i] = *(first + i);
			}
			_start = tmp;
			_finish = _endOfStorage = _start + sz;
		}
		void assign(size_t n, const T& val)
		{
			T* tmp = new T[n];
			for (size_t i = 0;i < n;i++)
			{
				tmp[i] = val;
			}
			delete[] _start;
			_start = tmp;
			_finish = _endOfStorage = tmp + n;
		}
		void assign(int n, const T& val)
		{
			T* tmp = new T[n];
			for (int i = 0;i < n;i++)
			{
				tmp[i] = val;
			}
			delete[] _start;
			_start = tmp;
			_finish = _endOfStorage = tmp + n;
		}
		//缩容
		void shrink_to_fit()
		{
			size_t sz = size();
			T* tmp = new T[sz];
			for (size_t i = 0;i < sz;i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
			_start = tmp;
			_finish = _start + sz;
			_endOfStorage = _start + sz;
		}
		void clear()
		{
			_finish = _start;
		}
	private:
		iterator _start;		// 指向数据块的开始
		iterator _finish;		// 指向有效数据的尾
		iterator _endOfStorage;  // 指向存储容量的尾
	};
}

5.总结

通过这篇博客，我们深入探讨了如何模拟实现 C++ 中的 std::vector 容器。从动态内存管理到基本功能的实现，我们逐步构建了一个简单而功能强大的向量类。

在这个过程中，我们学习了动态内存分配、指针操作、拷贝控制等 C++ 核心概念，并将它们应用于实际的容器实现中。通过手动实现 push_back、pop_back、resize 等函数，我们深入了解了向量的内部工作原理。

这篇博客不仅仅是一个容器的模拟实现，更是一个 C++ 学习的过程。通过动手实践，我们加深了对语言特性和编程技巧的理解，提高了自己的编程能力。

当然，我们的模拟实现还远远不能与标准库中的 std::vector 相提并论。标准库的实现经过了大量的优化和测试，在性能、稳定性和通用性上都远远超出了我们的模拟版本。但是，通过这个实践，我们不仅能更好地理解标准库中容器的工作原理，也能更深入地理解 C++ 语言本身。

在未来的学习和实践中，我们可以进一步探索容器的其他功能，比如迭代器、算法等，也可以尝试实现其他常用容器，比如链表、栈、队列等，从而不断提升自己的编程水平。

希望这篇博客能为你带来收获，也希望你能在学习 C++ 的道路上不断前行，探索更多有趣和有挑战的领域！

转载请注明来自码农世界，本文标题：《从零开始：实现你的第一个 C++ Vector》

码农世界 37815篇文章站点微博

每一天，每一秒，你所做的决定都会改变你的人生！

发表评论取消回复

评论列表（暂无评论，84人围观）参与讨论

码农世界管理员

从零开始：实现你的第一个 C++ Vector

1.引言

2.构造函数和析构函数还有赋值拷贝

2.1无参构造

2.2有参构造（用一个value初始化n个空间）

2.3迭代区间构造

2.4拷贝构造

2.5赋值拷贝

2.5.1int版本

2.5.2size_t版本

2.5.3迭代区间版本

2.6析构函数

3.成员函数

3.1迭代器

3.2容量大小和空间大小

3.3判空

3.4预开辟空间

3.5size大小的改变

3.6operator[]重载

3.7返回首或者尾的元素

3.8尾插一个值和尾删一个值

3.9交换函数

3.91指定位置的插入

3.9.2指定位置的删除

3.9.3缩容

3.9.4清除

4.完整代码

5.总结

发表评论取消回复

还没有评论，来说两句吧...

文章目录

码农世界管理员

从零开始：实现你的第一个 C++ Vector

1.引言

2.构造函数和析构函数还有赋值拷贝

2.1无参构造

2.2有参构造（用一个value初始化n个空间）

2.3迭代区间构造

2.4拷贝构造

2.5赋值拷贝

2.5.1int版本

2.5.2size_t版本

2.5.3迭代区间版本

2.6析构函数

3.成员函数

3.1迭代器

3.2容量大小和空间大小

3.3判空

3.4预开辟空间

3.5size大小的改变

3.6operator[]重载

3.7返回首或者尾的元素

3.8尾插一个值和尾删一个值

3.9交换函数

3.91指定位置的插入

3.9.2指定位置的删除

3.9.3缩容

3.9.4清除

4.完整代码

5.总结

Visual Studio 连接 MySQL 数据库 实现数据库的读写（C++）

[工业自动化-1]：PLC架构与工作原理

网络编程（六）TCP并发服务器

Vue3、Element Plus使用v-for循环el-form表单进行校验

Ceph: vdbench 测试ceph存储rbd块设备

linux如何部署前端项目和安装nginx

Windows OpenVPN的安装之服务器自动启动连接

服务器数据恢复—KVM虚拟机被误删除如何恢复虚拟磁盘文件？

发表评论取消回复

还没有评论，来说两句吧...

文章目录

Visual Studio 连接 MySQL 数据库实现数据库的读写（C++）