vector 基本使用 vector 是 C++ STL 中最常用的容器, 也是面试中的常见考点. 以下内容向大家介绍 vector 的最常见用法. 1. 头文件 vector 是标准库中的组件. 使用时需要包含相关头文件. #includ
vector 基本使用
vector 是 C++ STL 中最常用的容器, 也是面试中的常见考点. 以下内容向大家介绍 vector 的最常见用法.
1. 头文件
vector 是标准库中的组件. 使用时需要包含相关头文件.
#include <vector>2. 实例化
vector 是一个类模板, 在实例化的时候需要指定模板参数.
// 包含头文件#include <vector>
#include <string>
int main() {
// 实例化时需要指定模板参数.
// C++ 98/03 要求模板参数必须是具备拷贝构造函数的.
// C++ 11 要求模板参数具有转移构造函数也可以.
std::vector<int> ivec;
std::vector<std::string> svec;
return 0;
}
注意: 啥样类型的元素可以放到 vector 中呢?
3. 新增元素
3.1 尾插
#include <vector>#include <iostream>
int main() {
std::vector<int> ivec;
// 使用 push_back 尾插元素.
// 未触发扩容时时间复杂度 O(1).
// 触发扩容时时间复杂度为 O(N).
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3);
ivec.push_back(4);
for (int x : ivec) {
std::cout << x << std::endl;
}
return 0;
}
// 输出结果
1
2
3
4
vector 的尾插操作比较高效, 不扩容的情况下时间复杂度为 O(1).
一旦触发扩容(size达到capacity时), 涉及到元素搬运, 时间复杂度为 O(N)
3.2 中间插入
使用 insert 函数进行插入. 需要配合迭代器指定插入的位置.
#include <vector>#include <iostream>
int main() {
std::vector<int> ivec;
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3);
ivec.push_back(4);
// 使用 insert 在中间位置插入元素
auto it = ivec.begin() + 2;
ivec.insert(it, 100);
for (int x : ivec) {
std::cout << x << std::endl;
}
return 0;
}
// 输出结果
1
2
100
3
4
中间插入元素需要进行搬运, 相对比较低效, 时间复杂度 O(N)
4. 查看/修改元素
4.1 通过 [ ] 按下标访问
#include <vector>#include <iostream>
int main() {
std::vector<int> ivec;
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3);
ivec.push_back(4);
// 通过 [ ] 来访问元素
std::cout << ivec[0] << std::endl;
std::cout << ivec[1] << std::endl;
ivec[0] = 100;
std::cout << ivec[0] << std::endl;
std::cout << "循环访问元素: ";
for (size_t i = 0; i < ivec.size(); ++i) {
std::cout << ivec[i] << " ";
}
std::cout << std::endl;
return 0;
}
// 执行结果
1
2
100
循环访问元素: 100 2 3 4
- 下标从 0 开始
- 如果下标越界, 会引起未定义行为.
4.2 通过 at 方法按下标访问
#include <vector>#include <iostream>
int main() {
std::vector<int> ivec;
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3);
ivec.push_back(4);
// 通过 at 来访问元素
std::cout << ivec.at(0) << std::endl;
std::cout << ivec.at(1) << std::endl;
return 0;
}
// 执行结果
1
2
如果下标越界, 会抛出异常.
4.3 通过迭代器访问
#include <vector>#include <iostream>
int main() {
std::vector<int> ivec;
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3);
ivec.push_back(4);
// 通过 迭代器 来访问元素
std::vector<int>::iterator it = ivec.begin();
std::cout << *it << std::endl;
std::cout << "遍历元素: " << std::endl;
for (auto it = ivec.begin(); it != ivec.end(); ++it) {
std::cout << *it << std::endl;
}
return 0;
}
// 执行结果
1
遍历元素:
1
2
3
4
vector 的迭代器属于随机访问迭代器, 允许进行 + - 整数操作.
5. 查找元素
使用 std::find 进行查找
#include <vector>#include <iostream>
#include <algorithm>
int main() {
std::vector<int> ivec;
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3);
ivec.push_back(4);
// 通过 find 查找元素
auto pos = std::find(ivec.begin(), ivec.end(), 3);
if (pos != ivec.end()) {
std::cout << "找到了: " << *pos << std::endl;
} else {
std::cout << "没有找到!" << std::endl;
}
return 0;
}
// 执行结果
找到了: 3
6. 删除元素
使用 erase 方法删除元素 (需要通过迭代器指定删除位置)
#include <vector>#include <iostream>
#include <algorithm>
int main() {
std::vector<int> ivec;
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3);
ivec.push_back(4);
// 通过 erase 删除元素. 需要指定位置
auto pos = ivec.begin() + 2; // pos 指向元素 3
ivec.erase(pos);
for (int x : ivec) {
std::cout << x << std::endl;
}
return 0;
}
// 执行结果
1
2
4
7. 排序
使用 std::sort 对 vector 进行排序 (要求 vector 中的元素支持 operator< 或者可以通过 sort 的参数指定一个 std::function 对象来约定比较规则)
#include <vector>#include <iostream>
#include <algorithm>
int main() {
std::vector<int> ivec;
ivec.push_back(9);
ivec.push_back(5);
ivec.push_back(2);
ivec.push_back(7);
// 使用 sort 排序. 默认为升序排序
std::cout << "升序排序: " << std::endl;
std::sort(ivec.begin(), ivec.end());
for (int x : ivec) {
std::cout << x << std::endl;
}
// 使用 std::greater 可以修改为降序排序
std::cout << "降序排序: " << std::endl;
std::sort(ivec.begin(), ivec.end(), std::greater<int>());
for (int x : ivec) {
std::cout << x << std::endl;
}
return 0;
}
// 执行结果
升序排序:
2
5
7
9
降序排序:
9
7
5
2
小结
以上介绍了 vector 中最基础的操作. 其他更多操作, 可以参考 vector 的官方文档.
围绕 vector 的一些面试题通常从 vector 的内存管理策略切入, 咱们后面再详细介绍.