✨个人主页: Yohifo
🎉所属专栏: C++修行之路
🎊每篇一句: 图片来源

  • The power of imagination makes us infinite.
    • 想象力的力量使我们无限。

遇见彩虹,吃定彩虹



📘前言

vector 是表示可变大小数组的序列 容器,其使用的是一块 连续 的空间,因为是动态增长的数组,所以 vector 在空间不够时会扩容;vector 优点之一是支持 下标的随机访问,缺点也很明显,头插或中部插入效率很低,这和我们之前学过的 顺序表 性质很像,不过在结构设计上,两者是截然不同的

两者区别


📘正文

本文介绍的是 vector 部分常用接口

1、默认成员函数

vector 的成员变量如上图所示,就是三个指针,分别指向:

  • _start 指向空间起始位置,即 begin()
  • _finish 指向最后一个有效元素的下一个位置,相当于 end()
  • _end_of_storage 指向已开辟空间的终止位置

结构

1.1、默认构造

vector 支持三种默认构造方式

  1. 默认构造大小为 0 的对象
  2. 构造 n 个元素值为 val 的对象
  3. 通过迭代器区间构造,此时元素为自定义类型,如 stringvectorDate

默认构造

int main()
{
	vector<int> v1;	//构造元素值为 int 的对象

	vector<char> v2(10, 'x');	//构造10个值为'x'的对象

	string s = "abcedfg";
	vector<char> v3(s.begin(), s.end());	//构造 s 区间内的元素对象
	return 0;
}

结果
注:也可以直接通过 vector<int> v4 = {1, 2, 3} 的方式构造对象,不过此时调用了 拷贝构造 函数

vector<int> v4 = {1, 2, 3};	//这种构造方式比较常用,有点像数组赋初始值

1.2、拷贝构造

拷贝构造将对象 x 拷贝、构造出新对象 v拷贝构造 函数的使用方法很简单,利用一个已经存在的 vector 对象,创建出一个值相同的对象

拷贝构造

vector<int> x = { 1,2,3,4,5 };

vector<int> v(x);	//利用对象 x 构造出 v

结果
可以看到,对象 v 和对象 x 的值是一样的(copy)

注意: 调用拷贝构造时,两个对象类型需匹配,且被复制对象需存在

拷贝构造赋值重载深度拷贝 的讲究,在模拟实现 vector 时演示

1.3、析构函数

析构函数,释放动态开辟的空间,因为 vector 使用的空间是连续的,所以释放时直接通过 delete[] _start 释放即可

析构函数 会在对象生命周期 结束时自动调用,平常在使用时无需关心

析构函数

// ~vector 函数内部
delete[] _start;
_start = _finish = _end_of_storage = nullptr;

1.4、赋值重载

拷贝构造 的目的是创建一个新对象,赋值重载 则是对一个老对象的值进行 改写

赋值重载

int arr[] = { 6,6,8 };
vector<int> v1(arr, arr + (sizeof(arr) / sizeof(arr[0])));	//迭代器区间构造

vector<int> v2;	//创建一个空对象
v2 = v1;	//将 v1 的值赋给老对象 v2

赋值重载
注意: v1 对象赋值给 v2 对象后,v1 本身并不受任何影响,改变的只是 v2

赋值重载 函数有返回值,适用于多次赋值的情况

vector<int> v3 = { 9,9,9 };
v2 = v1 = v3;	//这样也是合法的,最终 v1、v2 都会受到影响

2、迭代器

迭代器 是一个天才设计,它的出现使得各种各样的容器都能以同一种方式进行 访问遍历 数据

vector 支持下标随机访问, 所以大多数情况下访问数据都是使用下标,但 迭代器 相关接口它还是有的
迭代器
vectorstring迭代器 本质上就是原生指针,比较简单,但后续容器的 迭代器 就比较复杂了

复杂归复杂,但每种 容器 的迭代器使用方法都差不多,这就是 迭代器 设计的绝妙之处

注:stringvector 的迭代器都是 随机迭代器(RandomAccessIterator),可以随意走动,支持全局排序函数 sort

迭代器分类

2.1、正向迭代器

正向迭代器即 从前往后 遍历的 迭代器
正向迭代器
利用迭代器正向遍历 vector 对象

const char* ps = "Hello Iterator!";
vector<char> v(ps, ps + strlen(ps));	//迭代器构造

vector<char>::iterator it = v.begin();	//创建该类型的迭代器

while (it != v.end())
{
	cout << *it;
	it++;
}
cout << endl;

结果
注意:

  • 迭代器在创建时,一定要先写出对应的类型,如 vector<int>,嫌麻烦可以直接用 auto 推导
  • 在使用迭代器遍历时,结束条件为 it != v.end() 不能写成 <,因为对于后续容器来说,它们的空间不是连续的,判断小于无意义
  • begin() 为第一个有效元素地址,end() 为最后一个有效元素的下一个地址

vector随机迭代器,也支持这样玩

//auto 根据后面的类型,自动推导迭代器类型
auto it = v.begin() + 3;	//这是随机的含义

