【STL】vector的使用

诺诺的包包

发布于 2023-10-15 13:57:34

1500

发布于 2023-10-15 13:57:34

文章被收录于专栏：个人笔记总结个人笔记总结

放在专栏【C++知识总结】，会持续更新，期待支持🌹

1、vector介绍

1.1、什么是vector？

vector是一个表示可变大小数组的序列容器，与我们平常定义的数组类似，区别在于vector在进行插入操作时，如果空间不足，会自动扩容。由于vector采用连续空间来进行存储数据，所以我们可以采用下标，来访问元素。

1.2、vector的数据结构

在SGI版本的STL中，vector的数据结构非常简单，就三个迭代器，以start和finish分别指向空间的头和已使用的尾，以end_of_storage指向整块空间的尾端。如下图所示：

接下来将进行讲解vector的常用接口的使用

2、vector的使用

2.1、构造相关

我们在使用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、容量相关

2.2.1、size与capacity

与string一样，vector的size()接口返回的是目前已经使用空间的大小，而capacity()返回的是整块空间的大小。如下所示：

2.2.2、resize与reserve

与string也是相同，resize改变的是size的大小，可能会间接影响到capacity，而reserve是直接改变capacity的大小，不会影响size。并且在reserve(n)时，如果n的大小小于capacity，此时不会做"缩容操作"。

2.2.3、vector扩容策略

在进行reserve扩容时，vector是采用异地扩容，即会新开辟一块空间，然后将旧空间内容拷贝进新空间，同时将旧空间free。我们可以来验证一下：

2.2.4、vector默认扩容机制

我们还可以通过如下代码，来观察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。）

2.3、元素访问

访问vector的元素，无非就这么几种：通过迭代器进行访问、通过[]，利用数组下标访问、范围for(实际底层还是迭代器)。

2.3.1、迭代器

在string章节中就提到了迭代器相关概念，迭代器就是用一个对象，来模拟指针行为，实现对容器成员进行访问，是所有容器中通用的方法。而string与vector，我们查看它的底层实现，起始这里的迭代器就是指针。（原因在于vector与string的存储空间连续）。

在这里，我们使用迭代器进行成员访问，很简单，如下所示：

迭代器除了有这种用来正向遍历的，vector还提供了一种反向迭代器reverse_iterator，rbegin()与rend（）,如下图：

当然，vector还提供了一中const迭代器，const迭代器的特点就是不能对其指向的空间元素进行修改。如下所示：

2.3.2、关于迭代器失效问题

我们知道，迭代器就是用一个对象来模拟指针行为（++、--），从而实现对容器元素的访问（*解引用）（string与vector在SGI版本下的迭代器就是指针本身）。迭代器失效意思就是指"指针"指向的空间已经被销毁，即指针指向了一块已经被free的空间。或者指向一块不属于它应该指向的空间。如果此时对成员进行访问，即指针的解引用操作，就会使程序崩溃。

因此，只要是涉及到底层空间发生改变的操作（如插入、删除、扩容等），都有可能引发迭代器失效。这里简单举几个例子：

VS下对于任何迭代器失效的处理，是直接报错，但是Linux下对有些迭代器失效引发的问题处理并不会这么严格，就好像下面这种情况：

该情况也是属于迭代器失效，虽然程序没有崩溃，但是结果却是错误的，同样的代码我们在VS下运行，是直接崩溃的，因为VS检查非常严格：

如何解决迭代器失效？

其实我们可以在使用迭代器之前对其重新赋值，确保当前迭代器为“最新”的即可，也就是更新迭代器，使迭代器指向当前想要的空间，就可以避免该问题。

如下所示，我们还是在删除2之前进行尾插，使其进行扩容，从而引发迭代器失效，但是我们在删除2之前对其重新赋值：

2.4、增删查改

push_back与pop_back

前者为尾插，后者为尾删。接口用起来也很简单。

insert与erase

insert可以实现在任意位置的插入一个或多个元素，erase则可以实现任意位置删除一个或多个元素，如下：

这里我们需要知道，vector的尾插尾删操作十分高效，时间复杂度为O(1)，但是头插头删效率则远远不如尾部操作，时间复杂度为O(N)。

find函数

find函数可以用来实现在区间[begin,end)内进行查找，假如在[begin,end)区间内查找val，则可以这样来实现:find(begin,end,val)；返回值为该位置的迭代器。不过需要注意的是，find并不是vector的成员函数，使用find需要包含头文件<algorithm>。在上文多个例子中已经多次使用，这里就不再演示，需要注意迭代器失效相关问题。