【C++】vector的使用及模拟实现

发布时间：2024年01月16日

一、vector的介绍及使用

1.1 介绍vector

vector是一个可变大小数组的容器，与数组一样，vector也是一块连续的空间，可以像数组一样对元素进行高效的遍历访问，但是普通数组的大小是不变的，vector可以改变自身大小。vector是采用动态分配数组来存储数据，即插入新元素时要改变存储空间大小，往往要分配一个新的数组，然后把原来数组的元素转移到新的空间里。vector的尾插尾删效率高，中间插入和删除效率较低。

1.2 vector的使用

1.2.1 构造

1??无参

vector()

vector<int> v;

2??构造并初始化n个val

vector（size_type n, const value_type& val = value_type()）

vector<int> v(10, 7);

在这里插入图片描述

3??拷贝构造

vector (const vector& x)

	vector<int> v1{ 1,2,3,4 };
	vector<int> v2(v1);

在这里插入图片描述
4??使用迭代器进行初始化构造

vector (InputIterator ?rst, InputIterator last)

	vector<int> v1{ 5,6,7,8};
	vector<int> v2(v1.begin(), v1.end());

在这里插入图片描述

1.2.2 遍历访问

1??begin+end

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

获取数组第一个元素的位置，像指针一样遍历整个数组，直到最后一个元素结束。auto是自动推导类型。

2??下标：operator[ ]

	vector<int> v{ 1,2,3,4,5 };
	for (int i = 0; i < 5; i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;

3??范围for

	vector<int> v{ 1,2,3,4,5 };
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

1.2.3 容量空间

1??获取元素个数

	vector<int> v{ 1,2,3,4,5 };
	cout << v.size() << endl;//5

2??获取容量大小

	vector<int> v{ 1,2,3,4,5 };
	cout << v.capacity() << endl;//5

3??判断是否为空

	vector<int> v;
	cout << v.empty() << endl;

4??改变vector的size

void resize (size_type n, value_type val = value_type());

	vector<int> v{ 1,2,3,4,5 };
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	v.resize(10, 9);
	cout << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << v.size() << endl;
	cout << v.capacity() << endl;

在这里插入图片描述
如果超出原来的存储空间，那么capacity也会改变

5??改变vector的capacity

void reserve (size_type n);

	vector<int> v{ 1,2,3,4,5 };
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	v.reserve(10);
	cout << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << v.size() << endl;
	cout << v.capacity() << endl;

在这里插入图片描述

1.2.4 增删查改

1??尾插

	vector<int> v{ 1,2,3,4,5 };
	v.push_back(9);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

在这里插入图片描述
2??尾删

	vector<int> v{ 1,2,3,4,5 };
	v.pop_back();
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

在这里插入图片描述
3??查找
注意查找不是vector的接口，是算法模块实现的。

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);

	vector<int> v{ 1,2,3,4,5 };
	auto it = find(v.begin(), v.end(), 2);
	cout << *it << endl;//2

4??交换

void swap (vector& x);

	vector<int> v1{ 1,2,3,4,5 };
	vector<int> v2{ 6,7,8,9,10 };
	v2.swap(v1);

在这里插入图片描述
5??在pos位置插入

iterator insert (iterator position, const value_type& val);

	vector<int> v{ 1,2,3,4,5 };
	auto pos = find(v.begin(), v.end(), 2);
	v.insert(pos, 10);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

在这里插入图片描述
6??在pos位置删除

iterator erase (iterator position);//指定位置删除
iterator erase (iterator first, iterator last);//指定范围删除

有两种写法：

//	一：
	vector<int> v{ 1,2,3,4,5 };
	auto pos = find(v.begin(), v.end(), 2);
	v.erase(pos);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

在这里插入图片描述

//    二：
	vector<int> v{ 1,2,3,4,5 };
	v.erase(v.begin() + 1, v.end() - 1);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

在这里插入图片描述

注意：insert 和 erase 一般只使用一次，重复使用可能导致迭代器失效。

二、vector的模拟实现

2.1 成员变量

vector的迭代器是一个原生指针，它的三个成员变量分别是：

在这里插入图片描述

	typedef T* iterator;
	typedef const T* const_iterator;
	//————————
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _endofstorage = nullptr;

