vector
vector 是一个可变长的动态数组，支持动态的添加元素，支持随机访问。重分配通常是性能上有开销的操作。如果元素数量已知，那么 reserve() 函数可用于消除重分配。
vector 上的常见操作复杂度（效率）如下：
- 随机访问——常数 𝓞(1)。
- 在末尾插入或移除元素——均摊常数 𝓞(1)。
- 插入或移除元素——与到 vector 结尾的距离成线性 𝓞(n)。
常用方法
构造
1
2
3
| vector<int> a;
vector<int> a = {1,2,3}
|
正向遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
for (int i = 0; i < a.size(); ++i){
cout << a[i] <<' ';
}
for (auto x : a){
cout << x << ' ';
}
for (auto it = v.begin(); it != v.end(); it++){
cout << *it << ' ';
}
|
反向遍历
1
2
3
4
5
6
7
8
9
10
|
if (a.empty()){
for (int i = a.size()-1; i > 0; i--){
cout << a[i] << ' ';
}
}
for (auto it = a.rbegin(); it != a.rend(); it++){
cout << *it << ' ';
}
|
添加、删除
