十一、vector 类

Ⅰ . vector 的介绍和使用

01 vector 的介绍

vector 的文档介绍：vector

① vector 是表示可变大小数组的序列容器，既像数组，又不像数组

像体现在：同样采用连续存储空间存储元素，可以使用下标访问元素

不像体现在：大小是可以动态改变的

② 本质上来说，vector 使用动态分配数组来存储它的元素

当新元素插入时，为了增加存储空间，这个数组就需要被重新分配大小。具体做法是分配一个新的数组，然后将全部元素转移到这个新的数组。就时间而言，这是一个相对代价较高的任务，因为每当一个新的元素加入后，vector 并不会每次都重新分配大小。

③ vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因此存储空间会比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于末尾插入一个元素时是在常数时间的复杂度完成的。

因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且有一种有效的方式去动态增长。

④ 与其他动态序列容器相比：

vector 在访问元素时更加高效，末尾添加和删除元素相对高效

但是对于其他位置不在末尾的插入和删除操作，效率更低

vector 的底层是一个动态的顺序表

02 vector 的初始化

#include <vector>
using namespace std;

① 无参构造：

vector<int> v1;   // 无参构造，创建一个int类型的，空的vector对象

② 构造并初始化：

vector<int> v2(10, 1);   // 10个1

③ 迭代器区间初始化：

vector<int> v3(v2.begin(), v2.end());

④ 拷贝构造：

vector<int> v4(v2);

还可以不全部拷贝：

vector<int> v3(++v2.begin(), --v2.end());

对于迭代器区间初始化，它这里的 InputInerator 不一定是 vector Inerator。

它是一个模板，所以你传的是谁的迭代器，它就可以实例化出谁的迭代器

有时候我们可以这样初始化：

string s("hello world");
vector<char> v5(s.begin(), s.end());

03 调试观察

#include<iostream>
#include<vector>
#include<string>
using namespace std;void vector_test1()
{vector<int> v1;vector<int> v2(10, 1);vector<int> v3(v2.begin(), v2.end());vector<int> v4(v2);string s("hello world");vector<char> v5(s.begin(), s.end());
}int main()
{vector_test1();return 0;
}

04 string 和 vector 的区别

string 和 vector 有什么区别呢？刚才通过监视观察，感觉 vector char 已经很像 string 了。

能不能让 vector char 去替代 string 呢？这合适吗？

答案是不能，因为 vector char 没有 \0 ，而 string 结尾有 \0

那我直接给 vector char 后面手动装一个 \0 行嘛？

你要硬是想这么玩，也不是不可以

但他们两个体系不一样，vector 是顺序表，存的是任意类型，是针对可动态增长的数组的。

而 string 就只是字符串，我随便举两个例子：

① vector 支持正常的增删查改，但是不支持 += （本身也没必要+=），也不支持比较大小。

② vector 也没有 c_str 这些东西，因为 string 作为字符串专用的类，能提供专有的接口（比如 +=，find），所以这就是 string 存在的意义。

05 关于 vector 的析构、拷贝构造和赋值构造

至于析构函数，一般情况下我们不需要管，因为它会自动调用。

拷贝构造和赋值构造，vector 的拷贝构造和赋值其实就是深拷贝。

这些我们放在 vector 模拟实现的章节里详细探讨。

Ⅱ . vector 的遍历

01 push_back()

vector 不能使用 operator+=

string 能用 += 主要是 string 不仅可以尾插一个字符还可以追加一个字符串。

但是 vector 就只支持一个一个数据的插入和删除，push_back 和 pop_back

我们发现，vector 和 string 一样，是没有提供 push_front 和 pop_front 的，因为挪动数据效率低。

如果你硬是要去头插头删，可以用 insert 和 erase 去操作

举个例子：

void vector_Traversal_test() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);
}

02 下标 + 方括号遍历

vector 是连续的空间，又支持 operator[] 和 size() ，所以可以用下标+方括号遍历。

看代码：

void vector_Traversal_test() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 遍历for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;
}

当然也可以修改：

void vector_Traversal_test() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 遍历for (size_t i = 0; i < v.size(); i++){v[i] += 1;cout << v[i] << " ";}cout << endl;
}

03 访问 vector 的 at()

at() 和 operator[] 一样，也是用来访问 vector 的，但是 at() 会进行边界检查。

代码演示：

void vector_test2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);cout << v.at(0) << endl;cout << v.at(3) << endl;
}

注意：operator[] 会断言检查越界，at() 会抛异常

void vector_test2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);cout << v.at(0) << endl;cout << v.at(3) << endl;cout << v.at(4) << endl;
}

04 使用迭代器遍历

代码演示：

void vector_Traversal_test() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator it = v.begin();while (it != v.end()){*it -= 1;cout << *it << " ";it++;}cout << endl;
}

05 范围 for

vector 支持迭代器，也就支持范围 for，这个我们在模拟实现 string 的时候已经验证过了。

范围 for 的本质就是编译器在编译时自动替换成迭代器，这里也一样。

代码演示：

void vector_Traversal_test() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 范围forfor (auto e : v){cout << e << " ";}cout << endl;for (auto& e : v){e += 10;cout << e << " ";}cout << endl;
}

Ⅲ . vector 空间

01 获取数据个数的 size()

void vector_test3() 
{vector<int> v(6, 6);        // 生成6个6cout << v.size() << endl;
}

02 获取 vector 最大存储的 max_size()

void vector_test4()
{vector<int> v(6, 6);        cout << v.max_size() << endl;
}

03 改变 vector 容量的 reserve()

void vector_test5()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.reserve(100);
}

reserve 会扩容，但是不会影响数据个数。[capacity] 4 → [capacity]100