这里在声明时先给成员变量缺省值为空指针，声明时给缺省值是给初始化列表的，后续写的时候就比较方便。

2.2 迭代器相关函数

begin函数返回空间的起始位置，end函数返回空间的最后一个有效元素的下一位。

	// 通过迭代器访问元素时可修改
	iterator begin()
	{
		return _start;
	}
	iterator end()
	{
		return _finish;
	}
	// 通过迭代器访问元素时不可修改
	const_iterator begin() const 
	{
		return _start;
	}
	const_iterator end() const
	{
		return _finish;
	}

2.3 构造-析构-赋值重载

2.3.1 无参构造

没有传参数

	vector()
	{}

2.3.2 有参构造1

代码：

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	reserve(last - first);//复用扩容函数
	while (first != last)//判断条件
	{
		push_back(*first);//复用尾插函数
		++first;//尾插一次后加1
	}
}

这个函数看起来有些奇怪，为啥还要套一层模板呢？使用这里就不说了，其实这个构造函数的作用是：只要传进来的是迭代器就可以初始化该迭代器的内容，前提是该迭代器是指向连续物理空间的指针。比如用vector定义了一个v1，v1已经是构造好的，有具体的元素；再定义一个v2，我想让v2的内容跟v1是一样的，就可以使用这个函数，传的迭代器指向的是v1的头和尾，它就会构造出和v1一样的内容。前面的使用方法有代码。不仅可以vector传vector，还可以list传vector，只要是迭代器即可。

2.3.3 有参构造2

vector(size_t n, const T& x = T())
{
	resize(n, x);//复用修改元素个数函数
}
vector(int n, const T& x = T())
{
	resize(n, x);//复用修改元素个数函数
}

该构造函数是初始化为n大小的空间，每个元素是x。可以直接复用resize函数，下面会介绍。这里写了两个构造函数唯一的区别是size_t 和int ，因为如果只有size_t 类型的那个构造函数，构造时不会调用该函数，会调用前面的构造函数（有参构造1），这与函数模板的匹配调用原则有关。假如传进来的n不是size_t 类型，那么它就要发生隐式类型转换，但是编译器想，隐式类型转换感觉麻烦，就使用有模板的那个函数。

为了防止出现以上情况，同时是模拟实现，要尽可能像标准库里面的vector，所以多重载了一个函数，它的参数n是int 类型的，这样的话传进来的参数n是int 类型，那么它就会直接调用这个构造函数，避免了以上情况。

2.3.4 拷贝构造

拷贝构造要注意深浅拷贝问题
1??写法1

vector(const vector<T>& v)
{
	_start = new T[v.capacity()];//开一样大的空间
	memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据
	_finish = _start + v.size();
	_endofstorage = _start + v.capacity();
}

与string的拷贝构造类似，开一块新空间，拷贝数据后，指向这个新空间，这样防止两个指针指向同一块空间。

在这里插入图片描述
写法1还要注意memcpy的深浅拷贝问题，与元素的类型有关，这个在后面会具体介绍，现在假设统一使用的元素类型先是 int 类型。

1??写法2

vector(const vector<T>& v)
{
	reserve(v.capacity());//复用扩容函数
	for (const auto& e : v)//范围for循环直接放入数据即可
	{
		push_back(e);//复用尾插函数
	}
}

先开与参数v一样大的空间，然后使用范围for直接放入数据，只要参数v里面有元素，都可以把元素一个一个的尾插到要构造的空间里面，同时也不影响v，最终完成拷贝构造。
在这里插入图片描述

2.3.5 赋值重载

1??写法1

vector<T>& operator=(const vector<T>& v)
{
	if (this != &v)//相同就不用赋值
	{
		T* tmp = new T[v.capacity()];//临时空间
		memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据
		delete[] _start;//清理旧空间
		_start = tmp;//指向新空间
		_finish = _start + v.size();//
		_endofstorage = _start + v.capacity();
	}
	return *this;
}

1??写法2
与string的是一样的，直接代码：

vector<T>& operator=(vector<T> v)
{
	swap(v);//复用交换函数
	return *this;
}

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

2.3.6 析构

如果空间里有元素才清理，让3个指针置空；没有元素本来就是空指针不能清理。

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

