1. vector的常用函数
1.1 vector 的介绍
文档链接：
https://cplusplus.com/reference/vector/vector/
① vector 是表示可变大小数组的序列容器，我们说 vector 像数组，但是又不像数组。
说它像数组体现在：vector 就像是数组一样，它也是采用连续存储空间来存储元素的。这也就意味着我们可以用下标访问 vector 的元素，和数组一样的高效。
说它不像数组体现在：vector 的大小是可以动态改变的，而且它的大小会被容器自动处理。
② 本质上来说，vector 使用动态分配数组来存储它的元素。
当新元素插入时，为了增加存储空间，这个数组就需要被重新分配大小。具体做法是分配一个新的数组，然后将全部元素转移到这个新的数组。就时间而言，这是一个相对代价较高的任务，因为每当一个新的元素加入后，vector 并不会每次都重新分配大小。
③ vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因此存储空间会比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于末尾插入一个元素时是在常数时间的复杂度完成的。
因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且由一种有效的方式去动态增长。
④ 与其它动态序列容器相比（deques, lists and forward_lists）：
vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。 但是对于其它不在末尾的删除和插入操作，效率更低。比起 lists 和 forward_lists 统一的迭代器和引用更好。
vector 的底层就是一个动态的顺序表
1.2 vector 的初始化
vector 是一个类模板，所以需要显示类型转化了：
#include<iostream> #include<vector> using namespace std; int main() { vector<int> v1; vector<int> v2(10, 1); vector<int> v3(v2); vector<int> v4(v2.begin(), v2.end()); string str("hello world"); vector<char> v5(str.begin(), str.end()); return 0; }
string 和 vector 有什么区别呢？刚才通过监视观察，感觉 vector char 已经很像 string 了。
能不能让 vector char 去替代 string 呢？这合适吗？
答案是否定的。因为 vector char 没有 \0，而 string 结尾是有 \0 的。
那给 vector char 后面手动装一个 \0 行吗？
也不是不可以。但是 "术业有专攻" ，他们俩的体系是不一样的。
vector 是顺序表，存的是任意类型，是针对可动态增长的数组的。
vector 支持正常的增删查改，但是不支持 += （本身也没必要+=），也不支持比较大小。
vector 也没有 c_str 这些东西，因为 string 作为字符串专用的类，能提供专有的接口（比如 +=，find），所以这就是 string 存在的意义。
关于析构函数，一般情况下我们不需要管，因为它会自动调用。
拷贝构造和赋值构造，vector 的拷贝构造和赋值其实就是深拷贝。
这些我们放在 vector 模拟实现的章节里详细探讨。
1.3 vector 的操作和遍历
先简单介绍3种 vector 的遍历方式，然后再介绍一些访问元素的接口。
其中为了讲解 "下标 + 方括号" 的遍历方式，先提前介绍一下 vector 的 push_back 。
除此之外还有反向迭代器、const 迭代器……就不一一介绍了，具体可以看文档。
vector 不能用很方便的 operator+= ，
string 能用 += 主要是 string 不仅可以尾插一个字符还可以追加一个字符串。
但是 vector 就只支持一个一个数据的插入和删除，push_back 和 pop_back。
vector 的接口和我们在数据结构实现过的顺序表都差不多。
而且学了string 大多都会用了，所以只简单介绍几个，剩下的可以自己查文档。
需要注意的是：operator[] 会用断言检查越界，而 at() 会抛异常，平时基本不用at() 的。
vector 和 string 一样，是没有提供 push_front 和 pop_front 的，因为挪动数据效率低。
虽然可以用 insert 和 erase 去操作，但效率确实低，不建议。测试一下vector 的遍历：
#include<iostream> #include<vector> using namespace std; void Test1() { 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; for (size_t i = 0; i < v.size(); i++) { v[i] += 1; // 每个元素+1 cout << v[i] << " "; } cout << endl; vector<int>::iterator it = v.begin();// 迭代器遍历 自然也可用范围for 不演示了 while (it != v.end()) { *it -= 1; // 令每个元素-1 cout << *it << " "; it++; } cout << endl; } int main() { Test1(); return 0; }
1.4 vector 的容量和增删查改
和string 一样， " reserve 和 resize 都是卖房子的（开空间的），reserve 只是把房子卖给你（开空间），而 resize 是一条龙服务，房子卖给你（开空间）之后还帮你搞装修（初始化），你还可以指定装修风格（初始化内容），如果不指定会按默认的简约风格装修（按类型的缺省值初始化）" resize 如果开的数据比之前更小，还会删除数据。
capacity 的代码在 VS 和 g++下分别运行会发现
：VS下 capacity 是按 1.5 倍增长的，而 g++ 下 capacity 是按 2 倍增长的。 这个问题经常会考察，不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。VS 是 PJ 版本 STL，g++ 是 SGI 版本 STL。
为什么 vector 不提供 find 接口：
string、map、set 都有 find() 用，凭什么 vector 和 list 没有？
其实，我们应该考虑的是 —— 为什么 string、map、set 能有 find 操作。
而 vector 之所以不提供 find ，是因为如果去查找元素效率就会是O（N）
但是"algorithm库" 里有通用的 find 操作
该 find 内部是从 begin 到 end 进行一次遍历，其复杂度是O（N）
值得一提的是，在C++中，凡是使用迭代器区间，都是左闭右开的
（map 和 set 接下来的章节会讲，以下部分可先作了解）
再去思考 map、set 为什么有 find() 通过迭代器从头到尾遍历 map 与 set 时，
得到的结果是按 key 排序的结果，而不是插入时的顺序，所以这两个容器没有 push_back 操作。
其实，插入到 map 与 set 中的元素会被组织到一颗红黑树上，红黑树是一颗平衡二叉树，
平衡二叉树是一颗二叉排序树，对一颗二叉排序树的查找有点像二分查找，复杂度是O（logN）
由于 map 与 set 的数据结构能有更快的查找方法，所以在容器内提供了 find 方法。
用的话大概就是这么用：这时候你就要记一下algorithm这个头文件怎么拼的了。
find()函数返回一个迭代器，指向范围内搜索元素的第一次出现。如果没有找到目标元素，则返回查找范围的结尾。
void Test2() { 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 << "找到了，下标是：" << ret << endl; } else { cout << "没找到" << endl; } }
剩下的接口学过前面的应该都会了。
