放在专栏【C++知识总结】,会持续更新,期待支持🌹
vector是一个表示可变大小数组的序列容器,与我们平常定义的数组类似,区别在于vector在进行插入操作时,如果空间不足,会自动扩容。由于vector采用连续空间来进行存储数据,所以我们可以采用下标,来访问元素。
在SGI版本的STL中,vector的数据结构非常简单,就三个迭代器,以start和finish分别指向空间的头和已使用的尾,以end_of_storage指向整块空间的尾端。如下图所示:
接下来将进行讲解vector的常用接口的使用
我们在使用vector时,首先要记得包<vector>的头文件,在定义一个vector时,有以下几种定义方式:
一:构造一个空的vector
vector<int> v;//定义一个元素为int类型的空容器
二:构造含有n个val的某类型容器,当不指定val时,会默认初始化为0
vector<int> v(10,1) //1 1 1 1 1 1 1 1 1 1
vector<int> vv(10) //0 0 0 0 0 0 0 0 0 0
三:拷贝构造
vector<int> v1(5,2);
vector<int> v2(v1);//拷贝构造,此时v2:2 2 2 2 2
//也可以写成vector<int> v2=v1;
四:迭代器区间构造
string s="hello world";
vector<char> v(s.begin(),s.begin()+5);//v:h e l l o
2.2.1、size与capacity
与string一样,vector的size()接口返回的是目前已经使用空间的大小,而capacity()返回的是整块空间的大小。如下所示:
与string也是相同,resize改变的是size的大小,可能会间接影响到capacity,而reserve是直接改变capacity的大小,不会影响size。并且在reserve(n)时,如果n的大小小于capacity,此时不会做"缩容操作"。
在进行reserve扩容时,vector是采用异地扩容,即会新开辟一块空间,然后将旧空间内容拷贝进新空间,同时将旧空间free。我们可以来验证一下:
我们还可以通过如下代码,来观察vs下以及linux下vector的默认扩容机制。(vs使用PJ版本的STL,linux中g++使用SGI版本的STL,进行对比)
void TestVectorExpand()
{
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';
}
}
}
(我们知道,扩容是有一定代价的,因此我们在编程时,假如知道待扩容空间的总大小,我们可以提前进行reserve。)
访问vector的元素,无非就这么几种:通过迭代器进行访问、通过[],利用数组下标访问、范围for(实际底层还是迭代器)。
在string章节中就提到了迭代器相关概念,迭代器就是用一个对象,来模拟指针行为,实现对容器成员进行访问,是所有容器中通用的方法。而string与vector,我们查看它的底层实现,起始这里的迭代器就是指针。(原因在于vector与string的存储空间连续)。
在这里,我们使用迭代器进行成员访问,很简单,如下所示:
迭代器除了有这种用来正向遍历的,vector还提供了一种反向迭代器reverse_iterator,rbegin()与rend(),如下图:
当然,vector还提供了一中const迭代器,const迭代器的特点就是不能对其指向的空间元素进行修改。如下所示:
我们知道,迭代器就是用一个对象来模拟指针行为(++、--),从而实现对容器元素的访问(*解引用)(string与vector在SGI版本下的迭代器就是指针本身)。迭代器失效意思就是指"指针"指向的空间已经被销毁,即指针指向了一块已经被free的空间。或者指向一块不属于它应该指向的空间。如果此时对成员进行访问,即指针的解引用操作,就会使程序崩溃。
因此,只要是涉及到底层空间发生改变的操作(如插入、删除、扩容等),都有可能引发迭代器失效。这里简单举几个例子:
VS下对于任何迭代器失效的处理,是直接报错,但是Linux下对有些迭代器失效引发的问题处理并不会这么严格,就好像下面这种情况:
该情况也是属于迭代器失效,虽然程序没有崩溃,但是结果却是错误的,同样的代码我们在VS下运行,是直接崩溃的,因为VS检查非常严格:
如何解决迭代器失效?
其实我们可以在使用迭代器之前对其重新赋值,确保当前迭代器为“最新”的即可,也就是更新迭代器,使迭代器指向当前想要的空间,就可以避免该问题。
如下所示,我们还是在删除2之前进行尾插,使其进行扩容,从而引发迭代器失效,但是我们在删除2之前对其重新赋值:
前者为尾插,后者为尾删。接口用起来也很简单。
insert可以实现在任意位置的插入一个或多个元素,erase则可以实现任意位置删除一个或多个元素,如下:
这里我们需要知道,vector的尾插尾删操作十分高效,时间复杂度为O(1),但是头插头删效率则远远不如尾部操作,时间复杂度为O(N)。
find函数可以用来实现在区间[begin,end)内进行查找,假如在[begin,end)区间内查找val,则可以这样来实现:find(begin,end,val);返回值为该位置的迭代器。不过需要注意的是,find并不是vector的成员函数,使用find需要包含头文件<algorithm>。在上文多个例子中已经多次使用,这里就不再演示,需要注意迭代器失效相关问题。
用来交换两个容器空间,如下:
以上为常用接口,其余可以自行查看相关文档进行了解。cplusplus.com/reference/
end.
生活原本沉闷,但跑起来就会有风!🌹