04 改变 vector 大小的 resize()

void vector_test6()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.resize(100);
}

string 的 resize 如果不指定 "填充值" ，默认给的是 \0

而 vector 的 resize 如果不指定，默认给的是其对应类型的缺省值作为 "填充值"

这里是 int 就是 0，如果是指针，对应的缺省值就是空指针。

提供特定的值：

void vector_test6()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.resize(100, 1);
}

注意：如果开的数据比之前更小，还会删除数据！

void vector_test6()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.resize(2);
}

这里虽然大小变成 2，数据也只有 [0]1 和 [1]2 了，但是容量仍然为 4

05 vector 空间增长问题

① capacity 的代码在 VS 和 g++下分别运行会发现：VS下 capacity 是按 1.5 倍增长的，而 g++ 下 capacity 是按 2 倍增长的。这个问题经常会考察，不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。VS 是 PJ 版本 STL，g++ 是 SGI 版本 STL。

② reserve 只负责开辟空间，如果确定知道需要用多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。

③ resize 在开空间的同时还会进行初始化，影响 size。

测试：

// vector::capacity
#include <iostream>
#include <vector>int main()
{size_t sz;std::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i = 0; i < 100; ++i) {foo.push_back(i);if (sz != foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}
}

Ⅳ . vector 增删查改

01 pop_back() 尾删

代码实现：

void vector_test7() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);for (auto e : v) cout << e << " "; cout << endl;v.pop_back();   // 尾删：3for (auto e : v) cout << e << " "; cout << endl;v.pop_back();   // 尾删：2for (auto e : v) cout << e << " "; cout << endl;
}

02 assign() 赋值

用 $n$ 个 value 覆盖：

void vector_test8() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.assign(10, 5);   // 原来是1到4，现在改成10个5
}

03 为什么 vector 不提供 find 接口

string、map、set 都有 find() 用，凭什么 vector 和 list 没有

其实，我们应该考虑的是 —— 为什么 string、map、set 能有 find 操作。

而 vector 之所以不提供 find ，是因为如果去查找元素效率就会是 $O(n)$ ...

凭什么不让我 vector 用 find() ，我偏要用！

可以的，"algorithm库" 里有通用的 find 操作，我们来一睹其芳容 ——

#include <algorithm>

该 find 内部是从 begin 到 end 进行一次遍历，其复杂度是 $O(n)$

值得一提的是，在C++中，凡是使用迭代器区间，都是左闭右开的

再去思考 map、set 为什么有 find() 通过迭代器从头到尾遍历 map 与 set 时，

得到的结果是按 key 排序的结果，而不是插入时的顺序，所以这两个容器没有 push_back 操作。

其实，插入到 map 与 set 中的元素会被组织到一颗红黑树上，红黑树是一颗平衡二叉树，

平衡二叉树是一颗二叉排序树，对一颗二叉排序树的查找有点像二分查找，复杂度是，

由于 map 与 set 的数据结构能有更快的查找方法，所以在容器内提供了 find 方法

04 通用查找 find()

如果非要在 vector 里用 find() ，我们可以用通用 find。

找到了：返回一个迭代器区间那个值的位置；

没找到：返回的是 $last$ ，即右边开区间的位置。

代码演示：

void vector_test9() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator ret = find(v.begin(), v.end(), 3);// auto ret = find(v.begin(), v.end(), 3);if (ret != v.end()) {cout << "找到了" << endl;}
}

05 insert() 插入

比如我们刚才用通用 find 找到了 3 的位置，

我们想在这个位置前面插入一个数据，就可以使用 insert() 插入。

在 3 前面插入一个 30：

void vector_test9() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator ret = find(v.begin(), v.end(), 3);// auto ret = find(v.begin(), v.end(), 3);if (ret != v.end()) {cout << "找到了" << endl;v.insert(ret, 30);}for (auto e : v) cout << e << " "; cout << endl;
}

虽然没有 vector 没有提供 push_front，但是我们也可以用 insert 去头插

代码演示：

void vector_test10() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v) cout << e << " "; cout << endl;v.insert(v.begin(), -1);   // 在起始位置插入一个-1for (auto e : v) cout << e << " "; cout << endl;
}

06 erase() 删除

我们我们想删除数据，我们就可以用 erase 去删除

代码演示：

void vector_test11() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v) cout << e << " "; cout << endl;vector<int>::iterator pos = find(v.begin(), v.end(), 3);if (pos != v.end()) {   // 判断pos是否存在v.erase(pos);       // 删除pos}for (auto e : v) cout << e << " "; cout << endl;
}

如果没有判断会怎么样？

void vector_test11() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v) cout << e << " "; cout << endl;vector<int>::iterator pos = find(v.begin(), v.end(), 3);v.erase(pos);       for (auto e : v) cout << e << " "; cout << endl;
}

如果要删除的目标存在，不会怎么样。

怕的就是要删的目标不存在！比如我要删个 5，但是 vector 里只有 1，2，3，4 。

vector<int>::iterator pos = find(v.begin(), v.end(), 5);
v.erase(pos);

如果有了判断，就不会翻车了，如果待删目标不存在，就不会去走 erase()

因为 pos 如果找不到就会等于 end() 上的值，我们利用这一点进行 if 判断

	vector<int>::iterator pos = find(v.begin(), v.end(), 5);if (pos != v.end()) {   // 检查！v.erase(pos);}

07 clear() 清空数据

void vector_test12() 
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);printf("清空前：");for (auto e : v) cout << e << " "; cout << endl;v.clear();printf("清空后：");for (auto e : v) cout << e << " "; cout << endl;
}