【C++】STL — vector的接口讲解 +详细模拟实现

前言:
本章我们将学习STL中另一个重要的类模板vector…

  • vector是表示可变大小数组的序列容器
  • 就像数组一样,vector也采用的连续存储空间来存储元素。但是又不像数组,它的大小是可以动态改变的
  • 本质讲,vector使用动态分配数组来存储它的元素
  • vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。

能不能用vector来替代string呢?

  • 可以是可以,但是有区别的,string的部分功能vector实现不了,比如:流插入>>和流提取 <<
  • string比较大小是按照ASCII码比较,但是vector的规则就不一样了。
  • Vector 是没有重载<< 和>>操作符的 find( ),以及以下使用情况,

vector < char> T;
string str ; // 数据结尾\0 、+=、find、比较大小、to_string、<< 、>>等等
// vector < char> 无法替代string

目录

    • 1. vector的使用
      • 1.1 vector的构造:
      • 1.2 vector的迭代器:
      • 1.3 vector的内存管理:
      • 1.4 迭代器可以访问容器:
    • 2. vector的模拟实现
    • 2.1 迭代器失效问题
    • 2.2 深浅拷贝问题

1. vector的使用

1.1 vector的构造:

在我们使用vector之前我们需要先包一下头文件#include< vector >

在这里插入图片描述

int main ()
{
  // constructors used in the same order as described above:
  std::vector<int> first;                                // empty vector of ints
  std::vector<int> second (4,100);                       // four ints with value 100
  std::vector<int> third (second.begin(),second.end());  // iterating through second
  std::vector<int> fourth (third);                       // a copy of third
// the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
  }

1.2 vector的迭代器:

用法和string中的迭代器一样.

void test_vector2()
{
	//遍历
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	//1、下标 + []
	for (size_t i = 0; i < v.size(); i++)
	{
		v[i] += 1;
		cout << v[i] << " ";
	}
	cout << endl;

	//2、迭代器
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		*it -= 1;
		cout << *it << " ";
		it++;
	}
	cout << endl;

	//3、范围for
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

1.3 vector的内存管理:

STL中vector每次扩容的规律:

