vector使用指南-创新互联
目录
创新互联建站是专业的京山网站建设公司,京山接单;提供网站设计、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行京山网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!引言
空间配置器
vector
vector容器与string容器的一些差异
接口介绍——reserve
resize接口
shrink_to_fit 接口
operator[ ] 和 at 接口
assign接口
增删查改接口
swap接口
例题讲解
引言
vector实质上就是数据结构的顺序表,也可以简单地理解为数组,它在库中的实现与之前我们所学的string有很多相似之处,重复的地方在此不多赘述。
空间配置器可以看到库里vector的模板参数第一项是实例化的类型,也就是顺序表实例化时里面的元素是int还是double的......vector
第二个参数是空间配置器,这个概念相对复杂一点,是一种底层实现机制,在使用层面我们可以暂时不用管。说明一下以防产生误解。
vector首先说明vector
第二个差异在于大小的比较,vector
第三个差异在于接口上,它们之间的接口也有很大区别,功能的不同,实现上的不同等等。比如对于操作符+=的重载,string有+=,可以直接在字符串后面加字符\字符串,而vector
其它的不同更多体现在vector 与 string整体的不同上,后面讲接口的时候会顺带提出。
vector容器与string容器的一些差异上面是vector
string是早期设计的,与后面容器的实现有时代的隔阂,string的接口庞杂繁复,数量是vector的一倍,其实有很多接口是没有什么意义的或者基本不会使用的,但由于向前兼容的特性这些接口都保留了下来。
在insert、erase这些增删接口上面,string与其他容器(如:vector) 的标识也不同,string是使用下标标识位置的,而vector等容器是用迭代器标识位置的 (insert(v.begin()+4,1) )
接口介绍——reservereserve接口主要是扩容,通过改变capacity的大小达成目的。
接口本身很简单易懂,但既然能改变capacity能扩容,那能不能缩容呢?
————一般来说是不会实现缩容的,因为缩容是有代价的,不是想缩就缩的。
缩容实质上是开一块新空间拷贝数据,是以空间换时间的方式。
缩容需要先开新空间,拷贝数据过去,然后释放旧空间,频繁缩容就会反复开空间、释放和拷贝,会有较大代价所以一般不会缩容。
有人会问:为什么不能直接缩容释放不需要的一块空间给操作系统,要开新空间拷贝数据呢?
————这样当然是不行的,和内存管理机制有关。
类似malloc一块空间是不能分两次free还给操作系统的。
resize接口resize接口是个非常重要的接口,主要是改变size,它不改变capacity,有四种情况:
1、没有开空间时,resize开空间+初始化(
2、容量不够时,扩容。如capacity为9,resize(20),此时空间不够会先扩容。
3、容量够时,会从初始size位置填数据直到当前size位置。
4、resize的size值比初始值小时会删除数据,注意不会删除空间!只是删除有效数据!
那么库里面给的接口,参数方面我们似乎看不懂,size_type 和 value_type是什么类型,这是由于库在里面再次typedef了这些类型,在Member types可以查到:
我们可以看到size_type 其实就是size_t类型
value_type则是第一个模板参数,也就是我们这里的T,class
所以库里面的函数定义翻译过来就是void resize(size_t n , T =T() )
n 是改变的size的大小,T = T() 是调用了系统默认构造函数。
由此可以应证C++内置类型也需要(也有)默认构造函数的概念,因为像这种类似的场景用得到。
如果T是内置类型不是自定义类型,如何调用默认构造,所以内置类型也有默认构造函数的概念。
shrink_to_fit 接口上面我们说了一般来说不会轻易缩容,因为代价比较大,像reserve只扩不缩,resize、clear都不动capacity,但是shrink_to_fit 接口是实现来缩容的,与上面reserve、resize相反,是 “以空间换时间 ”。
扩容一般是实现两倍扩容,像Linux等平台下都是两倍,也有些平台是1.5倍扩容,像VS,具体看编译器实现,两倍扩容一般用的比较多一点。
operator[ ] 和 at 接口两个接口都是用来遍历访问vector中的数据的,存在着一定差异。
相同之处是使用方式类似,都是通过下标获得数据。并且都提供了const和非const两个版本。
为什么要提供两个版本?————
1、只读接口函数只有const版本的(如:size函数)只能由const对象调用
2、只写函数接口只有非const版本的(如:push_back函数),只能由非const(普通)对象调用
3、可读可写接口函数,const+非const都提供(如:operator[]),两者都能调用
注意这里的[ ]是函数调用,不是单纯的操作符,与数组不同。
operator[ ]和at的区别在于越界的情况下,[ ] 内部实现的时候是assert断言下标位置pos< size的,
而at 则是通过抛异常的方式报错。(注:assert在debug下有效,relase下不产生效果)
assign接口assign 有2种用法:
用法 1、覆盖赋值,这种方式会覆盖掉之前所有数据。
vectora;
a.resize(5);
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
for (auto e : a)
{
cout<< e<< "";
}
cout<< endl;
a.assign(9, 1);
for (auto e : a)
{
cout<< e<< "";
}
cout<< endl;
从结果来看确实覆盖了之前的数据。
用法 2、支持迭代器区间
库里面给的接口参数就是迭代器区间 [first,last) \ [begin,end) ,是左闭右开的。
使用方式:
vectoraa;
aa.resize(5);
for (auto e : aa)
{
cout<< e<< " ";
}
cout<< endl;
size_t i = 0;
vectorbb;
bb.resize(5);
for (auto &e : bb)
{
e = i++;
}
aa.assign(bb.begin(), bb.end());
for (auto e : aa)
{
cout<< e<< " ";
}
cout<< endl;
再看参数类型,我们发现库里给参数迭代器也写了一个模板,有人会问:直接写成iterator不就行了,为什么还要写个迭代器模板?
————因为如果单写迭代器就只支持vector下的迭代器区间,写成模板的话可以支持其他容器的迭代器区间,比如:
这样就支持了string容器的迭代器区间。
也可以这样使用:
与上面对比一下,发现区间确实像期望所改变了。
增删查改接口数据结构最重要的一环可以说是增删查改了。
增:最常用的是push_back,但是push_back适用于尾插,而在顺序表中一般不建议在中间位置插入(尤其是头插),因为这样会挪动数据,效率低下。所以insert接口使用没有push_back频繁。
另外insert可以插入一个元素,也可以插入一段数据。
删:最常用的是pop_back,但是pop_back适用于尾删,和增一样,其他情况会挪动数据,因此erase接口也使用不那么频繁。
另外删可以删除单个位置数据,也可以直接删除一段数据。
查:在vector容器库中发现没有期望的find接口,这是怎么回事?————因为这个接口在每个容器中实现的方式都是一样的,都是遍历迭代器,找到了就返回对应的迭代器位置,所以不会特地在每个容器中都写一个find,而是将它拉出来写个模板,使得每个容器都能直接使用。
可以看到find是从first位置开始查找,到 last位置结束,找到了返回此时的迭代器,没找到就返回last位置的迭代器(这也体现了迭代器区间左闭右开,last不在区间中)。
使用方式:
vector::iterator it = find(aa.begin(), aa.end(), 101);
if (it != aa.end())
{
aa.insert(it, 0);
}
for (auto e : aa)
{
cout<< e<< " ";
}
cout<< endl;
这里找到了就在当前迭代器位置之前插入0,没找到就不插入。
改:改的话主要是通过operator[ ] 来实现。
swap接口vector中自己实现了一个swap函数,因为库里的swap函数交换代价太大,需要深拷贝。
容器中实现的可以直接完成交换,大大降低了代价开销。
vectorbb;
bb.push_back(1);
aa.swap(bb);
for (auto e : aa)
{
cout<< e<< " ";
}
cout<< endl;
例题讲解LeetCode118.杨辉三角
首先看到题目的图要明确一点:要实现的二维数组是每一行的元素个数不同,但并非按图上画的那般顺序排列,二维数组的图应该是这样的:
题中给的接口样式需要返回的是二维数组地址,传进来的是二维数组的行数。
对于这种问题,我们可以先创建一个二维数组模型,先建立行,再通过行来创建列,从而通过二维数组的下标访问每个元素。
创建二维数组模型:vector
建立行:vv.resize(numRows); //传参行数为numRows
通过行建立列(通过for循环实现):
for (int i = 0; i< vv.size(); ++i)
{
vv[i].resize(i + 1, 0);
}
同时观察杨辉三角图,每行首末元素都为1,所以在循环中将首末元素赋值为1:
for (int i = 0; i< vv.size(); ++i)
{
vv[i].resize(i + 1, 0);
vv[i][0] = vv[i][vv[i].size() - 1] = 1;
}
此时二维数组建立完成,首末元素为1,其余元素为0. 再观察图,发现每行非1元素 = 上一行同列元素 + 上一行同列元素前一个;
于是用for循环将每个非1元素的值填上:
for (int i = 0; i< vv.size(); ++i)
{
for (int j = 0; j< vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
最后返回二维数组首元素地址vv就可以了。
完整代码如下:
class Solution {
public:
vector>generate(int numRows) {
vector>vv;
vv.resize(numRows);
for (int i = 0; i< vv.size(); ++i)
{
vv[i].resize(i + 1, 0);
vv[i][0] = vv[i][vv[i].size() - 1] = 1;
}
for (int i = 0; i< vv.size(); ++i)
{
for (int j = 0; j< vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
return vv;
}
};
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页名称:vector使用指南-创新互联
路径分享:http://azwzsj.com/article/cdhdoo.html