2.4 容量操作

2.4.1 size和capacity

根据三个指针的指向，可以确定有效元素个数和容量的区间

//返回个数
size_t size() const
{
	return _finish - _start;
}
//返回容量
size_t capacity() const
{
	return _endofstorage - _start;
}

2.4.2 reserve

如果存储的元素超出原来的空间大小要扩容，扩容要开辟一块新空间，然后拷贝数据到新空间里，再让指针重新指向这块新空间。
代码：

//扩容
void reserve(size_t n)
{
	if (n > capacity())//满了要扩容
	{
		size_t old = size();//记录当前元素个数
		T* tmp = new T[n];//新空间
		if(_start)
		{
			//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝
			for (size_t i = 0; i < old; i++)
			{
				tmp[i] = _start[i];//深拷贝
			}
			delete[] _start;//释放就空间
		}
		_start = tmp;//指向新空间
		_finish = _start + old;//防止迭代器失效
		_endofstorage = _start + n;
	}
}

问题1：为什么要定义变量old

开空间拷贝数据后，旧空间被释放，指向新空间，_finish等于_start 加上元素个数，注意，如果没有old前面先记录元素个数的值，加上的是调用size函数返回的元素个数，那么就会出现迭代器失效问题。因为_start已经指向新的空间，而_finish还是指向旧空间的某个位置，那个不同空间相减就出问题了。

在这里插入图片描述
所以这里提前用变量old记录好元素的个数，_finsih等于_start+old，就不会出现以上情况。

问题2：memcpy是浅拷贝

元素类型是int 等内置类型没关系，如果是自定义类型，比如string，这里就会出现浅拷贝的问题。

在这里插入图片描述
深拷贝的做法是以赋值的形式逐个把旧空间的字符串给新空间：

2.4.3 resize

该函数可通过参数n修改元素个数，超出容量也会扩容。主要分为以下3点：

1.n小于等于元素个数
2.n大于元素个数且小于等于容量
3.n大于容量

代码：

void resize(size_t n, const T& x = T())
{
	if (n <= size())
	{
		_finish = _start + n;//修改_finish指向即可
	}
	else//n>size()
	{
		size_t len = n - size();//n与元素个数的差值
		if (n > capacity())//n大于容量要扩容
		{
			reserve(n);//复用扩容函数
		}
		while (len--)//插入len个x，只要n大于size()都要插入
		{
			*_finish = x;
			++_finish;
		}
	}
}

2.5 插入与删除

2.5.1 尾插

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

尾插数据，_finish 指向同_endofstorage说明空间内数据已满，要扩容。然后插入在_finish指向的位置插入数据，_finish往后移。

2.5.2 尾删

void pop_back()
{
	assert(size() > 0);//有元素才能删
	--_finish;
}

2.5.3 pos位置插入

首先断言pos的位置是否合理，然后凡是插入数据，都要检查是否需要扩容。接着挪动数据，在pos位置插入新的元素。

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos <= _finish);//检查pos位置是否合理
	size_t len = pos - _start;//记录pos与开始位置差值
	if (_finish == _endofstorage)//满了要扩容
	{
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
		reserve(newcapacity);
		pos = _start + len;//防止迭代器失效
	}
	iterator end = _finish - 1;
	while (end >= pos)//挪动数据
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;//插入新数据
	++_finish;
	return pos;
}

这里唯一要注意的是如果有发生扩容，pos的位置要进行更新。
在这里插入图片描述

2.5.3 pos位置删除

判断pos位置是否合理，然后挪动数据往前覆盖一个元素。

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

2.6 遍历访问

遍历访问有两种实现方式，一种是迭代器，前面已经写过了，另一种是方括号重载运算符，即我们常见的下标。

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

2.7 全部代码

2.7.1 vector.h

#include <iostream>
#include <assert.h>
using namespace std;

namespace yss
{
	template <class T>
	class vector
	{
	public:
		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;
		}
		//构造1
		vector()
		{}
		//构造2
		vector(size_t n, const T& x = T())
		{
			resize(n, x);
		}

