0. 官方文档
1. vector介绍
Vector 简单来说就是顺序表，是一个可以动态增长的数组。
vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。
优点：
支持下标随机访问，间接的就很好的支持了排序、二分查找、堆算法等等
缺点：
头部和中部的插入删除效率低。O(N)，因为需要挪动数据。
插入数据空间不够需要增容，增容需要开新空间，拷贝数据，释放旧空间，会付出很大代价。
2. vector库函数的使用
2.1 vector 的基本构造、拷贝与赋值操作
vector 的默认构造与元素添加
vector<int> v1; // 创建一个空的整型vector
v1.push_back(1); // 在vector末尾添加元素1
v1.push_back(2); // 在vector末尾添加元素2
v1.push_back(3); // 在vector末尾添加元素3
v1.push_back(4); // 在vector末尾添加元素4vector<int> v1使用默认构造函数创建一个空的vector容器push_back()成员函数用于在vector的末尾添加新元素
vector 的拷贝构造
vector<int> v2(v1); // 使用v1作为源创建v2（拷贝构造）拷贝构造函数
vector<int> v2(v1)创建一个新vector，其元素是v1元素的完整拷贝两个vector对象完全独立，修改一个不会影响另一个
vector 的遍历与下标访问
for (size_t i = 0; i < v1.size(); ++i)
{
cout << v1[i] << " "; // 使用下标运算符[]访问元素
}size()成员函数返回vector中元素的数量可以使用下标运算符
[]像数组一样访问vector中的元素
vector 的赋值操作
vector<int> v3;
v3.push_back(60);
v3.push_back(61);
v3.push_back(62);
v3.push_back(63);
v1 = v3; // 将v3的内容赋值给v1赋值操作
v1 = v3会将v3的所有元素复制到v1中赋值后v1的原始内容会被替换，大小会调整为与v3相同
2.2 vector 的遍历与元素修改
使用下标遍历和修改元素
for (size_t i = 0; i < v.size(); ++i)
{
v[i] *= 2; // 修改元素值
cout << v[i] << " "; // 访问元素值
}使用下标遍历是最直观的方式，类似于操作普通数组
可以通过下标直接修改vector中的元素
使用迭代器遍历和修改元素
vector<int>::iterator it = v.begin(); // 获取指向第一个元素的迭代器
while (it != v.end()) // 循环直到迭代器指向末尾
{
*it *= 2; // 解引用迭代器并修改元素值
cout << *it << " "; // 访问元素值
++it; // 移动迭代器到下一个元素
}begin()返回指向第一个元素的迭代器end()返回指向最后一个元素之后位置的迭代器迭代器提供了类似指针的语法来访问和修改元素
使用范围for循环遍历元素
for (auto e : v)
{
cout << e << " "; // 访问每个元素
}范围for循环是C++11引入的语法糖，代码更简洁
编译器会自动将其转换为迭代器操作
注意：这种方式默认是值拷贝，如果需要修改元素，应使用引用
for (auto& e : v)
2.3 vector 的迭代器类型
一般来说分为三大种：正向、反向、const
普通正向迭代器
vector<int>::iterator it = v.begin();
while (it != v.end())
{
*it *= 2; // 可读写操作
cout << *it << " ";
++it;
}普通迭代器允许读取和修改指向的元素
使用
iterator类型定义，适用于需要修改vector内容的场景
const 正向迭代器
vector<int>::const_iterator it = vt.begin();
while (it != vt.end())
{
// *it *= 2; // 错误：不能修改const迭代器指向的值
cout << *it << " "; // 只能读取
++it;
}const迭代器指向的元素不能被修改
使用
const_iterator类型定义，适用于只读访问场景
反向迭代器
vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v.rend())
{
cout << *rit << " "; // 从后向前遍历
++rit; // 注意：++操作是向前移动
}反向迭代器从容器的末尾向开头遍历
rbegin()返回指向最后一个元素的迭代器rend()返回指向第一个元素之前位置的迭代器++操作使迭代器向前移动（向容器开头方向）
const 反向迭代器
vector<int>::const_reverse_iterator crit = v.rbegin();结合了反向迭代和const特性的迭代器
可以反向遍历容器，但不能修改元素值
函数参数中的const引用
void print_vector(const vector<int>& vt)
{
vector<int>::const_iterator it = vt.begin();
while (it != vt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}使用const引用传参
const vector<int>& vt避免不必要的拷贝函数内部使用const迭代器确保不会意外修改原始数据
这是C++中常见的编程实践，既能提高效率又能保证数据安全
const对象与const迭代器
const对象只能使用const迭代器进行遍历
在实际工程中，const对象常用于函数参数，防止函数内部修改调用者的数据
使用const是正确的编程习惯，可以提高代码的可读性和安全性
2.4 容量相关
下面是一段扩容测试代码，插入1000个数据，观测容量空间变化：
void test_vector4()
{
vector<int> v;
cout << "making v grow:\n";
size_t sz = v.size();
for (int i = 0; i < 1000; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}同样的代码，如下图，左边是linux环境下编译运行出的结果，右边是window的vs编译的结果：
增容次数越少，效率越高，但可能导致的空间浪费越多。
增容次数越多，效率越低，但可能导致的空间浪费越少。
v.reserve(1000); // 扩容
v.resize(1000); // 扩大size，额外扩出来的部分会自动补'\0'或自定义字符reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size。
2.5 修改与查找
尾部插入元素
vector<int> v;
// 尾插 - 使用 push_back() 在容器末尾添加元素
v.push_back(5);
v.push_back(4);
v.push_back(3);
v.push_back(2);
v.push_back(1);push_back()是 vector 最常用的添加元素方法每次调用会在 vector 的末尾添加一个新元素
如果当前容量不足，vector 会自动重新分配更大的内存空间
指定位置插入元素
// 头插 - 使用 insert() 在指定位置插入元素
v.insert(v.begin(), 0); // 在开头插入元素0
v.insert(v.end(), -1); // 在结尾插入元素-1insert()方法可以在任意位置插入元素第一个参数是迭代器，指定插入位置
第二个参数是要插入的值
在开头插入元素会导致后续所有元素向后移动，效率较低
删除指定位置元素
// 头删 - 使用 erase() 删除指定位置的元素
v.erase(v.begin()); // 删除第一个元素erase()方法删除指定位置的元素参数是一个迭代器，指向要删除的元素
删除元素后，后面的所有元素会向前移动
删除开头元素效率较低，因为需要移动所有后续元素
查找操作：使用标准库的 find 算法
// vector 没有提供内置的查找方法// 使用标准库中的 find 算法
vector<int>::iterator pos = find(v.begin(), v.end(), 5);vector 本身不提供查找方法，需要使用标准库的
find算法find需要包含<algorithm>头文件find接受三个参数：起始迭代器、结束迭代器和要查找的值查找范围是左闭右开区间
[first, last)，即包含 first 但不包含 last
处理查找结果
if (pos != v.end()) // 检查是否找到元素
{
v.erase(pos); // 如果找到，删除该元素
}find返回一个迭代器，指向找到的元素如果没找到，返回结束迭代器
v.end()在删除前必须检查是否找到元素，否则可能引发未定义行为
vector 的排序操作：使用标准库的 sort 算法
// 使用标准库的 sort 算法对 vector 排序
sort(v.begin(), v.end()); // 默认升序排序sort需要包含<algorithm>头文件默认情况下，
sort按升序排列元素sort使用快速排序算法实现，平均时间复杂度为 O(N log N)排序范围也是左闭右开区间
[first, last)
2.6 标准库算法的说明
find 算法
// std::find 函数模板声明（简化）
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);find是一个函数模板，可用于任何支持迭代器的容器它在
[first, last)范围内查找第一个等于value的元素如果找到，返回指向该元素的迭代器；否则返回
last使用
==运算符进行比较，因此元素类型必须支持此操作
sort 算法
// std::sort 函数模板声明（简化）
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);sort要求迭代器是随机访问迭代器，vector 的迭代器满足此要求默认使用
<运算符进行比较，因此元素类型必须支持此操作可以自定义比较函数来实现不同的排序规则
2.7 迭代器失效问题
1.增容导致的迭代器失效
看下面这段代码：
void test_vector8()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
v.push_back(6);
v.push_back(7);
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
如果我们把上面的代码修改一下，把push_back(7)注释掉，就可以运行：
这是为什么呢？这个问题和动态增容有关。
假设我们插入 7 之前的 v 有6个空间，即 v.capacity() 为6，当我们插入 7 后发生了增容，开辟了一块新的空间，v 的内容全都被拷贝去了新的空间，然而此时 it 迭代器还指向旧空间的 v.begin() ，it 迭代器就失效了。
因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
所以 push_back 、insert 、resize 、reserve 等可能扩容的接口都会导致迭代器失效。
解决办法（正确写法）：
很简单，不要在初始化迭代器后在调用可能导致扩容的接口就行了。
2.删除导致的迭代器失效
void test_vector9()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
// 要求删除容器中的所有偶数
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}程序又崩溃了：
当 it 到 2 的位置时，会删掉 2 ，然后后面的数据会往前挪，it++，此时 it 会直接略过 3 ，到 4 的位置。
也就是说，删除 it 位置的元素后，it 就失效了，这里的失效是 it 迭代器已经失效了，再 ++it 就不行。这个问题在 vs 下会报错，是编译器强制检查的，但是在 gcc 下就不报错，但是结果不对，无法删除掉连续的偶数（比如把3改成30就无法删除30）。
编译器检查迭代器失效原因：erase删除 it 位置元素后，it 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 it 刚好是最后一个元素，删完之后 it 刚好是end的位置，而end位置是没有元素的，那么 it 就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。
总结：不管哪个平台下，erase(it) 后，it 就失效了，只是导致的结果不一样，总之都有各种各样的问题。
作为编译器检查迭代器失效的印证，哪怕把代码改成下面这样也会报错（vs 会报错，linux 下正常运行）
解决办法（正确写法）：
通过官网对 erase 的返回值的介绍，我们可以知道，erase 的返回值是被删除元素的下一个元素的位置。我们只需要改一下代码就可以正常运行了：
void test_vector9()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
// 要求删除容器中的所有偶数
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it); // 修改
}
else
{
++it;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}