🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《C++》 《Linux》 《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️

---

前言

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

---

一、默认成员函数

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

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

1.1 默认构造

vector 支持三种默认构造方式

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

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

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

	string s = "abcdefg";
	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 都会受到影响

---

二、迭代器

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

vector 支持下标随机访问， 所以大多数情况下访问数据都是使用下标，但 迭代器 相关接口它还是有的

vector 和 string 的 迭代器 本质上就是原生指针，比较简单，但后续容器的 迭代器 就比较复杂了

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

注：string 和 vector 的迭代器都是 随机迭代器(RandomAccessIterator)，可以随意走动，支持全局排序函数 sort

2.1 正向迭代器

正向迭代器即 从前往后 遍历的 迭代器

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

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 Iterator!";
vector<char> v(ps, ps + strlen(ps));

vector<char>::reverse_iterator rit = v.rbegin();

while (rit != v.rend())
{
	cout << *rit;
	++rit;
}
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 中的这个新语法完全没必要，可以不用，但不能看不懂

---

三、容量相关

下面来看看 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
• 这种构造方法称为 匿名构造，后续会经常简单（很方便）

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

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

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

resize 和 reserve：

• 两者的共同点是都能起到扩容的效果

• resize 扩容的同时还能进行初始化，reserve 则不能

• resize 会改变 _finish，而 reserve 不会

• 对于两者来说，当 n 小于等于 capacity() 时，都不进行扩容操作

  • resize 此时会初始化 size() 至 capacity() 这段空间

3.4 缩容

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

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

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

---

四、数据访问相关

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

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];
    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() 就是返回 \*_start，back() 则是返回 \*_finish

---

五、数据修改相关

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++;	//再次使用迭代器
}

不止 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::swap，std::swap 实际在交换时，需要调用多次拷贝构造和赋值重载函数，对于深拷贝来说，效率是很低的

• 而 vector::swap 在交换时，交换是三个成员变量，因为都是指针，所以只需要三次浅拷贝交换，就能完美完成任务

• 实际在 vector::swap 内部，还是调用了 std::swap，不过此时是高效的浅拷贝

至于 clear 函数，实现很简单：

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