Ⅲ. vector 空间
0x00 获取数据个数的 size()
💬 和 string 里的一样，是用来获取数据的个数的。
void test_vector2() { vector<int> v(6, 6); // 生成6个6 cout << v.size() << endl; }
🚩 运行结果如下：
0x01 获取 vector 最大存储的 max_size()
💬 我们来用 max_size 看看有多大：
void test_vector3() { vector<int> v(6, 6); // 生成6个6 cout << v.max_size() << endl; }
🚩 运行结果如下：
0x02 改变 vector 容量的 reserve()
💬 reserve：
void test_vector3() { 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
0x03 改变 vector 大小的 resize()
" reserve 和 resize 都是卖房子的（开空间的），reserve 只是把房子卖给你（开空间），而 resize 是一条龙服务，房子卖给你（开空间）之后还帮你搞装修（初始化），你还可以指定装修风格（初始化内容），如果不指定会按默认的简约风格装修（按类型的缺省值初始化）"
💬 resize：
void test_vector4() { 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，如果是指针，对应的缺省值就是空指针。
💬 我们来试着给 resize 提供指定 "填充值"：
void test_vector5() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.resize(100, 6); // 开100个空间，用6补 }
📌 注意事项：如果开的数据比之前更小，还会删除数据！
void test_vector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.resize(2); }
当然，正如我们 string 章节所说，它的容量并不会因此改变。
这里虽然大小变成 2，数据也只有 [0]1 和 [1]2 了，但是容量仍然为 4。
0x04 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(void) { 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'; } } }
🚩 VS运行结果如下：
making foo grow : capacity changed : 1 capacity changed : 2 capacity changed : 3 capacity changed : 4 capacity changed : 6 capacity changed : 9 capacity changed : 13 capacity changed : 19 capacity changed : 28 capacity changed : 42 capacity changed : 63 capacity changed : 94 capacity changed : 141
🚩 g++ 运行结果如下：
making foo grow : capacity changed : 1 capacity changed : 2 capacity changed : 4 capacity changed : 8 capacity changed : 16 capacity changed : 32 capacity changed : 64 capacity changed : 128
Ⅳ. vector 增删查改
| swap | 交换两个 vector 的数据空间 |
| operator[] （重点） | 像数组一样访问 |
刚才讲 "下标 + 方括号" 的遍历方式的时候已经讲过 push_back 了，
也顺便解释了为什么不提供 push_front 和 pop_front ，所以这里就不多bb了。
0x00 pop_back() 尾删
现在我们把 pop_back 简单介绍一下，pop_back 就是尾删，可用来删除 vector 中的数据。
💬 pop_back：
void test_vector5() { 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(); // 尾删：3 for (auto e : v) cout << e << " "; cout << endl; v.pop_back(); // 尾删：2 for (auto e : v) cout << e << " "; cout << endl; }
🚩 运行结果如下：
0x01 assign() 赋值
assign 可以把 vector 的内容覆盖掉。允许给一段区间覆盖，也可以给 个 value 去覆盖。
💬 用 个 value 覆盖：
void test_vector6() { 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 }
🐞 调试结果如下：
0x02 探讨：为什么 vector 不提供 find 接口
string、map、set 都有 find() 用，凭什么 vector 和 list 没有？
太不公平了吧！歧视这是赤裸裸的容器歧视？？
其实，我们应该考虑的是 —— 为什么 string、map、set 能有 find 操作。
而 vector 之所以不提供 find ，是因为如果去查找元素效率就会是 ……
呵呵，凭什么不让我 vector 用 find() ，我偏要用！
可以的，"algorithm库" 里有通用的 find 操作，我们来一睹其芳容 ——
#include <algorithm>
该 find 内部是从 begin 到 end 进行一次遍历，其复杂度是
值得一提的是，在C++中，凡是使用迭代器区间，都是左闭右开的 ——
（map 和 set 接下来的章节会讲，以下部分可先作了解）
再去思考 map、set 为什么有 find() 通过迭代器从头到尾遍历 map 与 set 时，
得到的结果是按 key 排序的结果，而不是插入时的顺序，所以这两个容器没有 push_back 操作。
其实，插入到 map 与 set 中的元素会被组织到一颗红黑树上，红黑树是一颗平衡二叉树，
平衡二叉树是一颗二叉排序树，对一颗二叉排序树的查找有点像二分查找，复杂度是 ，
由于 map 与 set 的数据结构能有更快的查找方法，所以在容器内提供了 find 方法。
0x03 通用查找 find()
如果非要在 vector 里用 find() ，我们可以用通用 find。
找到了：返回一个迭代器区间那个值的位置；
没找到：返回的是 ，即右边开区间的位置。
💬 使用方法演示：
void test_vector7() { 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; } }
0x04 insert() 插入
比如我们刚才用通用 find 找到了 3 的位置，
我们想在这个位置前面插入一个数据，就可以使用 insert() 插入。
💬 在 3 前面用 insert 插入一个 30：
void test_vector7() { 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); if (ret != v.end()) { cout << "找到了" << endl; v.insert(ret, 30); // 在ret位置前面插入一个30 } for (auto e : v) cout << e << " "; cout << endl; }
🚩 运行结果如下：
我们刚才说过，虽然没有 vector 没有提供 push_front，但是我们也可以用 insert 去头插。
💬 用 insert 去头插：
void test_vector8() { 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); // 在起始位置插入一个-1 for (auto e : v) cout << e << " "; cout << endl; }
🚩 运行结果如下：
0x05 erase() 删除
我们我们想删除数据，我们就可以用 erase 去删除。
💬 使用 erase 的时要判断一下有没有找到要删除的目标：
void test_vector9() { 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(), 5); if (pos != v.end()) { // 判断pos是否存在 v.erase(pos); // 删除pos } for (auto e : v) cout << e << " "; cout << endl; }
🚩 运行结果如下：
❓ 如果没有判断会怎么样？
void test_vector9() { 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); }
0x04 clear() 清空数据
💬 clear：
void test_vector10() { 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; }
🚩 运行结果如下：
