C++语法-vector

这篇文章来讲下我在 OI 中遇到的 vector 的用法，本文基于 C++14 。

---

一、vector 底层相关

vector 是封装动态数组的顺序容器，并且是连续存储的，因此除了迭代器，还可以通过指针访问。

vector 的存储是自动管理的，按需扩张收缩，因此内存占用会较多于静态数组。

vector 所用的方式不是在每次插入元素时，而只在额外内存耗尽时重分配，也就是装不下的时候再扩充一定量。

我们可以用 capacity() 函数查询分配的内存总量，还可以用 shrink_to_fit() 返回多出的内存给系统。

vector<int> a(15); // 初始化为15个元素
vector<int> b; // 初始为空

// capacity（意思是“容量”） 查询占用内存，返回的是元素个数
// 值得注意的是，占用内存分配方式取决于标准库的实现方式，不过一定有 占用内存 ≥ 使用内存
cout << (int)a.capacity() << ' ' << (int)b.capacity() << '\n'; // 输出 15 0

int n; cin >> n; // 输入 n = 5
for(int i = 0; i < n; i++) b.push_back(i);
cout << (int)a.capacity() << ' ' << (int)b.capacity() << '\n'; // 输出 15 8

b.shrink_to_fit(); // 缩到合适大小（居然直译）
cout << (int)a.capacity() << ' ' << (int)b.capacity() << '\n'; // 输出 15 5

假设此时有一个 size 初始为 \(0\) 的 vector（我就是不初始化个大的咋滴）

如果我已经知道要插入比如 \(10^6\) 个数，那我岂不是白白重分配了好几次吗？

解决方法有两种，各有优劣：

1. 使用函数 reserve() 更改 vector 的 cap 值为 \(10^6\) 。

   reserve() 函数可用于更改容器的 cap 值，也就是实际容量大小。这不会修改原 vector 的 size。

   主要传参方式 reserve(new_cap) ，new_cap 为一个 int。

   若 new_cap 大于当前 cap 值，则重新分配新的存储（因此所有迭代器都会失效，这个我们后面讲）

   否则若小于当前的 cap 值，什么都不会做（此时只有 shrink_to_fit() 可用，原理类似）

   注意，由于每次有效调用都会重新分配新的存储，因此滥用这两个函数不会有更好的性能

   reserve() 函数的时间复杂度：至多与容器的 size 成线性。

   vector<int> c;  // 此时容量为 0
   c.reserve(15);  // 此时容量为 15
   cout << (int)c.capacity() << '\n'; // 15

2. 使用函数 resize() 更改 vector 的 size 为 \(10^6\) 。

   resize() 函数可用于重设重设容器大小以容纳 count 个元素

   传参方式 resize(count, value) ，count 为一个 int

   value 的类型取决于 vector（ value 可不传，此时为默认值，一般为 \(0\) ，取决于构造函数）。

   • 若当前 size 大于 count ，则减小容器到它开头的 count 个元素
   • 若当前 size 小于 count ，则后附额外的「默认插入的元素」或「value 的副本」

   resize() 函数的时间复杂度：

   与当前大小和 count 间的差成线性，在容量小于 count 时会有（一次）重分配的额外复杂度。

   b.resize(10,666); // 从 5 改到 10，增加的部分全都是666
   
   // 输出 0 1 2 3 4 666 666 666 666 666，如果没有指定value，输出就是玄学了
   for(int i = 0; i < 10; i++) cout << b[i] << " \n"[i == 9];

---

二、vector 常见操作及初始化

vector 常见操作有：

1. 随机访问：\(\mathcal{O}(1)\) 。如 vec[123] 。
2. 在末尾插入或移除元素，即 push_pack() 或 pop_back() ：均摊 \(\mathcal{O}(1)\) 。
3. 插入或移除元素，即 insert() 或 erase() ：与到 vector结尾的距离成线性 \(\mathcal{O}(n)\) 。

第三点尤其需要注意，虽然看上去跑得快，其实是标准库底层优化的好+数据水，实际上复杂度是不对的。

vector在初始化上也有很多方法

vector<int> v1; // empty
vector<int> v2(v1); // v2 = v1;
vector<int> v3 = {1,2,3.0,4,5,6,7}; // 3.0 会自动转为 int 型
vector<int> v4(5); // size = 5
vector<int> v5(7,5); // {5,5,5,5,5,5,5}

