vector

sLMxf · 2023-08-10 15:57:20 · 个人记录

Vector

什么是 vector
Vector 是一种可以存储任意类型的动态数组，属于序列式容器，可以用 sort 对其进行排序，底层数据结构是数组，可以随机访问元素。Vector 包含着一系列连续存储的元素，其行为和数组类似。访问 Vector 中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在 Vector 中插入元素则是线性时间复杂度。
vector 基本用法
- 建立
  代码：
```
vector<类型> a;
```
  表示建立了一个类型类型的vector a。
- 调用
  和数组一样，就是a[i]。
- 插入·push_back
```
a.push_back(x);
```
  上面的代码就是说在vector a的最后面插入了 x。时间复杂度 O(1)。
- 插入·insert
```
a.insert(w,x);
```
  向 w 的位置插入了 x。时间复杂度 O(n)。
- 排序
  排序代码很简单：
```
sort(a.begin(),a.end(),cmp);
```
  其中cmp可填可不填。这段代码表示将 a 里的所有数字排序。时间复杂度 O(n \log n)
- 删除·pop_back
```
a.pop_back();
```
  上面代码就是将 a 的最后一个数据删除。时间复杂度 O(1)。
- 删除·erase
  - 删除单个元素，erase(it)即删除it处的元素；
  - 删除一个区间内的所有元素，erase(first,last)即删除[first,last)内的所有元素；
  - 清空vector可以使用v.erase(v.begin(),v.end());。
  时间复杂度 O(n)。
- 清空
```
a.clear();
```
  将 a 中所有数据删除。时间复杂度 O(n)。
- 长度
  用 a.size() 可以求出 a 的长度。时间复杂度 O(1)。
- 二维 vector 两种方法：
  1. vector<vector<类型> >a;
    这样就是两维都是不定长度的。可自己思考如何插入
  2. vector<类型> a[第一维长度];
    第一维的长度就被固定了。
vector 练习
- 寄包柜