2.2、反向迭代器

反向迭代器常用来 反向遍历(从后往前)容器

反向迭代器
反向遍历 vector 对象

const char* ps = "Hello ReverseIterator!";
vector<char> v(ps, ps + strlen(ps));

vector<char>::reverse_iterator it = v.rbegin();	//创建该类型的迭代器

while (it != v.rend())
{
	cout << *it;
	it++;
}
cout << endl;

结果
反向迭代器的注意点与正向迭代器一致,值得注意的是 rbegin()rend()
反向迭代
begin()end() 适用于 正向迭代器

  • begin() 为对象中的首个有效元素地址
  • end() 为对象中最后一个有效元素的下一个地址

rbegin()rend() 适用于 反向迭代器

  • rbegin() 为对象中最后一个有效元素地址
  • rend() 为对象中首个有效元素的上一个地址

注意: begin() 不能和 rend() 混用

上述 迭代器 都是用于正常 可修改 的对象,对于 const 对象,还有 cbegin()cend()crbegin()crend(),当然这些都是 C++11 中新增的语法

其他迭代器

注:对于 const 对象,存在重载版本,如 begin() const,也就是说,const 修饰的对象也能正常使用 begin()end()rbegin()rend()C++11 中的这个新语法完全没必要,可以不用,但不能看不懂


3、容量相关

下面来看看 vector 容量相关函数和扩容机制

3.1、大小、容量、判空

大小 size()
容量 capacity()
判空 empty()

这些函数对于我们太熟悉了,和 顺序表 的一模一样

接口
直接拿来用一用

vector<int> v = { 1,2,3,4,5 };
cout << "size:" << v.size() << endl;
cout << "capacity:" << v.capacity() << endl;
cout << "empty:" << v.empty() << endl;

结果
这几个函数都是直接拿来用的,没什么值得注意的地方

3.2、空间扩容

连续空间可扩容,像 string 一样,vector 也有一个提前扩容的函数:reserve()
输入指定容量即可扩容,常用来 提前扩容避免因频繁扩容而导致的内存碎片

下面来通过一个小程序先来简单看看 PJ 版 和 SGI 版的 默认扩容机制

vector<int> v;
size_t capacity = v.capacity();
cout << "Default capacity:" << capacity << endl;

int i = 0;
while (i < 100)
{
	v.push_back(i);	//尾插元素 i

	//如果不相等,证明出现扩容
	if (capacity != v.capacity())
	{
		capacity = v.capacity();
		cout << "New capacity:" << capacity << endl;
	}

	i++;
}

扩容机制
可以看出,PJ 版采用的是 1.5 倍扩容法,而 SGI 版直接采用 2 倍扩容法,待扩容量较小时,PJ 版会扩容更多次,浪费更多空间;但待扩容量越大时,变成 SGI 版浪费更多空间,总的来说,两种扩容方式各有各的优点

如果我们提前知道待扩容空间大小 n,可以直接使用 reserve(n) 的方式进行 提前扩容,这样一来,无论是哪种版本,最终容量大小都是一致的,且不会造成空间浪费

v.reserve(100);	//提前开辟空间

提前扩容
此时是非常节约空间的,而且不会造成很多的内存碎片

注意: n 小于等于 capacity() 时,reserve 函数不会进行操作

3.3、大小调整

与提前扩容相似的大小调整,主要调整的是 _finish

在扩容的同时对新空间进行初始化,参数2 val 为缺省值,缺省为对应对象的默认构造值

  • 自定义类型也有默认构造函数,如 int(),构造后为 0
  • 这种构造方法称为 匿名构造,后续会经常简单(很方便)

resize

vector<int> v1;
v1.resize(10);	//使用缺省值

vector<int> v2;
v2.resize(10, 6);	//使用指定值

resize
区别在于:是否指定初始化值

resizereserve

  • 两者的共同点是都能起到扩容的效果
  • resize 扩容的同时还能进行初始化,reserve 则不能
  • resize 会改变 _finish,而 reserve 不会
  • 对于两者来说,当 n 小于等于 capacity() 时,都不进行扩容操作
    • resize 此时会初始化 size()capacity() 这段空间

3.4、缩容

vector 中还提供一个了缩容函数,将原有容量缩小,但这完全没必要,以下是缩容步骤:

  • 开辟新空间(比原空间更小的空间)
  • 用原空间中的数据将新空间填满,超出部分丢弃
  • 释放原空间,完成缩容

为了一个缩容而导致的是代价是很大的,因此 不推荐缩容想要改变 size() 时,可以使用 resize 函数

缩容函数
这里就不演示这个函数了,就连官方文档上都有一个 警告标志


4、数据访问相关

连续空间数据访问时,可以通过 迭代器,也可以通过 下标,这里还是更推荐使用 下标,因为很方便;作为 “顺序表”,当然也支持访问首尾元素

4.1、下标随机访问

下标访问是通过 operator[] 运算符重载实现的

下标访问
库中提供了两个重载版本,用以匹配普通对象和 const 对象

