C++ [STL之vector模拟实现]网站首页 技术教程

C++ [STL之vector模拟实现]

ARMCSKGT 2024-06-28 18:01:02

简介C++ [STL之vector模拟实现]

本文已收录至《C++语言和高级数据结构》专栏！
作者：ARMCSKGT

前言

vector是STL容器容器之一，其底层实现类似于数据结构顺序表，相当于string来说得益于泛型模板的加持使得vector可以变为任何类型，且是可以动态扩容，堪称大号数组！在vector的实现中，有许多值得我们学习的细节，接下来将为大家一一介绍！
C++ for STL-vector

正文

本文将实现一些有学习意义的常规简单接口，提高我们的代码能力！

空间结构

与C语言实现顺序表不同，vector底层空间结构为三个指针:

_start：指向空间的起始地址
_finish：指向最后一个数据的下一个地址(下一个空位)
_end_of_stroage：指向空间最后一个最末地址
namespace My_vector
{
	template<class T> //模板参数T
	class vector
	{
		typedef T* iterator; //指针重命名为迭代器
		typedef const T* const_iterator;
	
	private:
		iterator _start; //首地址
		iterator _finish; //空位地址
		iterator _end_of_storage; //空间末地址
	}
}
这里需要注意的是，由于vector使用了模板，所以函数实现都在头文件中，防止因为模板导致的链接错误的问题！

默认成员函数

无一例外，常用的默认成员函数有四个：

构造函数
拷贝构造函数
赋值重载函数
析构函数

这里的默认成员函数都需要自己设计，因为涉及深拷贝和一些其他细节问题！

构造函数

构造函数有三个版本，分别是：默认构造函数，带参构造函数和迭代器区间构造

默认构造函数：初始化三个指针置空即可
带参构造函数：初始化n个T类型的value值在对象中
迭代器区间构造：通过其他容器迭代器或指针迭代插入其所有值
//迭代器区间构造
vector()
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{}

//带参构造函数
//vector(size_t n, const T& value = T()) //初始化n个t类型数据
//	:_start(nullptr)
//	, _finish(nullptr)
//	, _end_of_storage(nullptr)
//{
//	reserve(n);
//	for (int i = 0; i < n; ++i)
//	{
//		*(_finish++) = value;
//	}
//}

//带参构造函数 int修复版本
vector(int n, const T& value = T()) //初始化n个t类型数据
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	if (n > 0) //n必须大于0才能处理
	{
		reserve(n); //提前开辟空间
		for (int i = 0; i < n; ++i) //逐一插入
		{
			*(_finish++) = value;
		}
	}
}

//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	auto it = first;
	int n = 0;
	while (it != last) { ++n; ++it; }	//计算数据长度

	reserve(n); //提前开辟空间
	while (first != last) //迭代器插入数据
	{
		push_back(*first);
		++first;
	}
}
这里需要注意几个问题：
我们首先实现了带参构造函数的n为size_t类型的版本，因为不可能插入负数个T类型的value数据，但是如果我们使用带参构造函数实例化，则会发生非法间接寻址的错误！这是因为size_t是整型，实例化T数据类型也是整型，此时编译器会自动匹配最合适的构造函数，于是匹配到了迭代器区间构造！
vector(size_t n, const T& value = T()) //int类型n vector<int> v(2,1);时会冲突
vector(int n, const T& value = T()) //size_t类型n 
解决方法就是写一个n为int类型的带参构造参数去匹配，而且可以不用size_t版本！

此外，这里多处使用了匿名对象初始化缺省参数，这里T()就是一个匿名对象，用于初始化value。当我们只输入n参数时，匿名对象会作为缺省值传递给value，这里需要注意：

匿名对象的生命周期只在这一行，但是被const修饰后会延长生命周期
内置类型也支持像构造对象一样初始化
//例如
int a(1)
int b(); //默认初始化为0
char c('c');

//所以可以这样赋值
double d = double(1.23);
float f = float()
拷贝构造函数

拷贝构造最大的问题就是涉及深拷贝问题，我们希望当一个vector对象拷贝另一个对象时新对象开辟独立的空间拷贝数据，而不是两个对象共用一段空间，否则在析构时会出现异常现象！
//传统写法
vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(v.capacity()); 提前开辟空间
	for(int i = 0;i<v.size();++i)
	{
		*(_finish++) = v._start[i]; //访问v中的数据并赋值
	}
}

//现代写法 - 在实现swap后可以构造临时对象然后交换资源
//vector(const vector<T>& v)
//	:_start(nullptr)
//	, _finish(nullptr)
//	, _end_of_storage(nullptr)
//{
//	vector<T> tmp(v.begin(), v.end()); //迭代器区间构造局部对象
//	swap(tmp); //swap交换数据
//}
默认生成的构造函数是浅拷贝，所以我们自己实现，在插入数据时预先开辟空间，然后逐一赋值，这样就能避免浅拷贝问题，因为如果是自定义对象在赋值时会调用其自己的拷贝构造！