void test_vector3()
{
	//vector<int> v;
	//cout << v.max_size() << endl;

	//Capicity容量测试 -- VS是PJ版本 大概是1.5倍增容,Linux是SGI版本 是2倍增容
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

内存管理数据分析:

  • 单次增容越多,插入N个值,增容次数越少,效率就越高
  • 单次增容越多,造成空间浪费。

reserve / resize 的使用:

  • reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
  • resize在开空间的同时还会进行初始化,影响size
容量空间接口说明
resize(重点)改变vector的size
reserve (重点改变vector的capacity
void tese_vector4()
{
	vector<int> countV;
	//resize 开空间 + 初始化
	countV.resize(100, 1);
	countV.resize(10);
	countV.reserve(1000);
	//sting 和 vector等都有一个特点,删除数据,一般不会主动缩容的

	countV.shrink_to_fit();
	cout << countV.size() << endl;
	cout << countV.capacity() << endl;

	cout << endl << endl;
//操作系统的空间不允许一部分一部分还
//vector没有头插头删,效率比较低
}

insert / erase 的使用:

void test_vector5()
{
	//遍历
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	v.insert(v.begin(), -1);
	v.insert(v.begin(), -2);
	v.insert(v.begin(), -3);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	//可以在尾最后一个位置插入,越界了是不行的
	v.insert(v.begin() + 7, 3000);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.erase(v.begin());
	v.erase(v.begin());

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

1.4 迭代器可以访问容器:

void test_vector6()
{
	vector<int> v;
	//auto pos = find(v.begin(), v.end(), 3);
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		cout << "找到了" << endl;
		v.erase(pos);
	}
	else
	{
		cout << "没有找到" << endl;
	}

	for (auto ch : v)
	{
		cout << ch << " ";
	}
	cout << endl;
	v.push_back(0);
	v.push_back(9);
	v.push_back(3);
	v.push_back(1);

	//默认是升序
	//sort(v.begin(), v.end()); // < 

	//排降序,使用仿函数greater
	//关于仿函数,先记住这个用法,具体后面学习队列细学
	sort(v.begin(), v.end(), greater<int>()); // > ,greater<int>()匿名对象
}
  • 仿函数我们后期会学,先包一下头文件:#include< functional> – 仿函数
  • vector和list没有find,没有查找函数,我们需要包一个算法的头文件 #include< functional >

2. vector的模拟实现

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;

	//构造函数1
	vector()
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstoage(nullptr)
	{}
   //给一个迭代器的区间去构造2
	template<class InputIterator>
	vector(InputIterator first, InputIterator last)
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstoage(nullptr)
	{
		while (first != last)
		{
			push_back(*first);
			first++;
		}
	}
	//用n个val初始化3
	vector(size_t n, const T& val = T())
		: _start(nullptr)
		, _finish(nullptr)
		, _endofstoage(nullptr)
	{
		reserve(n);
		for (size_t i = 0; i < n; i++)
		{
			push_back(val);
		}
	}
//重载一个int n (逻辑和上面一样)
	vector(int n, const T& val = T())
		: _start(nullptr)
		, _finish(nullptr)
		, _endofstoage(nullptr)
	{
		reserve(n);
		for (int i = 0; i < n; i++)
		{
			push_back(val);
		}
	}

void swap(vector<T>& v)
	{
		std::swap(_start, v._start);
		std::swap(_finish, v._finish);
		std::swap(_endofstoage, v._endofstoage);
	}

//拷贝构造--现代写法1
	vector(const vector<T>& v)
		//vector(const vector& v)
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstoage(nullptr)
	{
		//拷贝构造中调用一个构造函数,构造一个tmp出来
		vector<T> tmp(v.begin(), v.end());
		//通过this指针调用该对象的成员函数
		this->swap(tmp);
	}

	//-----现代写法2
	vector<T>& operator=(vector<T> v)
	{
		this->swap(v);
		return *this;
	}
}

C++中,内置类型也可以认为,有构造函数和析构函数

原因在于:1.这样可以更好支持模板 2.void resize(size_t n, T val = T()) 与类的对象使用方法一样:
int i=0;
int j= int(1)
int m(1);
在这里插入图片描述

//资源清理
~vector()
{
	if (_start != nullptr)
	{
		delete[] _start;
		_start = _finish = _endofstoage = nullptr;
	}
}

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

const_iterator begin() const
{
	return _start;
}

const_iterator end() const
{
	return _finish;
}

size_t size() const
{
	return _finish - _start;
}

size_t capacity() const
{
	return _endofstoage - _start;
}

void reserve(size_t n)
{
	//这里存在start更新之后就算不准的现象
	size_t sz = size();
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start != nullptr)
		{
			//memcpy(tmp, _start, size() * sizeof(T));
			//这里是浅拷贝,所以会有问题
			for (size_t i = 0; i < size(); i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
	}
	_finish = _start + sz;
	_endofstoage = _start + n;
}

注意:

  • 一开始的时候 _finish 和 _start 都是0空指针nullptr
  • _start被更新了,要是这样:_finish = _start + size();
  • 不能用size( ),要是这样:_finish = _start + _finsih - _start;
//生成T类型的匿名对象,C++内置类型也有默认构造函数
//分3种情况:
 1.n>capacity 需要扩容+初始化
 2.n>size && n<=capacity 初始化
 3.n<size 删除数据
 
void resize(size_t n, const T& val = T())
{
	if (n > capacity())
	{
		reserve(n);
	}

	if (n > size())
	{
		while (_finish < _start + n)
		{
			*_finish = val;
			_finish++;
		}
	}
	else
	{
		_finish = _start + n;
	}
}

void push_back(const T& x)
{
	/*if (_finish == _endofstoage)
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*_finish = x;
	_finish++;*/finish代表最后一个,所以要加一个

	insert(end(), x);
}

void pop_back()
{
	/*if (_finish > _start)
	{
		_finish--;
	}*/

	//返回的临时对象不能改变,不能++(自增)和--(自减)
	erase(end() - 1);
}

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.1 迭代器失效问题

两种迭代器失效原因:

  • 1.野指针
  • 2.意义变了

与vector类似, string在插入+扩容操作+ erase之后,迭代器也会失效
1.在迭代器位置P插入数据以后,不要访问P了,因为P可能失效了

auto p=find(v.begin( ),v.end( ),3);
if(p!=v.end( ))
{
     v.insert(p,30);
     cout<<*p<<endl;
     //这里最好就不要使用了,迭代器P已经失效了,如果必须要有,要接收返回值,对P重新赋值
     v.insert(p,30);
}
  1. 总结一下,如果必须要用,为了防止迭代器失效,在使用迭代器前,对迭代器重新赋值即可

结论:insert/erase pos位置后,不要直接访问pos.一定要更新,因为直接访问,可能会出现各种出乎意料的结果,这就是所谓的迭代器失效

演示代码1:

void test_vector2()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	v.insert(v.begin(), 0);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

迭代器失效问题,是因为pos是不更新的。

  • 当reserve扩容之后,如果是新空间,_start和_finish更新了,pos(就是v.begin())还指向旧空间
  • 但是旧空间被释放了,这个问题就是迭代器失效,pos为野指针
  • 所以就插入失败了
  • 迭代器发生了野指针的问题
    insert函数中的内部pos指针更新了,但是形参的改变不会影响实参,pos指针是一个传值传参
	//pos前一个位置插入(之前是void,所以错误)
	iterator insert(iterator pos, const T& x)
	{
		//检查Pos位置是否合理
		assert(pos >= _start && pos <= _finish);
		//扩容
		//扩容以后pos就失效了,需要更新一下
		if (_finish == _endofstoage)
		{
			size_t n = pos - _start;
			size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
			reserve(newCapacity);
			//更新迭代器的位置,做返回
			pos = _start + n;
		}

		//挪动数据
		iterator end = _finish - 1;
		while (end >= pos)
		{
			*(end + 1) = *end;
			end--;
		}
		*pos = x;
		_finish++;
		return pos;
	}


	**//有返回值是防止STL库里面有缩容的情况,不知道怎么实现的**
	//如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是,没有元素的,那么pos就失效了
	iterator erase(iterator pos) %-**-返回删除位置的下一个位置**
	{
		assert(pos >= _start && pos < _finish);
		iterator begin= pos + 1;
		while (begin != _finish)
		{
			*(begin - 1) = *begin;
			begin++;
		}
		_finish--;
		return pos;
	}

	void clear()
	{
		_finish = _start;
	}
private:
	iterator _start;
	iterator _finish;
	iterator _endofstoage;
};

