【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现

这篇具有很好参考价值的文章主要介绍了【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:C++从入门到精通⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习C++
  🔝🔝


【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

1. 前言

和string的学习不同
vector即要掌握它的用法
更要会自己去实现一个vector

本章重点:

熟悉STL库中vector的接口函数
自己实现一个简易vector类
本章只实现容量相关函数
和构造,析构,拷贝构造函数

注:vector其实就是顺序容器
string类只用考虑存储字符
然而vector中可以存储任一类型
所以vector的自我实现需要用模板


2. 熟悉vector的接口函数

还是借助老朋友:cplusplus来查阅文档

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

库中的vector的模板参数有两个
后一个是内存池,用来提升空间利用效率
对于现阶段的学习而言可有可无


2.1 vector的构造与拷贝构造

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

常见的构造有:

vector<int> v1;
vector<int> v2(10,1);
vector<int> v3(v2);

v2:构造并初始化10个值为1的顺序表

vector可以用迭代器区间初始化:

string str("abcdefg");
vector<string> vv(str.begin(),str.end());

2.2 vector迭代器的使用

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言
和string一样,vector有正向和反向
两种迭代器,且使用方法和string相同

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

vector<int> vv{1,2,3,4,5,6};
vector<int>::iterator it = vv.begin();
while(it!=vv.end())
{
	cout<<*it;
	it++;
}

2.3 vector空间相关函数

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

vector的空间相关的函数
和string的机会一模一样
如果你看了文档还不懂的话
可以先阅读此篇文章:string接口函数


2.4 vector的增删查改

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言
push_back和pop_back
都是老朋友了,这里就不多说了
在介绍insert和erase之前
先来了解几个算法库的函数


2.41 find,swap和sort

这三个函数都在头文件:algorithm

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

find函数:参数是一段迭代器区间
以及在此区间你需要查找的值
找到后返回这个值对应的迭代器位置
若找不到,则返回迭代器last

find的使用:

vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
cout<<*pos;

注:使用auto是为了简写迭代器也可以用
vector< int >::iterator替代

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

swap想必是大家的常客了
这里给它个面子,就不介绍它了

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

sort非常方便,它内部实现是快排
我们只需要传一个迭代器区间
就可以将整个区间排好序

sort的使用:

vector<int> vv{5,7,3,9,6,4,1,2,8};
sort(vv.begin().vv.end());

2.42 insert和erase

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

和string不同,vector的insert
的参数pos不是整型,而是迭代器
默认是在pos位置前插入一个数据

insert和find常常配合在一起使用

在整型5前面插入一个100:

vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
vv.insert(pos,100);

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

和string的erase不同,vector
的erase一次只删除一个数据
然而string如果使用缺省值就是
将全部数据删完

vector的erase甚至可以删除一段区间

删除顺序表中值为100的元素

vector<int> vv{1,2,3,4,5,6,7,8,9,100};
auto pos = find(vv.begin(),vv.end(),100);
vv.erase(pos);
//删除一个区间
vv.erase(vv.begin()+2,vv.end()-2);

2.43 随机访问operator[ ]

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

vector中最喜欢用的是[ ]
它支持随机访问,是否方便

operator[]的使用:

vector<int> vv{1,2,3,4,5,6,7,8,9};
for(int i=0;i<vv.size();i++)
{
	cout<<vv[i]<<" ";
}

3. vector的模拟实现

首先要关注的是成员变量
vector是顺序表,所以和实现C语言
时的顺序表一样,至少有三个参数

  1. 指向一段空间的指针
  2. 空间的有效大小
  3. 空间的实际大小

由于vector的迭代器就是普通指针
所以成员变量的类型其实是迭代器

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

private:
	iterator _start;
	iterator _finish;
	iterator _endof_storage;

这里使用迭代器作为三个参数的类型
是因为:求vector的size和capacity时
可以直接使用finish-start
也就是指针相减求出长度

成员变量和空间的关系:

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言


3.1 vector容量相关函数

上来首先要考虑的容量相关的函数:

  • size
  • capacity
  • empty
  • resize
  • reverse

前三个十分简单:

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

size_t capacity() const
{
	return _endof_storage - _finish;
}

bool empty() const
{
	return (size()==0);
}

3.11 reverse函数

reverse只会改变capacity的大小
并不会改变size的大小

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T)*sz);
			for (size_t i = 0; i < sz; ++i)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}

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

注:当n小于capacity时,不进行扩容

由于C++内存管理的new
无法像C语言的realloc一样原地扩容
所以必须先开辟n个空间,再将数据
拷贝到新空间,且释放旧空间


3.12 resize函数

resize即会改变size大小
也会改变capacity大小

resize要分三种情况:

  1. n大于capacity时
  2. n大于size小于capacity时
  3. n小于size时

它们的解决方案分别是:

  • 直接套用reversezhu

  • 初始有效值不变,在此之后
    初始化新的内容

  • 直接将size缩小到n

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;
	}
}

注:参数val=T()使用了匿名对象
C++将内置类型特殊处理过
int/char等等都被升级为了类
所以可以使用int()表示匿名对象

int tmp1 = int();
int tmp2 = int(10);

int的缺省值为0


3.2 vector的构造函数

  1. 首先最简单的无参构造:
vector()
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{}
  1. 紧接着是带参的构造函数
    我们跟着STL库的风格走:
vector(size_t n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);//开辟n个空间
	for (size_t i = 0; i < n; ++i)
	{
		push_back(val);//给初始值赋值
	}
}
  1. 最后是使用迭代器区间来构造
    比如我想在顺序表中存放string类型:
string str("abcdefg");
vector<string> vv(str.begin(),str.end());