现代写法需要先实现swap函数，然后构造临时对象交换对应的指针即可！

赋值重载

赋值重载与拷贝构造的问题类似，也要注意深拷贝问题；区别于拷贝构造的地方在于不需要新建对象，但是需要判断是否为同一个对象避免重复开空间，clear先清空已有数据，reserve开v对象空间大小的容量，如果v对象空间小于现有空间则不开，此时_finish无论是否开空间都在空间的起始位置(也就是容器为空)，直接使用_finish赋值即可！

当然，赋值重载也有基于swap的现代写法；现代写法无论是否是同一个对象都会重新开空间拷贝，两者各有优劣！
//传统写法
vector<T>& operator=(const vector<T>& v)
{
	if (&v != this) //判断是否为同一个对象
	{
		clear(); //先清空原空间 方便下面继续使用
		reserve(v.capacity()); //开v对象大的空间，如果比v对象大则不开
		for (int i = 0; i < v.size(); ++i)
		{
			*(_finish++) = v._start[i]; //无论是否开了空间_finish指针重新开始赋值
		}
	}
	return *this;
}

//现代写法
//vector<T>& operator=(vector<T> tmp) //使用传值参数临时对象
//{
	//	swap(tmp);
	//	return *this;
//}
析构函数

析构函数就非常简单了，释放_start指向的空间，置空三个指针即可！
但是在此之前要判断一下_start是否有空间，如果是空指针则不需要释放！
~vector()
{
	if (_start) //判断是否为空指针
	{
		delete[] _start;
		_start = _finish = _end_of_storage = nullptr;
	}
}
关于数据拷贝问题

拷贝构造和赋值重载自己实现的意义
浅拷贝也称值拷贝，只是拷贝这个值而已；但我们需要的是独立开辟空间然后将数据拷贝一份下来，两者完全独立！

对于浅拷贝带来的问题：

两个对象指向同一片空间，最后delete两次这片空间，最终导致报错！

所以在涉及空间操作和扩容操作的情况下，必须注意自定义对象深拷贝问题，对于自定义类型，只需要其自己调用对应的拷贝构造，而不是我们自己擅自操作空间！

数据拷贝使用赋值的意义
因为vector是模板，在string实现中我们对于字符串数据是通过strcpy拷贝的，那么vector数据的拷贝能不能用内存拷贝函数memcpy或memmove呢？答案是肯定不能！

vector实例化为内置类型使用内存拷贝函数没有问题，但是实例化为自定义类型就会出现内存问题，因为内存拷贝函数在拷贝数据时是从内存中逐字节拷贝，我们实际需要的是内置类型直接拷贝，而自定义类型去调用其对应的拷贝构造，但是使用了mem等内存函数自定义类型就无法调用拷贝构造，最终导致也出现内存错误！

因为这个问题，在vector拷贝构造和reserve扩容等涉及数据拷贝的函数中，我们使用的不是内存拷贝函数，而是直接赋值！

迭代器

vector存储数据使用的是一段连续的存储空间，所以迭代器只需要将指针typedef即可，对指针 ++和- - 就能遍历数据！
typedef T* iterator;
typedef const T* const_iterator;
//迭代器部分
iterator begin() { return _start; } //自适应普通迭代器
iterator end() { return _finish; }

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

const_iterator cbegin() const { return  begin(); } //const迭代器
const_iterator cend() const { return end(); }
这里我们提供了普通迭代器和const迭代器，对于const迭代器，有许多人吐槽cbegin和cend没必要设计，因为begin和end普通迭代器可以设计为自适应模式！

对于下面的函数：
void func(const vector<int>& v) 
{
	auto vit = v.begin(); 	
}
如果begin没有重载const_iterator类型的迭代器，则会报错，但是重载后，编译器会识别这个对象是const引用类型就会调用begin的const_iterator版本！

这里begin和end迭代器就非常智能，实现了自适应，很多人觉得cbegin和cend设计就冗余了！

其实库里面也是为了保持一致，尽量让所有的容器都有这些接口，降低学习成本！
所以我们模拟实现还是实现了cbegin和cend，只不过复用了普通迭代器的const版本！

至于库中还存在反向迭代器，这个我们后面会就行介绍(其实是对普通迭代器的封装，对反向迭代器的++就是对普通迭代器的- -)！

容量操作

查询容量

对于查询容量常用的就三个函数：