		vector(int n, const T& x = T())
		{
			resize(n, x);
		}
		//构造3
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			reserve(last - first);
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//拷贝构造
		//写法1
		//vector(const vector<T>& v)
		//{
		//	_start = new T[v.capacity()];//开一样大的空间
		//	memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据
		//	_finish = _start + v.size();//
		//	_endofstorage = _start + v.capacity();
		//}
		//写法2
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (const auto& e : v)
			{
				push_back(e);
			}
		}

		//赋值重载
		//写法1
		//vector<T>& operator=(const vector<T>& v)
		//{
		//	if (this != &v)
		//	{
		//		T* tmp = new T[v.capacity()];//临时空间
		//		memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据
		//		delete[] _start;
		//		_start = tmp;
		//		_finish = _start + v.size();//
		//		_endofstorage = _start + v.capacity();
		//	}
		//	return *this;
		//}
		//写法2
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

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

		//返回个数
		size_t size() const
		{
			return _finish - _start;
		}
		//返回容量
		size_t capacity() const
		{
			return _endofstorage - _start;
		}
		//交换
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

		//扩容
		void reserve(size_t n)
		{
			if (n > capacity())//满了要扩容
			{
				size_t old = size();//记录当前元素个数
				T* tmp = new T[n];//新空间
				if(_start)
				{
					//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝
					for (size_t i = 0; i < old; i++)
					{
						tmp[i] = _start[i];//深拷贝
					}
					delete[] _start;//释放就空间
				}
				_start = tmp;//指向新空间
				_finish = _start + old;//防止迭代器失效
				_endofstorage = _start + n;
			}
		}
		//改变元素个数
		void resize(size_t n, const T& x = T())
		{
			if (n <= size())
			{
				_finish = _start + n;
			}
			else
			{
				size_t len = n - size();
				if (n > capacity())
				{
					reserve(n);
				}
				while (len--)
				{
					*_finish = x;
					++_finish;
				}
			}
		}


		//尾插
		void push_back(const T& x)
		{
			if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
			}
			*_finish = x;
			++_finish;
		}
		//尾删
		void pop_back()
		{
			assert(size() > 0);
			--_finish;
		}
		//pos位置插入
		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			size_t len = pos - _start;//记录pos与开始位置差值
			if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
				pos = _start + len;//防止迭代器失效
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
			return pos;
		}
		//pos位置删除
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator begin = pos + 1;
			while (begin < _finish)
			{
				*(begin - 1) = *begin;
				++begin;
			}
			--_finish;
			return 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];
		}

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

2.7.2 test.cpp

#include"vector.h"

int main()
{
	/*yss::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;*/

	/*yss::vector<int> v(10);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;*/

	/*yss::vector<int> v1(5, 99);
	yss::vector<int> v2(v1.begin(), v1.end());
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;*/

	/*yss::vector<int> v1(5, 55);
	yss::vector<int> v2(v1);
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;*/

	/*yss::vector<int> v1(7, 44);
	yss::vector<int> v2 = v1;
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;*/

	/*yss::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	auto pos = find(v.begin(), v.end(), 2);
	v.insert(pos, 99);
	for (auto e : v)
	{
		cout << e << " ";
	}*/

	/*yss::vector<int> v;
	v.push_back(1);
	v.push_back(22);
	v.push_back(43);
	v.push_back(64);
	v.push_back(85);
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;*/
	return 0;
}

文章来源:https://blog.csdn.net/2301_77459845/article/details/135451634
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

【C++】vector的使用及模拟实现

目录

一、vector的介绍及使用

1.1 介绍vector

1.2 vector的使用

1.2.1 构造

1.2.2 遍历访问

1.2.3 容量空间

1.2.4 增删查改

二、vector的模拟实现

2.1 成员变量

2.2 迭代器相关函数

2.3 构造-析构-赋值重载

2.3.1 无参构造

2.3.2 有参构造1

2.3.3 有参构造2

2.3.4 拷贝构造

2.3.5 赋值重载

2.3.6 析构

2.4 容量操作

2.4.1 size和capacity

2.4.2 reserve

2.4.3 resize

2.5 插入与删除

2.5.1 尾插

2.5.2 尾删

2.5.3 pos位置插入

2.5.3 pos位置删除

2.6 遍历访问

2.7 全部代码

2.7.1 vector.h

2.7.2 test.cpp