C++ STL vector 学习笔记

1. vector 基本概念

vector 是 C++ STL 中最常用的容器之一，它是一个动态数组，能够在运行时自动调整大小。

1.1 特点

  • 连续内存存储
  • 支持随机访问
  • 动态扩容
  • 在尾部插入/删除效率高
  • 在中间或头部插入/删除效率低

2. 基本操作

2.1.1 声明和初始化

1
2
3
4
5
6
7
cpp
// 常见的初始化方式
vector<int> vec; // 空vector
vector<int> vec(5); // 包含5个元素，初始值为0
vector<int> vec(5, 1); // 包含5个元素，初始值都为1
vector<int> vec2(vec); // 复制构造
vector<int> vec = {1, 2, 3, 4, 5}; // 列表初始化

2.1.2 输入元素

1
2
3
4
5
6
7
8
9
vector<int> vec;
int size;
cin>>size;
vec.resize(size);// 预分配内存
for(int i=0;i<size;i++){
    int temp;
    cin>>temp;
    vec.push_back(temp);
}

2.1.3 输出元素

1
2
3
4
vector<int> vec;
for(int i=0;i<vec.size();i++){
    cout<<vec[i]<<" ";
}

2.2 常用成员函数

  • push_back(): 在尾部添加元素
  • pop_back(): 删除尾部元素
  • size(): 返回元素个数
  • capacity(): 返回当前分配的存储空间
  • empty(): 判断是否为空
  • clear(): 清空所有元素
  • reserve(): 预分配存储空间
  • resize(): 改变vector大小

3. 迭代器操作

3.1 基本迭代器

3.1.1 正向迭代器

1
2
3
4
5
//vector<int>::iterator it; // 正向迭代器
for (vector<int>::iterator it = vtr.begin(); it != vtr.end(); ++it)
	{
		cout << *it << " ";
	}

3.1.2 反向迭代器

1
2
3
4
5
//vector<int>::reverse_iterator rit; // 反向迭代器
for (vector<int>::reverse_iterator rit = vtr.rbegin(); it != vtr.rend(); ++rit)
	{
		cout << *rit << " ";
	}

3.2 常用迭代器函数

  • begin(): 返回首元素迭代器
  • end(): 返回尾后迭代器
  • rbegin(): 返回反向首元素迭代器
  • rend(): 返回反向尾后迭代器

4. 内存管理

4.1 扩容机制

  • vector在需要更多空间时会自动扩容
  • 一般情况下扩容为原来的1.5或2倍
  • 扩容会导致迭代器失效

4.2 内存优化

1
2
3
vector <int> vec; // 初始分配空间
vec.reserve(1000); // 预分配空间，避免频繁扩容
vec.shrink_to_fit(); // 释放多余空间

5. 常见操作示例

5.1 插入和删除

1
2
3
4
vector <int> vec(1000); // 初始分配空间
vec.insert(vec.begin() + 2, 5); // 在指定位置插入元素
vec.erase(vec.begin() + 2); // 删除指定位置元素
vec.erase(vec.begin(), vec.begin() + 3); // 删除一个范围的元素

5.2 访问元素

1
2
3
4
5
vector <int> vec(1000); // 初始分配空间
vec[0]; // 通过下标访问（不进行边界检查）
vec.at(0); // 通过at访问（会进行边界检查）
vec.front(); // 访问第一个元素
vec.back(); // 访问最后一个元素

6. 注意事项

  1. 避免频繁在中间插入删除元素
  2. 注意迭代器失效的情况
  3. 合理使用reserve()预分配空间
  4. 注意越界访问

7. 性能分析

  • 随机访问: O(1)
  • 尾部插入/删除: 均摊 O(1)
  • 中间插入/删除: O(n)
  • 查找: O(n)

评论区仅供交流，有问题请 联系我 反馈。