C++第二十一弹---vector深度剖析及模拟实现(上)

2024-06-01 13:37:21

✨个人主页：熬夜学编程的小林

????系列专栏：【C语言详解】【数据结构详解】【C++详解】

1、基本结构

2、默认成员函数

2.1、构造函数

2.2、析构函数

2.3、拷贝构造函数

2.3、赋值操作符重载

3、数据访问

4、迭代器获取

总结

1、基本结构

首先定义一个vector模版类，其中三个成员变量均为迭代器，且此处vector的迭代器是一个原生指针，我们这里为其定义别名iterator。

namespace lin 
{

	template<class T>//此处为类模板，实现不同数据类型的存储
	class vector
	{
	public:
        //vector迭代器为原生指针
		typedef T* iterator;//定义指针类型的别名iterator
		typedef const T* const_iterator;
        //...函数接口的实现

	private:
		iterator _start;// 指向容器的开始
		iterator _finish;// 指向容器中最后一个有效数据的下一个位置
		iterator _endofstorage;  // 指向存储容量的结尾
	};
}

私有成员变量：

_start: 这是一个指针，指向容器的第一个元素。
_finish: 这个指针指向容器中最后一个有效数据的下一个位置。
_endofstorage: 这个指针指向分配给vector的内存块的末尾。这不是最后一个有效元素的位置，而是整个内存块的结束位置，在这之后可能会有额外的未初始化空间，预留以实现当vector增长时无需重新分配整个数组。

2、默认成员函数

2.1、构造函数

vector()

默认构造的函数功能是构造一个没有元素的空容器。

默认构造函数实现有两种方式，第一种是直接通过初始化列表直接初始值，第二种是通过成员变量的缺省值。

1.初始化列表

//将成员变量都初始化为空
vector()
	: _start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{}

2. 缺省值

//会默认使用缺省值构造
vector()
{}

private:
	iterator _start=nullptr;		
	iterator _finish=nullptr;		
	iterator _endofstorage=nullptr;  
};

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

填充构造函数功能是构造一个包含 n 个元素的容器。每个元素都是 val 值。

思想：

为了确保空间足够，我们可以先将空间扩容至n(减少扩容消耗)，再将n个值尾插到容器中。

//构造n个数值 并初始化为val
vector(size_t n, const T& val = T())
{
	reserve(n);//细节，先开空间
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

注意：

vector构造函数中的const T& val = T()，T是一种类型，T的类型取决于vector后的<>，<>中是什么类型，T就是什么类型。

T是内置类型时，T() == 0。

char()需要强转成int才能看到0，因为ASCII码值为0的char字符是'\0'，屏幕上显示不出来。

当T是自定义类型时，T()调用无参或者全缺省构造函数构造一个匿名对象，若T类中不存在无参全缺省构造方法时报错。

vector(InputIterator first, InputIterator last)

迭代器区间构造函数功能是将[first,last)区间的元素构造成一个新容器，注意 last位置的元素是不取的。

template <class InputIterator> 是一个函数模板，函数参数是一个迭代器类型。
函数实现原理：从 first 位置开始遍历迭代器区间，遍历的同时将该位置的数据尾插到vector上，直到遍历到 last 位置则结束循环。

//类模板里面有函数模板
//template<typename InputIterator>
template <class InputIterator>//与类模板类型名区分
vector(InputIterator first, InputIterator last)//拷贝迭代器区间
{
	while (first != last)//起始与结尾不相等则插入
	{
		push_back(*first);
		++first;//向后移动
	}
}

如果实现了迭代器区间构造函数以及填充构造函数之后，去实例化vector<int> v(10,1)则会出错，因为此时的参数都为int类型，而填充构造函数 vector(size_t n, const T& val = T()) 的第一个类型时无符号整数，迭代器区间构造函数 vector(InputIterator first, InputIterator last)是两个相同类型的模板参数，此时会优先调用更匹配的迭代器区间构造函数，然后10-1不是一个区间，也不能解引用，因此编译器报错。

解决办法是重载一个填充构造函数，如下：

vector(int n, const T& val = T())

//构造n个数值 并初始化为val
vector(int n, const T& val = T())//x64有问题
{
	reserve(n);//细节，先开空间
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

2.2、析构函数

析构函数功能是销毁动态开辟的空间。

释放空间并将指针置空即可。

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

2.3、拷贝构造函数

vector(const vector<T>& v)

函数功能构造一个包含 v 中所有元素的容器。

先开辟一个与原容器大小相等的空间，然后直接尾插即可。

//v(v1)
vector(const vector<T>& v)
{
	reserve(v.capacity());//开始扩容，减少频繁扩容
	for (auto& x : v)//字符串可能有问题，加&
	{
		push_back(x);//尾插数据
	}
}

注意：reserve()与push_back()函数在后面有实现！！！

vector(initializer_list<T> il)

initializer_list 是一个类，支持{}初始化。

实现思想是使用范围for遍历该类，遍历的同时尾插数据即可，为了减少扩容消耗，可以提前开辟好空间。

//vector<int> v ={1,2,3,4,5}
vector(initializer_list<T> il)
{
	reserve(il.size());//提前开好il大小的空间
	for (auto& x : il)
	{
		push_back(x);//尾插
	}
}

2.3、赋值操作符重载

vector<T>& operator=(vector<T> v)

赋值操作符重载的功能是将新内容分配给容器，替换其当前内容，并相应地修改其大小。

此处为现代写法，直接交换两个容器，函数参数不能加引用。

void swap(vector<T>& v)
{
	swap(_start, v._start);//调用库函数的swap函数
	swap(_finish, v._finish);
	swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> v)
{
	swap(v);//调用就近类内函数
	return *this;
}

3、数据访问

operator[](size_t pos)

使用下标加 [ ] 访问数据。

T& operator[](size_t pos)//[]运算符重载
{
	assert(pos < size());
	return _start[pos];
}
const T& operator[](size_t pos) const
{
	assert(pos < size());
	return _start[pos];
}

front()

获取第一个元素(即_start指向的位置)。

T& front()
{
	return *_start;
}

const T& front()const
{
	return *_start;
}

back()

获取最后一个元素(_finish前面一个位置)。

T& back()
{
	return *(_finish - 1);
}

const T& back()const
{
	return *(_finish - 1);
}

4、迭代器获取

begin()

返回容器的首地址(_start)。

iterator begin()
{
	return _start;
}
const_iterator begin() const //无允许修改，加const修饰函数
{
	return _start;
}

end()

返回容器当中有效数据的下一个数据的地址(_finish)。

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

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！

码农公寓

1、基本结构

2、默认成员函数

2.1、构造函数

2.2、析构函数

2.3、拷贝构造函数

2.3、赋值操作符重载

3、数据访问

4、迭代器获取

总结

相关文章