【C++】使用vector和模拟其实现-创新互联

文章目录
    • 1、vector的使用
      • 1.1 vector的构造、拷贝构造与迭代器
      • 1.2 vector的空间查询和随机访问
      • 1.2 vector的增删查改
    • 2、vector的模拟实现
      • 2.1 vector的迭代器
      • 2.2 vector的结构构建
      • 2.4 vector的构造和拷贝构造
      • 2.4 vector的增删

你所需要的网站建设服务，我们均能行业靠前的水平为你提供.标准是产品质量的保证，主要从事成都网站制作、网站建设、外贸网站建设、企业网站建设、移动网站建设、网页设计、高端网站设计、网页制作、做网站、建网站。创新互联公司拥有实力坚强的技术研发团队及素养的视觉设计专才。1、vector的使用

C++中的vector和C数据结构中的动态顺序表是相似的。

vector属于C++STL中的容器，STL在主流上有PJ版本（Windows Visual C++采用，可读性较差）、SGI（被Linux采用，可移植性好，阅读性也高）等。

这里的使用在VS环境下进行，后续模拟实现参考SGI版本。

值得注意的是，因为类模板的出现，容器中如vector，只是一个类模板，而真正的类需要实例化，如vector，所以定义一个vector对象，应该是类似vectorv这样的。

 

1.1 vector的构造、拷贝构造与迭代器

先认识一下，包括vector的构造、拷贝构造、赋值。
构造：
(为了更好理解使用，做了一些关于空间配置器的省略)

//第一种无参构造
vector()
//第二种，第一个参数代表初始有效个数，val代表赋的初始值
vector(size_type n, const value_type& val = value_type());
//第三种，迭代器赋值
template(class InputIterator)
vector(InputIterator first, InputIterator last);

拷贝构造:
拷贝构造很简单

vector (const vector& x);

赋值:
赋值注意的是两种不同的形式，代表不同含义。

//第一种 直接赋值
vectorv1;
vectorv2(10, 0);
v1 = v2;
//第二种 表面赋值，其实是拷贝构造
vectorv3 = v2;

实例:

#include#includeusing namespace std;

void vector_test1()
{//构造
	vectorv1;
	vectorv2(10, 0);
	vectorv3(v2.begin(), v2.end());
	
	string s = "hello world";
	vectorvs(s.begin(), s.end());
	
	//拷贝构造
	vectorv4(v2);
	vectorv5 = v2;
	
	//赋值
	vectorv6;
	v6 = v2;
}

int main()
{vector_test1();
	return 0;
}

vector中的迭代器使用
迭代器在C++中，封装了iterator和const_iterator两个类。在使用层面上与指针的使用一致，但在底层实现上不同STL版本，不一致，不能简单和指针等同。

首先介绍简单的begin和end。

//begin 返回指向vector中首元素位置的迭代器
iterator begin();

//end 返回指向vector中末尾元素再下一个位置的迭代器
iterator end();

比如:

void vector_test2()
{//构造
	vectorv1(10, 1);
	vectorv2(v1.begin(), v1.end());
	
	//打印
	vector::iterator it = v2.begin();
	while(it != v2.end())
	{cout<< *it;
		++it;
	}
	cout<< endl;
}

 
const 迭代器的使用
const迭代器保护的是指向的数据不能被修改，而迭代器本身是可以被修改的。

//begin 返回指向vector中首元素位置的迭代器
const iterator begin();

//end 返回指向vector中末尾元素再下一个位置的迭代器
const iterator end() const;

比如：

void vector_test3()
{//构造
	vectorv1(10, 1);
	//权限的缩小
	const vectorv2(v1.begin(), v1.end());
	
	//打印
	//切记不能写成 因为这样是使得it不能修改。
	//const vector::iterator it = v2.begin();
	
	//这样改变的是迭代器类型，得换的是一个类
	vector::const_iterator it = v2.begin();
	while(it != v2.end())
	{cout<< *it;
		++it;
	}
	cout<< endl;
}

在迭代器成员函数中还有rbegin，rend。它们使用和begin、end一样，只是返回迭代器指向位置反了过来。
在这里插入图片描述
 

1.2 vector的空间查询和随机访问

vector作为动态数组，也有着当前有效数据个数（size）和当前总容量(capacity)。

size相关的成员函数:

//返回当前有效数据个数
size_type size() const;
//重新设置当前有效数据个数
void resize(size_type n, value_type val = value_type());

capacity相关的成员函数:

//返回当前总容量大小
size_type capacity() const;
//重新设置总容量大小 不缩容只扩容
void reserve(size_type n);

随机访问与其它:

//[]是运算符重载，返回值是单个数据
reference operator[](size_type n);
const_reference operator[](size_type n) const;

//at和[]结果一样，只不过是函数，不怎么用
reference at (size_type n);
const_reference at (size_type n) const;

//返回首元素
reference front();
const_reference front() const;

//返回末尾元素
reference back();
const_reference back() const;
void vector_test4()
{vectorv1(1, 5);
	cout<< v1.size()<< endl;
	cout<< v1.front()<< endl;

	//扩大size，补4
	v1.resize(11, 4);
	cout<< v1.back()<< endl;
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1[i];
	}
	cout<< endl;

	//缩小size, 截断
	v1.resize(6);
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1.at(i);
	}
	cout<< endl;

	//不缩容只扩容
	v1.reserve(10);
	cout<< v1.capacity()<< endl;//11

	v1.reserve(12);
	cout<< v1.capacity()<< endl;//12

}

在这里插入图片描述

1.2 vector的增删查改

注意:vector的插入和删除，一定要注意返回的迭代器，在进行插入删除后，最好对迭代器指向的位置进行更新，不然可能会引起迭代器失效问题。

//尾插
void push_back (const value_type& val);
//尾删
void pop_back();

//指定位置插入删除
//指向位置pos插入val, 返回插入新元素的位置
iterator insert (iterator position, const value_type& val);
//指定位置删除，返回下一个位置
iterator erase (iterator position);

//指定范围插入删除
//指定位置，范围插入。
templatevoid insert (iterator position, InputIterator first, InputIterator last);
//指定范围删除，返回删除范围后一个位置
iterator erase (iterator first, iterator last);

//交换数据
void swap (vector& x);
//清空数据，容量不变
void clear();

测试:

void vector_test5()
{//测试尾插尾删
	vectorv1;
	v1.push_back(1);
	v1.push_back(2);
	v1.pop_back();

	//测试指定位置插入删除
	vector::iterator it = v1.begin();
	it = v1.insert(it, 0);
	it = v1.erase(it);
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1[i];
	}
	cout<< endl;

	//测试指定范围插入删除
	vectorv2(10, 1);
	it = v1.begin();
	v1.insert(it, v2.begin(), v2.end());

	it = v1.erase(v1.begin(), v1.begin() + 3);

	//其它
	v1.swap(v2);
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1[i];
	}
	cout<< endl;

	v2.clear();
	cout<< v2.size()<< endl;
	cout<< v2.capacity()<< endl;
}

使用完~

2、vector的模拟实现

因为SGI版STL可读性比较好，模拟实现以它为参考。
由于vector的模拟实现简单易懂，这里只说部分重要的。

 

2.1 vector的迭代器

由于vector是一个连续的线性空间，所以原生指针可以作为vector的迭代器且满足所有必要条件。（但vs中vector的迭代器底层不是这样的）

templateclass vector
{public:
	typedef T* iterator;
	typedef const T* const_iterator;
	...
}

所以

vector::iterator it;

it就是int*.

2.2 vector的结构构建

vector是一个线性连续空间。在SGI底层，用三个迭代器start、finish、end_of_storage分别指向空间来标识范围。

templateclass vector
{public:
	typedef T* iterator;
	typedef const T* const_iterator;
	...
private:
	iterator _start; //表示已使用用空间的头
	iterator _finish; //表示已使用空间的尾
	iterator _end_of_storage; //表示目前可用空间的尾
}

通过这三个迭代器，可以很轻松的联系上以下功能

templateclass vector
{public:
	typedef T* iterator;
	typedef const T* const_iterator;
	
	iterator begin()
	{return _start;
	}

	const_iterator begin() const
	{return _start;
	}

	iterator end()
	{return _finish;
	}
	
	const_iterator end() const
	{return _finish;
	}
	
	size_t size() const
	{return end()-begin();
	}
	
	size_t capacity() const
	{return _end_of_storage - begin();
	}
	
	bool empty() const
	{return end() == begin();
	}

	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; //表示已使用用空间的头
	iterator _finish; //表示已使用空间的尾
	iterator _end_of_storage; //表示目前可用空间的尾
}