size()：查询有效元素个数
capacity()：查询当前容量大小
empty()：查询当前容器是否为空(没有数据)
//元素个数
size_t size() const { return _finish - _start; }
//容量大小
size_t capacity() const { return _end_of_storage - _start; }
//判空
bool empty() const { return _start == _finish; }
这三个函数都比较简单，直接实现即可！

唯一需要注意的两点是，首先这些函数只是查询函数不涉及修改，可以使用const修饰this指针，其次因为对空间的管理使用的是三个指针，所以使用_finish(有效数据指针)减去_start(空间首地址)就能得出有效数据个数，容量也是如此！

容量操作

扩容操作
对于reserve函数，前面我们介绍了关于数据拷贝的问题，reserve最重要的点就是不能使用内存函数拷贝数据，而是使用赋值调用拷贝构造就行数据拷贝！

对于reserve函数的首先，有以下几点情况：

对于申请的空间大小n进行判断，小于当前空间大小就不进行任何操作
开辟n大小的空间，使用tmp临时变量存储地址，方便准备数据拷贝
判断当前空间是否存有数据以及是否为空指针，进行数据迁移
在数据迁移时一定要用赋值而不是内存拷贝(否则释放旧空间时，vector实例的自定义类型会调用对于的析构，而我们拷贝的是旧空间中的旧对象，而不是拷贝构造的新对象，在旧空间释放后，新空间中的自定义对象也会释放，则存储的都是无效数据)
最后交付数据，初始化三个指针
void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t len = size(); //获取当前原空间下数据个数
		T* tmp = new T[n]; //开辟n个空间(n>size())

		if (begin() && (len > 0)) 
		{
			for (int i = 0; i < size(); ++i) //有数据则拷贝
			{
				tmp[i] = _start[i];
			}
			delete[] _start; //拷贝完成后释放原空间
		}

		_start = tmp; //交付空间
		_finish = _start + len;
		_end_of_storage = _start + n;
	}
}
数据大小调整
对于resize函数，最大的区别在于新的数据空间的初始化！

对于resize：

先判断n是否大于容量，准备扩容
将新的数据位置为val(val有缺省参数，为T())
最后初始化_finish指针
void resize(size_t n, T val = T()) //数据长度设置为n，新的数据位置为val
{
	if (n > capacity()) //如果n大于容量就先扩容
	{
		reserve(n);
	}
	iterator it = _start + n; //初始化新空间
	while (_finish < it)
	{
		*_finish = val; //逐一置为val
		++_finish;
	}
	_finish = it; //最后初始化_finish
}

数据访问

下标访问

下标访问通过重载运算符[ ]首先的，这里我们首先了两个版本的[ ]重载函数，在对应不同的场景！
T& operator[](size_t pos) //引用版本
{
	assert(pos < size() && pos >= 0); //检查下标合法性
	return _start[pos];
}

const T& operator[](size_t pos) const //const引用版本
{
	assert(pos < size() && pos >= 0); //检查下标合法性
	return _start[pos];
}
对于at函数，由于其抛异常的特性，这里我们简单实现，复用运算符[ ]，对于异常问题，以后会为大家进行介绍！
T& at(size_t pos) { return (*this)[pos]; }
const T& at(size_t pos) const { return (*this)[pos]; }
头尾数据访问

同样的，front和back函数也有普通版本和const版本，在不同场景下编译器会选择合适的函数进行调用！
//front 首个数据
T& front() { return (*this)[0]; }
const T& front() const { return (*this)[0]; }
//back //末尾数据
T& back() { return (*this)[size()-1]; }
const T& back() const { return (*this)[size() - 1]; }
这里复用运算符[ ]，复用下标和容量的检查！

数据增删

尾插尾删

对于尾插：在插入前需要检查容量是否充足，不充足需要扩容，然后直接插入_finish的空位下即可，_finish指针移动到下一个空位
对于尾删：只需要将_finish指针向前移动即可(- -指针)，但需要判断size是否>0
//尾插
void push_back(const T& val)
{
	if (_finish == _end_of_storage)
	{
		//扩容时采用两倍策略，如果为空则赋予四个空间的初值
		reserve(capacity() == 0 ? 4 : capacity() * 2); 
	}
	*_finish = val; //赋予_finish指向的空位
	++_finish; //_finish指针后移
}

//尾删
void pop_back()
{
	assert(size() > 0); //判断是否有数据可删
	--_finish; //_finish指针前移
}
重新分配

vector通过了重新分配函数assign，这个函数类似于赋值重载，会清空里面原有的所有数据，然后重新赋值，如果空间不足则会扩容！

这个函数有两个版本：