//类外定义拷贝构造-模板写法:
template<typename T>
vector<T>::vector(const vector<T>& v)
   :_start(nullptr)
   , _finish(nullptr)
   , _endofstoage(nullptr)
{
	vector<T> tmp(v.begin(), v.end());
    this->swap(tmp);
}

2.1.1 Insert 和 Erase 迭代器失效的讨论

vector<int>::iterator it = v.begin();

	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
		//错误写法:
		   v.insert(it, 20)
		 //正确写法:
			it = v.insert(it, 20);
			it++;
		}
		it++;
	}

(1)Insert 扩容的情况:(野指针)

  • 如果扩容的话,迭代器将it指向原来的空间,原来的空间已经被释放了
  • 当再次进入Insert时,it变成野指针。

(2) Insert 不扩容的情况:(意义变了)

  • insert以后虽然没有扩容,it不是野指针,但是it指向位置的意义变了

  • it++之后一直指向20,导致了我们这个程序重复插入20

  • 不是it是野指针失效的,而是it指向的位置意义变了

  • 也叫作迭代器失效

(3)Erase 缩容的情况:(野指针)

  • STL里对erase的实现,有可能存在缩容实现,就会出问题
  • 当再次进入erase时,it变成野指针。

(4) Erase不扩容的情况:(意义变了)

  • erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效。
  • 但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是没有元素的,那么pos就失效了

解决方案:

  • 采取返回指针的话可以完美避开上述所有问题
  • 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等

2.2 深浅拷贝问题