在这里插入图片描述
 

2.4 vector的构造和拷贝构造

vector构造有三种：

vector();

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

templatevector(InputIterator first, InputIterator last);
值得注意的是:第二个构造在调用时可能是vector v(10,1);这样的，由于10和1的类型一样，可能会导致调用第三个构造造成寻址错误，所以下面通过函数重载避免其出现。
#include#include 
using namespace std;

namespace test
{templateclass vector
	{public:
		...
		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_end_of_storage(nullptr)
		{}

		//构造
		vector(size_t n, const T& val = T()) //默认0
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	size_t i = 0;
			for (i = 0; i< n; ++i)
			{		push_back(val);
			}
		}

		//重载解决类似vectorv(10, 1);这样引发的寻址错误
		vector(int n, const T& val = T()) //默认0
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	int i = 0;
			for (i = 0; i< n; ++i)
			{		push_back(val);
			}
		}

		templatevector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	while (first != last)
			{		push_back(*first);
				++first;
			}
		}
		...
		...
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

vector的拷贝构造，可以多进行函数复用，来精简代码。

//拷贝构造 写法一
		//vector(const vector& v)
		//	:_start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//{//	reserve(v.capacity());
		//	for (const auto& e : v) //注意要加& 不然T可能是自定义类型
		//	{//		push_back(e);
		//	}
		//}

		//函数复用 写法二
		vector(const vector& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	vectortmp(v.begin(), v.end());
			swap(tmp);
		}

		//利用v拷贝构造的临时对象进行交换
		vector& operator=(vectorv)
		{	swap(v);
			return *this;
		}
		
		//调用官方std中的浅拷贝
		void swap(vector& v)
		{	std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}
2.4 vector的增删

插入中的迭代器需要注意，扩容可能会导致原本空间被释放，需要迭代器重新指向新空间。

reserve实现有两个注意点：

1. 因为扩容是会开辟新空间，归还旧空间的，所以指向原来旧空间的指针也需要更新。
2. 在拷贝旧空间数据的时候，需要深拷贝，不然自定义类型数据浅拷贝会出现析构错误。

void reserve(size_t n)
	{if (n >capacity())
		{	//使用oldsize 记录旧空间size大小
			size_t oldSize = size();
			T* tmp = new T[n];
			if (_start)
			{		//memcpy(tmp, _start, sizeof(T) * oldSize); 拷贝的是内置数据 对于自定义类型是浅拷贝
				for (size_t i = 0; i< oldSize; ++i)
				{tmp[i] = _start[i];
				}
				delete[] _start;
			}

			_start = tmp;
			_finish = _start + oldSize;
			_end_of_storage = _start + n;
		}
	}

insert实现要注意迭代器失效问题，迭代器pos在扩容以后与原来start的相对距离是固定的，但是指向的位置是原来旧空间的位置，在扩容后需要更新。

iterator insert(iterator pos, const T& val)
	{assert(pos >= _start);
		assert(pos< _finish);
		if (_finish == _end_of_storage)
		{	// 迭代器失效
			// 扩容导致迭代器失效
			size_t oldPos = pos - _start;
			size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
			reserve(newCapacity);
			pos = _start + oldPos; //但形参不改变实参
		}

		iterator end = _finish - 1;
		while (end >= pos)
		{	*(end + 1) = *end;
			--end;
		}

		*pos = val;
		++_finish;

		return pos;

	}

	iterator erase(iterator pos)
	{assert(pos >= _start);
		assert(pos< _finish);

		iterator begin = pos + 1;
		while (begin< _finish)
		{	*(begin - 1) = *(begin);
			++begin;
		}
		--_finish;

		return pos;
	}

最后在vector中，insert或者erase后，一定要注意迭代器的位置，如果在插入或删除后需要使用迭代器，一定要让迭代器接收返回值，不然会出现迭代器失效。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：【C++】使用vector和模拟其实现-创新互联
标题链接：https://www.cdcxhl.com/article34/ipdpe.html

成都网站建设公司_创新互联，为您提供建站公司、网站营销、静态网站、软件开发、网站策划、手机网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

外贸网站制作

网站导航知识

分类信息网