此时在模板类中还应该有一个模板

template <class InputIterator>
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

注:inputiterator取名是模仿STL的
你也可以取任一除了T的名字


3.3 vector的析构函数

vector的析构函数非常简单
只需要将空间释放
并且将各个指针置为空就行了

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

3.4 vector的拷贝构造函数

拷贝构造的实现有很多种写法
大家可以先自己尝试一下

vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endof_storage(nullptr)
	{
		reserve(v.size());
		for (const auto& e : v)
		{
			push_back(e);
		}
	}

4. 总结以及拓展

vector模拟实现的全部代码我将在
下一篇文章中分享给大家

可以发现:STL的神奇之处在于
它把所有接口函数都做了统一化处理
每一个容器的接口函数的使用都相似
但是内部实现被这种封装隐藏起来了
进一步又体现了C++的三大特性:
封装

并且C++实现了所有容器通用的算法库
比如sort和find都只需要传迭代器
然而所有容器都会被迭代器封装
所以一份代码就能实现对不同容器的操作

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现,C++从入门到精通,c++,java,开发语言

拓展题目:

熟悉了vector的基本使用
可以尝试解决一下下面几个问题:

  • 只出现一次的数字
  • 删除有序数组中的重复项
  • 数组中出现次数超过一半的数字
  • 杨辉三角

留给大家当作小试牛刀了~文章来源地址https://www.toymoban.com/news/detail-679111.html


🔎 下期预告:迭代器失效和深浅拷贝问题 🔍

到了这里,关于【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】STL——vector 深度剖析 及 模拟实现

    这篇文章我们来学习一下STL里面的vector,它属于STL中容器的一员,我们先来学习一下它的使用,然后,我们也会对vector进行一个深度的剖析和模拟实现。 1.1 vector的介绍 vector的文档介绍 vector 是表示大小可以更改的数组的序列容器: 其实大家可以认为 vector就是我们之前数据结

    2024年02月05日
    浏览(47)
  • 【C++】透过STL源码深度剖析及模拟实现vector

    鉴于读者的响应,打算将文章拆分一下,方便观看,基本接口可看 深入浅出STL之vector类 以下我所介绍的都是基于【SGI】版本的STL,对源码有兴趣的同学可以去看看 侯捷老师的《STL源码剖析》 然后呢我们就去调出【vector】的一些核心源码,这里我们主要关注的就是这个使用原

    2024年02月14日
    浏览(42)
  • 【C++进阶(一)】STL大法以及string的使用

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 由于C语言的 标准库不够强大 没有数据结构和一些基本算法 什么都需要程序员自己实现 所以C语言在某种意义上并不实用 本章重点: 本章会

    2024年02月11日
    浏览(45)
  • 【C++】:STL源码剖析之vector类容器的底层模拟实现

    构造一个空vector size和capacity为0 将_start _finish _endofstorage 都置为空指针即可 传统写法 : 1). 新开辟一块和 v 同样容量的空间,更新 _start, _finish, _endofstorage 2). 将 v 中的数据拷贝到新开辟的空间中 注意 : 不要使用memcpy函数拷贝数据,如果数据是内置类型或浅拷贝的自定义类型

    2024年02月04日
    浏览(52)
  • 【C++从入门到放弃】vector深度剖析及模拟实现

    🧑‍💻作者: @情话0.0 📝专栏:《C++从入门到放弃》 👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢! vector 是表示 可变大小数组 的序列容器。 就像数组一样,vector也采用的 连续存储空间 来存储元素。也就是意味着可以

    2024年02月07日
    浏览(49)
  • 【C++】STL——list深度剖析 及 模拟实现

    这篇文章我们来继续STL的学习,今天我们要学习的是list,也是STL中容器的一员。 和之前一样,我们还是先学习它的使用,然后再对它进行一个深度剖析和模拟实现。 1.1 list的介绍 list的文档介绍 list的底层实现其实就是我们之前数据结构学过的带头双向循环链表: 1.2 list的使

    2024年02月05日
    浏览(43)
  • 【C++】STL之list深度剖析及模拟实现

    目录 前言 一、list 的使用  1、构造函数 2、迭代器 3、增删查改 4、其他函数使用 二、list 的模拟实现  1、节点的创建  2、push_back 和 push_front  3、普通迭代器  4、const 迭代器  5、增删查改(insert、erase、pop_back、pop_front)  6、构造函数和析构函数   6.1、默认构造   6.2、构造

    2024年02月07日
    浏览(46)
  • C++入门之stl六大组件--List源码深度剖析及模拟实现

    文章目录 前言 一、List源码阅读 二、List常用接口模拟实现 1.定义一个list节点 2.实现一个迭代器 2.2const迭代器 3.定义一个链表,以及实现链表的常用接口 三、List和Vector 总结 本文中出现的模拟实现经过本地vs测试无误,文件已上传gitee,地址:list: 模仿实现stl的list - Gitee.com 首

    2024年02月13日
    浏览(51)
  • C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现

    目录 前言 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的模拟实现 三、priority_queue的介绍和使用 1.priority_queue的介绍 2.priority_queue的使用 3.priority_queue的模拟实现 3.1解决一个topK问题 四、容器适配器 1

    2024年02月14日
    浏览(49)
  • 【C++】:C++中的STL序列式容器vector源码剖析

    vector定于与stl_vector.h头文件中 例如: vector的数据结构非常简单:一个线性连续空间 下面介绍vector的3个数据结构: start:表示目前使用空间的头 finish:表示目前使用空间的尾 end_of_storage:表示目前可用空间的尾 说明:为了降低空间配置时的速度成本,vector实际配置的大小可

    2024年01月22日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包