以杨辉三角为例:
vector<vector< int>> vv;
在这里插入图片描述

  • vector<vectot< int >>表示里面的每个数据存的都是vector的对象
  • 外面vector的是深拷贝,里面的Vector 使用的是memcpy( )做的是浅拷贝, 导致delete析构的时候,指向同一个空间,出现问题
  • vector里面的T类型有可能是自定义类型,使用Memcpy( )就是浅拷贝,所以里面也要做深拷贝。

**结论:**如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃

尾声
看到这里,相信大家对这个C++有了解了。
如果你感觉这篇博客对你有帮助,不要忘了一键三连哦

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/603954.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

智慧公厕的核心技术详解:物联网、云计算、大数据、自动化控制

公共厕所是城市的重要组成部分&#xff0c;而智慧公厕的建设和管理正成为城市发展的重要方向。智慧公厕的核心技术即是物联网、云计算、大数据和自动化控制。下面将以智慧公厕源头实力厂家广州中期科技有限公司&#xff0c;大量精品案例项目现场实景实图实例&#xff0c;详细介…

Sealos急速部署生产用k8s集群

最近一段时间部署k8s全部使用sealos了&#xff0c;整体使用感觉良好&#xff0c;基本没有什么坑。推荐给大家。 使用 Sealos&#xff0c;可以安装一个不包含任何组件的裸 Kubernetes 集群。 最大的好处是提供 99 年证书&#xff0c;用到我跑路是足够了。不用像之前kubeadm安装…

【计算机科学速成课】笔记一

文章目录 写在前面1.计算机的早期历史2.电子计算机3.布尔运算和逻辑门4.二进制5.算术逻辑单元-ALU6.寄存器和内存 写在前面 所有的一切源于这样一个网站——CS自学指南。 这是新手小白入门计算机科学必要了解的知识——【计算机科学速成课】[40集全/精校] - Crash Course Comp…

地平线的花样年华

北京车展在这个喧闹的“五一”假期落幕了&#xff0c;它留给我们许多思考。 虽然社会面的传播焦点落在了“网红”两个字上&#xff0c;但技术的更新依然如暗流涌动&#xff0c;给这届北京车展写下注脚。整个过程前后&#xff0c;最重要和吸引了最多目光的&#xff0c;是智驾&a…

2024蓝桥杯CTF writeUP--cc

给了个网页&#xff0c;里面有加密算法&#xff0c;密钥&#xff0c;密文 使用在线解码工具 CTF最全在线工具整理_在线ctf工具-CSDN博客 将输出的密文&#xff0c;密钥&#xff0c;vi&#xff0c;加密方式一一对应

Linux变量的认识及环境变量配置详解

文章目录 1、变量的划分2、局部变量3、全局变量4、环境变量4.1、概述4.2、配置临时环境变量4.3、配置永久环境变量4.3.1、用户级配置文件1&#xff09;配置方法一&#xff1a;~/.bashrc文件2&#xff09;配置方法二&#xff1a;~/.profile文件3&#xff09;配置方法三&#xff…

生产制造中刀具管理系统,帮助工厂不再频繁换刀

一、刀具管理的定义与重要性 刀具管理是指对生产过程中使用的各种刀具进行计划、采购、存储、分配、使用、监控、维修和报废等全过程的管理。刀具作为制造过程中的直接工具&#xff0c;其性能、质量和使用效率直接影响产品的加工精度、表面质量和生产效率。因此&#xff0c;建…

ansible—playbook的template、tags、roles模块

目录 一、template 1、简介 2、template模块实例 1.先准备一个以.j2结尾的template模板文件&#xff0c;设置引用的变量&#xff0c;ansible上要先安装httpd 2、修改主机清单文件&#xff0c;使用主机变量定义一个变量名相同而值不同的变量 3、主机添加hosts 4、编写pla…

【漏洞复现】金和OA FileDownLoad接口处存在任意文件读取漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…

词袋法TFIDF

Tf-idf⽂本特征提取 TF-IDF的主要思想是&#xff1a;如果某个词或短语在⼀篇⽂章中出现的概率⾼&#xff0c;并且在其他⽂章中很少出现&#xff0c;则认为此词或者短语具有很好的类别区分能⼒&#xff0c;适合⽤来分类。TF-IDF作⽤&#xff1a;⽤以评估⼀字词对于⼀个⽂件集或…