顺便讲一下二维 vector 的以及初始化方法

vector<int> vec0[105]; // 一维静态一维动态的 vector
vector< vector<int> > vec1; // 动态二维 vector
vector< vector<int> > vec2(vec1); // vec2 = vec1
vector< vector<int> > vec3(5, vector<int>(3)); // 5*4的矩阵，默认为0
// vector<int>(3) 通过调用 vector 模板的构造函数创建了一个包含 3 个整数元素的向量（默认全为0）
vector< vector<int> > vec4(5, vector<int>(3,5)); // 5*4的矩阵，全是5
vector< vector<int> > vec5(5, vector<int>(vec4[0].begin(), vec4[0].end())); // 显然

有关动态的二维 vector 我用的不多，主要是矩阵快速幂板子会用，可以去康康

---

三、迭代器失效

---

四、常用成员类型&函数

成员类型一般只会用到 iterator ，即迭代器，类似于指针。

常用成员函数如下：

常见的非成员函数主要就是 operator== 系列的了，这些均为按字典序比较。

接下来我们来讲几个比较重要的函数

1. insert() ，主要有3种用法

   1. insert(pos, val) 传一个迭代器和一个 int ，在 pos 前插入 val 。返回值为插入 val 的迭代器。

   2. insert(pos, count, val) 多传一个 int ，表示在 pos 前插入 val 的 count 个副本。

      返回值为首个被插入元素的迭代器，或在 count == 0 时返回 pos 。

   3. insert(pos, fir, las) 插入来自范围 \(\mathtt{[fir, las)}\) 的元素。

      返回值为首个被插入元素的迭代器，或在 fir == las 时返回 pos 。

   注意：如果新 size 插入后超过了旧 cap ，则会导致重分配，所有迭代器和引用会失效

   第三种用法需要讲一下，我们一般传两个迭代器，并且不是指向 *this 中的迭代器，否则行为未定义。

   这个的一个常见应用就是合并两个 vector。我们前面提到过， vector 会动态控制内存占用

   所以如果你把 B 里的一个一个 push_back 到 A 里，复杂度就会变高，有题目卡这个的（被卡过）

   时间复杂度：显然线性，分析略。

2. erase()，两种用法：删 pos 或删 \(\mathtt{[fir, las)}\) 的元素

   形式和 insert() 类似，但在参数上有了一定限制：迭代器 pos 必须合法且可解引用，且均指向 *this。

   （话说要是传一个不指向 *this 的，好像也不会报错，但是会段错误）

   函数的返回值通常为移除元素之后的迭代器（位于擦除点或之后的迭代器已经失效）

   如果 pos 指代末元素，则返回新 end() 迭代器；如果移除前 las == end() 则返回新的 end()

   时间复杂度为线性：调用 T 析构函数的次数与被擦除的元素数相同，

   调用 T 赋值运算符的次数与 vector 中被擦除元素后的元素数相等

3. clear() 清空，需要提的有两点：

   1. 该函数的时间复杂度为线性，显然但是需要注意。
   2. 清空后所有迭代器等均失效，但是 cap 值不变。（卡常小技巧）

最后我们来讲讲 emplace_back() 和 push_back() 的区别

push_back() 向容器尾部添加元素时，首先会创建这个元素，

然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）

而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

在语法上也略有不同，如下：

vector< pair<int,int> > d;
d.push_back({1,2}); d.emplace_back(2,1);
cout << d[0].first << ' ' << d[1].second << '\n'; // 输出 1 1

（cxy：那我还用什么 push_back() 啊？）

事实上 emplace_back() 可读性较差，举一个非常简单的例子

struct node { int val; }
// ....
vec.emplace_back(1919);

当代码量达到一定程度时， emplace_back() 的可读性差就会体现出来

你看这个 1919 ，它到底是塞了一个 int 呢，还是塞了一个 node 呢？然后你就得往上翻或者直接误解。

总结一下就是 emplace_back() 效率更高，可读性差，所以我基本不用。

---

参考文献：

[1] https://zh.cppreference.com/w/cpp/container/vector

[2] ChatGPT. (2023, February 16)