const char* ps = "Hello";
vector<char> v(ps, ps + strlen(ps));	//迭代器区间构造
const vector<char> cv(ps, ps + strlen(ps));	//迭代器区间构造

size_t pos = 0;	//下标
while (pos < v.size())
{
	cout << v[pos];	//普通对象
	cout << cv[pos];	//const 对象
	pos++;
}
cout << endl;

结果
除了 operator[] 以外,库中还提供了一个 at 函数,实际就是对 operator[] 的封装

v.at(0);
v[0]	//两者是完全等价的

注意: 因为是下标随机访问,所以要小心,不要出现 越界 行为

4.2、首尾元素

front() 获取首元素,back() 获取尾元素

vector<int> v = { 1,1,1,0,0,0 };
cout << "Front:" << v.front() << endl;
cout << "Back:" << v.back() << endl;

结果
实际上,front() 就是返回 *_startback() 则是返回 *_finish


5、数据修改相关

vector 也可以随意修改其中的数据,比如尾部操作,也支持任意位置操作,除此之外,还能交换两个对象,亦或是清除对象中的有效元素

5.1、尾插尾删

push_back()pop_back() 算是老相识了,两个都是直接在 _finish 上进行操作

文档
这两个函数操作都很简单,不再演示

注意: 如果对象为空,是不能尾删数据的

对于已有对象数据的修改,除了赋值重载外,还有一个函数 assign(),可以重写指定对象中的内容,使用方法很像默认构造函数,但其本质又和赋值重载一样
重写
第一种方式是通过迭代器区间赋值,第二种是指定元素数和元素值赋值

5.2、任意位置插入删除

任意位置插入删除是使用 vector 的重点,因为这里会涉及一个问题:迭代器失效,这个问题很经典,具体什么原因和如何解决,将在模拟实现 vector 中解答

文档
简单演示一下用法:

int arr[] = { 6,6,6 };
vector<int> v = { 1,0 };

//在指定位置插入一个值
v.insert(find(v.begin(), v.end(), 1), 10);	//10,1,0

//在指定位置插入 n 个值
v.insert(find(v.begin(), v.end(), 0), 2, 8);	//10,1,8,8,0

//在指定位置插入一段迭代器区间
v.insert(find(v.begin(), v.end(), 8), arr, arr + (sizeof(arr) / sizeof(arr[0])));	//10,1,6,6,6,8,8,0

//删除指定位置的元素
v.erase(find(v.begin(), v.end(), 10));	//1,6,6,6,8,8,0

//删除一段区间
v.erase(v.begin() + 1, v.end());	//1

先浅浅演示一下 迭代器失效的场景

vector<int> v = { 1,2,3 };
auto it = v.end();	//利用迭代器模拟尾插

for (int i = 0; i < 5; i++)
{
	v.insert(it, 10);
	it++;	//再次使用迭代器
	i++;
}

运行(调试模式下)结果是这样的:

报错

不止 insert 的迭代器会失效,erase 的迭代器也会失效

简单来说:插入或删除后,可能导致迭代器指向位置失效,此时没有及时更新,再次使用视为非法行为

因此我们认为 vector 在插入或删除后,迭代器失效,不能再使用,尤其是 PJ 版本,对迭代器失效的检查十分严格

至于其具体原因和方法,留在下篇文章中揭晓

5.3、交换、清理

还剩下两个简单函数,简单介绍下就行了

函数

vector<int> v1 = { 1,2,3 };
vector<int> v2 = { 4,5,6 };

v1.swap(v2);	//交换两个对象

v1.clear();
v2.clear();	//清理

std 中已经提供了全局的 swap 函数,为何还要再提供一个呢?

  • 这个函数实现原理不同 std::swapstd::swap 实际在交换时,需要调用多次拷贝构造和赋值重载函数,对于深拷贝来说,效率是很低的
  • vector::swap 在交换时,交换是三个成员变量,因为都是指针,所以只需要三次浅拷贝交换,就能完美完成任务
  • 实际在 vector::swap 内部,还是调用了 std::swap,不过此时是高效的浅拷贝

至于 clear 函数,实现很简单:

  • _finish 等于 _start,就完成了清理,不需要进行缩容,这样做是低效的

关于 vector 更多、更详细的内容,欢迎移步 《C++ STL学习之【vector的模拟实现】》


6、相关试题

光知道怎么使用是不够的,还需要将知识付诸于实践,切忌纸上谈兵

下面是一些比较适合练习使用 vector 的试题,可以做做

vector 值得做的题目


📘总结

以上就是本次关于 STLvector 的全部讲解了,vector 相对来说函数比较少,也比较好理解,不过在实际使用中,会存在不少问题,需要对 vector 的不断使用以提高认知,如果对 vector 剩余函数感兴趣,可以阅读官方文档 vector

如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正


星辰大海

相关文章推荐

STL 之 string 类

C++ STL学习之【string类的模拟实现】

C++ STL 学习之【string】

===============

内存、模板

C++【模板初阶】

C/C++【内存管理】

===============

类和对象实操

类和对象实操之【日期类】

感谢支持

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