数据结构-线性表-链表-2.3-1

设计一个递归算法&#xff0c;删除不带头结点的单链表L中所有值为x的结点。 void del(Linkllist &L&#xff0c;int x){LNode *p;if(LNULL){return;}if(L->datax){pL;LL->next;;free(p);del(L,x);}else{del(L->next,x);} } 时间复杂度为O(n)

Linux系统编程--网络编程

一、OSI网络七层模型 OSI模型将整个网络通信过程分解为七个层次&#xff0c;每个层次都为网络通信提供了特定的功能。以下是OSI模型的七个层次&#xff0c;从上到下依次是&#xff1a; 应用层&#xff08;Application Layer&#xff09;&#xff1a;为应用软件提供网络服务&am…

盘点四种计算数组中元素值为1的个数的方法

目录 一、引言 二、方法一&#xff1a;基础循环遍历 三、方法二&#xff1a;列表推导式 四、方法三&#xff1a;使用内置函数sum和生成器表达式 五、方法四&#xff1a;使用NumPy库 六、性能比较 七、性能结果分析与讨论 八、最佳实践 九、总结 一、引言 在编程和数…

Linux:进程通信(二)信号的保存

目录 一、信号的处理是否是立即处理的&#xff1f; 二、信号如何保存 1、阻塞、未决、递达 2、信号集 3、信号集操作函数 4、sigprocmask函数 5、sigpending 函数 上篇文章我们讲解了信号的产生&#xff1a;Linux&#xff1a;进程信号&#xff08;一&#xff09;信号的产…

7天精通Web APIs——-Bom操作(理论+实战)(第五天)

一、window对象 1.1 window对象和bom的关系 首先理解dom和bom之间的关系 显然bom的范围比较大 bom的全称为浏览器对象模型 window是bom的核心对象&#xff0c;window里面有很多属性和方法&#xff0c;用于实现浏览器与 JavaScript 代码之间的交互。作为 JavaScript 的全局对…

项目管理-项目绩效域2/2

项目管理&#xff1a;每天进步一点点~ 活到老&#xff0c;学到老 ヾ(◍∇◍)&#xff89;&#xff9e; 何时学习都不晚&#xff0c;加油 八大绩效域包括&#xff1a;“团干部 策划开公交” 团队、干系人、不确定性、测试、规划、开发方法与生命周期、项目工作、交付。 上节…

淘宝评论电商API接口:便捷查询商品真实评价

随着电商的快速发展&#xff0c;用户对于商品的评价越来越重要。淘宝作为中国最大的电商平台&#xff0c;拥有海量的商品和用户评价数据。联讯数据为了提供便捷的商品评价查询服务&#xff0c;淘宝推出了评论电商API接口。 什么是淘宝评论电商API接口 淘宝评论电商API接口是淘…

抖音赚钱可以看看这些小众赛道,很多人都赚到了自己的第一个一百万!2024适合小白入手的项目!白手起家新手小白创业真经

抖音创业最大的魅力是什么&#xff1f; 如果你还想创业&#xff0c;还想在抖音这个赛道上发光发热&#xff0c;不妨停下来思考一下这个问题。 那就是可以让一个及其小众的小品类的产品&#xff0c;捅破天花板&#xff01;达到一个不可思议的销售额&#xff01;这就是我的答案&…

Windows注册表

注册表 一.概述 注册表&#xff08;Registry&#xff09;是Microsoft Windows中的一个重要的数据库&#xff0c;用于[存储系统]和[应用程序]的设置信息。早在[Windows 3.0]推出[OLE]技术的时候&#xff0c;注册表就已经出现。随后推出的[Windows NT]是第一个从系统级别广泛使…

Python:一种强大的编程语言与无限可能

引言 Python是一种易于学习且功能强大的编程语言&#xff0c;它被广泛用于各种领域&#xff0c;包括数据科学、人工智能、Web开发、系统自动化等。Python以其简洁的语法、丰富的库和易于阅读的风格&#xff0c;成为了许多开发者的首选。本文将探讨Python的特性和应用&#xff…
最新文章