迭代器区间分配
分配n个val值到容器中
//迭代器区间分配
template<class InputIterator>
void assign(InputIterator first, InputIterator last)
{
	size_t n = 0;
	auto it = first;
	while (it != last) { ++n; ++it; }
	if (n > capacity())
	{
		reserve(n); //扩容
	}
	clear(); //默认清空数据
	while (first != last)
	{
		(*(_finish++)) = (*(first++)); //赋值完成后_finish会指向下一个空位
	}
}

//分配n个val值
void assign(int n, const T& val)
{
	reserve(n); //默认扩容，如果空间足够就不会执行任何操作
	clear(); //默认清空数据
	while (n--) { push_back(val); } //插入n个数据
}
这里要注意的，首先是容量问题，其次是分配数据需要清空原有的数据！

任意位置插入删除

任意位置插入和删除是我们常用的函数，但是这里最大的问题就是迭代器失效的问题！

当我们使用现在的迭代器插入一个数据，可能涉及容器扩容，如果扩容，那么迭代器是旧空间的迭代器，则会导致迭代器失效，因为原有空间已经被释放，但迭代器还是指向原空间(那么就是野指针)，所以我们在插入或删除后要更新迭代器，那么我们的插入删除函数必须在操作后返回一个迭代器！

对于插入来说，插入一个元素后返回这个新插入元素位置的迭代器
– 对于插入来说，如果涉及扩容，则将迭代器更新到新空间的对应数据位置
对于删除来说，删除一个元素后返回其下一个元素的迭代器
– 对于删除来说，删除是后面的数据覆盖前面的数据，最终从pos位置开始所有数据会向前挪动一位，那么挪动完成后，当前pos位置就是下一个迭代器的位置，直接返回即可
//在pos迭代器位置插入x
iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);

	if (_finish == _end_of_storage) //判断容量问题
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		//扩容后迭代器失效了，需要更新同步迭代器
		pos = _start + len;
	}
	iterator cur = _finish++;
	while (cur != pos)
	{
		*cur = *(cur - 1);
		--cur;
	}
	*cur = x;
	return cur;
}

//删除pos迭代器位置的数据
iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos <= _finish);

	iterator cur = pos;
	while (cur != _finish - 1)
	{
		*cur = *(cur + 1); //挪动数据
		++cur;
	}
	--_finish;
	return pos; //挪动完成后pos位置的数据已经被下一个数据覆盖了，直接返回即可
}
迭代器失效问题概述

对于我们扩容后，迭代器失效的现象：

对于迭代器失效的现象，删除也可能出现此现象！

对于迭代器失效问题，编译器也会检查：

VS下(PJ)版本是一旦插入或删除必须更新迭代器，哪怕没有发生扩容，否则报错
g++下(SGI)版本不会主动检查迭代器更新问题，但是如果发生扩容或删除完了元素没有更新迭代器就会发生段错误

其他操作

清空函数

对于vector元素的清空，我们只需要将_finish指针设置为_start即可，这样就代表当前vector中没有任何元素，同时清空不需要缩容！
//清空函数
void clear() { _finish = _start; }
交换函数

对于vector的交换，只需要交换两个vector对象的三个指针即可！
//交换函数
void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}
关于排序

vector因为连续的空间，对排序是非常有利的；库函数中已经实现了快排，也就是sort函数，可以对支持迭代器的容器排序！

关于sort的使用，这里需要给大家介绍一下

sort有两个版本，都是通过迭代器区间进行排序，默认升序，第二个版本支持控制升序和降序！
int arr[] = { 3,2,1,5,4 };
vector<int> v(arr,arr+5);
sort(v.begin(), v.end());// 默认升序
for (const auto& x : v)
{
	cout << x << " ";
}
cout << endl;
sort(v.begin(), v.end(), greater<int>()); //排降序
for (const auto& x : v)
{
	cout << x << " ";
}
cout << endl;
//控制函数Compare是一个仿函数
less<T>(); //T类型的升序比较仿函数
greater<T>(); //T类型的升降序比较仿函数
这里需要注意的是，sort函数需要声明algorithm算法头文件并声明std命名空间，greater和less也需要在std命名空间中声明！

最后

vector模拟实现到这里就结束了，相信vector的模拟实现让大家对底层代码的细节问题又有了新的认识，这就是我们学习和使用这些容器代码的意义！

本次 <C++ vector模拟实现> 就先介绍到这里啦，希望能够尽可能帮助到大家。

如果文章中有瑕疵，还请各位大佬细心点评和留言，我将立即修补错误，谢谢！

本文整体代码：vector模拟实现代码

?其他文章阅读推荐?
C++ <STL之vector的使用> -CSDN博客
 C++ <STL之string的使用> -CSDN博客
 C++ <STL之string模拟实现> -CSDN博客
 C++ <STL简介> -CSDN博客
 C++ <模板> -CSDN博客
?欢迎读者多多浏览多多支持!?