数据结构vector

### 关于数据结构 `vector` 的介绍

`vector` 是一种动态数组的数据结构，它能够自动调整大小来容纳新加入的元素。与静态数组不同的是，`vector` 不需要预先指定长度，在运行过程中可以根据需求增加或减少容量[^1]。

#### 基本特性
- **随机访问**：支持通过索引快速定位任意位置上的元素。
- **高效增删**：在向量末端添加或移除元素效率较高；但在中间部分执行这些操作则可能导致大量移动其他元素而降低性能。
- **连续存储空间**：内部采用一块连续内存区域保存所有成员变量，这使得遍历速度较快但也意味着当达到当前分配的最大尺寸时需重新申请更大块的空间并复制已有内容过去。

### C++ 中 `vector` 的基本用法

为了声明一个整型向量对象可以这样写：

#include <vector>
using namespace std;

// 创建一个空的整数类型的 vector 对象 v
vector<int> v;

初始化带有初始值列表的方式如下所示：

// 使用大括号 {} 初始化含有三个元素 (1, 2, 3) 的 vector w
vector<int> w{1, 2, 3};

对于已经存在的容器进行拷贝也可以很方便地完成：

// 定义另一个名为 u 的 vector 并将其设置为等于之前创建好的 w
vector<int> u(w);

#### 添加和删除元素

可以通过调用特定的方法来进行插入和弹出动作：

v.push_back(7);    // 向 v 尾部追加数值 7
w.pop_back();      // 移除 w 最后一项
u.insert(u.begin(), 8); // 在 u 开头处插入数字 8
u.erase(u.begin());     // 删除 u 首个元素

#### 访问元素

获取单个元素通常有两种方式——下标运算符[] 和 at 函数：

cout << "The first element is " << v[0];        // 输出第一个元素
try {
    cout << "\nThe second element is " << u.at(1); // 更安全地读取第二个元素
} catch(const out_of_range& e){
    cerr << "Error: Index Out Of Range";
}

迭代整个序列也很简单：

for(auto it = v.begin(); it != v.end(); ++it){  
    cout << *it << ' ';
}

// 或者更简洁的形式
for(auto elem : v){
    cout << elem << ' ';
}