vector是动态数组，支持随机访问，使用前需要包含头文件<vector>。

定义与初始化

#include<vector>
using namespace std;
void test()
{
  vector<int> v1;//空vector
  vector<int> v2(5,10);//初始化n个值为val的元素
  vector<int> v3(v2.begin(),v2.end());//用迭代器范围初始化
  vector<int> v4{1,2,3,4};//列表初始化
  vector<int> v5(v4);//拷贝构造,拷贝v4的所有元素
}

vector的定义

无参构造函数

构造一个空的 vector，里面没有任何元素

#include<iostream>
#include<vector>
using namespace std;
int main()
{
  vector<int> v1;
  cout<<"v1的大小是"<<v1.size()<<endl;
  return 0;
}

vector<size_type n,const value_type& val=val_type()>

构造一个 vector，其中包含 n 个值为 val 的元素。如果没有指定 val，则使用元素类型的默认构造值

vector<int> v2(5,10);
for(int i:v2)
{
  cout<<i<<" ";
}
cout<<endl;

vector (const vector& x)
功能：拷贝构造函数，用一个已有的 vector 对象 x 来构造新的 vector 对象，新对象和 x 的内容完全相同。

vector<int> v2(v3);

vector (InputIterator first, InputIterator last)
功能：使用迭代器范围 [first, last) 来初始化构造 vector，将迭代器范围内的元素依次添加到新构造的 vector 中。

int arr[]={1,2,3,4};
vector<int> v1(arr,arr+5);

vector iterator的使用

begin+end

vector<int> v={1,2,3};
for(vector<int>::iterator it=v.begin();it!=v.end();it++)
{
   *it*=2;
}

rbegin+rend

rbegin:获取最后一个元素位置的反向迭代器，rend获取第一个元素前一个位置的反向迭代器。

vector<int> v1={1,2,3};
for(vector<int>::reverse_iterator rit=v.rbegin();rit!=rend();++rit)
{
   cout<<*rit<<endl;
}

vector空间增长问题

size

获取有效的数据个数

vector<int> v={1,2,3};
cout<<v.size()<<endl;

capacity

获取 vector 当前的容量大小，也就是 vector 目前能容纳的最大元素个数

vector<int> v;
for(int i=0;i<10;i++）
{
  v.push_back(i);
  cout<<"size:"<<v.size()<<"capacity:"<<v.capacity()<<endl;
}

运行结果（g++ 环境下，容量按 2 倍增长):

size: 1, capacity: 1
size: 2, capacity: 2
size: 3, capacity: 4
size: 4, capacity: 4
size: 5, capacity: 8
size: 6, capacity: 8
size: 7, capacity: 8
size: 8, capacity: 8
size: 9, capacity: 16
size: 10, capacity: 16

empty

判断vector是否为空

resize

能改变vector的size，如果新的size比原来的大，则多的元素用val填充，如果比原来的小，则截断。

v.resize(5,8);// 改变 size 为 5，多出的用 8 填充

resverse

能改变vector的capacity，提前为vector预留足够的空间，避免后续添加元素的时候频繁扩容，提高效率。如果参数小于vector的容量，则reserve不会改变容量大小。

v.reserve(100);

vector增删查改

push_back

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

cout<<"v的元素："<<endl;
for(int i:v)
{
  cout<<i<<endl;
}
//输出结果：
v 的元素: 1 2 3 

pop_back

删除vector的尾部元素

vector<int> v={1,2,3};
v.pop_back;
for(int i:v)
{
  cout<<i<<" ";
}//删除后的v：1,2

find

在指定的范围内查找元素，返回指向该元素的迭代器；如果找不到，返回范围末尾的迭代器。需要包含头文件 <algorithm>

vector<int> v={1,2,3,4};
auto it=find(v.begin(),v.end(),3);
if(it!=v.end())
{
  cout<<(it-v.begin())<<endl;
}
else
{
  cout<<"未找到元素3"<<endl;
}

insert

在指定的位置之前插入元素val

vector<int> v = {1, 2, 4, 5};
    cout << "插入前 v 的元素: ";
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;

    // 在第二个元素（下标为 1）的位置前插入元素 3
    v.insert(v.begin() + 2, 3);
    cout << "插入后 v 的元素: ";
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
/*运行结果
插入前 v 的元素: 1 2 4 5 
插入后 v 的元素: 1 2 3 4 5 */

erase

删除指定位置的元素

v.erase(v.begin()+3);

swap

交换两个vector的数据空间

 vector<int> v1 = {1, 2, 3};
 vector<int> v2 = {4, 5, 6, 7};
 v1.swap(v2);

operate[]

像访问数组通过下标访问vector当中的元素

vector<int> v = {1, 2, 3, 4, 5};
    // 访问元素
cout << "v[2]: " << v[2] << endl;

通过 reserve 提前为 vector 预留足够的空间，避免在插入元素时频繁扩容，从而提高效率

#include<iostream>
#include<vector>
using namespace std;
void test()
{
  vector<int> v;
  size_t sz=v.capacity();
  reverse(100);//可以把空间提前设为100
  for(int i=0;i<100;i++)
  {
     v.push_back(i);
  }
  if(sz!=v.capacity())
  {
    sz=v.capacity();
  }
}
  
  

由于提前用 reserve(100) 为 vector 预留了 100 个元素的空间，所以在后续插入 100 个元素的过程中，vector 不需要再进行扩容操作，避免了扩容带来的时间开销，提高了效率

vector迭代器失效问题

vector的本质是指向底层连续内存的指针。当迭代器指向的内存空间被释放或者元素位置改变的时候，迭代器就会失效。

引起迭代器失效的操作以及成因

这类操作会导致vector重新分配内存（旧空间被释放，新空间被分配），原迭代器指向的旧空间无效，从而失效。

具体操作包括：

resize(n,val)若n超过当前容量，会扩容（释放旧空间）

reserve(n)若n超过当前容量，会扩容（释放旧空间）

insert(pos,val)插入元素可能会导致扩容（释放新空间）

push_back(val)尾插可能会导致扩容（释放新空间）

assign(n,val)重新赋值可能会导致扩容（释放新空间）

vector<int> v={1,2,3};
auto it=v.begin();
v.resize(100,9);
while(it!=v.end())//it指向已经释放的旧空间，解引用或移动会崩溃
{
  cout<<*it<<" ";
  ++it;
}

失败原因：

erase删除元素之后，it指向的元素已经被后续元素覆盖，且vector会标记it为失败（避免误用）。继续使用it可能会导致访问错误元素或者越界。

迭代器失效的解决办法：

1 对于可能导致空间改变的操作（如 resize、insert、push_back 等），操作完成后需重新通过 begin()、end() 等接口获取迭代器

vector<int> v1={1,2,3};
auto it=v.begin();
v.push_back(4);
it=v.begin();

2利用erase的返回值更新迭代器

erase会返回删除位置的下一个有效迭代器，可用于更新迭代器，避免失效

auto it=v.begin();
while(*it!=v.end())
{
  if(*it%2==0)
  {
    it=v.erase(it);
  }
  else
     ++it;
}

代码错误分析

1

#include <iostream>
using namespace std;
#include <vector>
int main()
{
 int a[] = { 1, 2, 3, 4 };
 vector<int> v(a, a + sizeof(a) / sizeof(int));
 // 使用find查找3所在位置的iterator
 vector<int>::iterator pos = find(v.begin(), v.end(), 3);
 // 删除pos位置的数据，导致pos迭代器失效。
 v.erase(pos);
 cout << *pos << endl; // 此处会导致非法访问
 return 0;
}

错误原因：

1 执行v.erase(pos)之后，pos位置的迭代器已经失效

2后续执行cout<<*pos<<endl;解引用一个失效的迭代器，这是未定义行为

2

#include <iostream>
using namespace std;
#include <vector>
int main()
{
 vector<int> v{ 1, 2, 3, 4 };
 auto it = v.begin();
 while (it != v.end())
 {
 if (*it % 2 == 0)
 v.erase(it);
 ++it;
 }
 return 0;
}

执行v.erase(it)这个时候迭代器会失效。然后执行++it，对一个失效的迭代器进行加加操作，这是未定义行为，会导致程序崩溃。

3（正确）

#include <iostream>
using namespace std;
#include <vector>
int main()
{
 vector<int> v{ 1, 2, 3, 4 };
 auto it = v.begin();
 while (it != v.end())
 {
 if (*it % 2 == 0)
 it = v.erase(it); // 关键：用erase的返回值更新迭代器
 else
 ++it;
 }
 return 0;
}

vector的erase成员会返回被删除元素的下一个元素的有效迭代器

执行it=v.erase(it);此时的it会更新为下一个有效的迭代器，避免使用了失效的迭代器

VS 编译器：对迭代器失效的检测非常严格，只要迭代器可能失效（即使是理论上未改变空间的情况），就会标记为失效，强制开发者处理。

不同编译器的差异

g++ 编译器（Linux 下）：对迭代器失效的检测相对宽松。例如，在第二个错误示例中，g++ 可能不会立即崩溃，但代码仍属于未定义行为，在某些场景下（如复杂数据或大规模操作）仍会出错。

因此，即使在 g++ 下，也应按照 用 erase 返回值更新迭代器 的方式编写代码，保证跨编译器的正确性。

例一 扩容后迭代器失效

int main() {
    vector<int> v{1,2,3,4,5};
    auto it = v.begin();
    v.reserve(100); // 扩容，旧空间释放，it 失效

    while(it != v.end()) {
        cout << *it << " "; // 错误：使用失效迭代器
        ++it;
    }
}

vs下直接崩溃

g++下可能正常运行，但会出现乱码错误。

例二

int main() {
    vector<int> v{1,2,3,4,5};
    auto it = find(v.begin(), v.end(), 3);
    v.erase(it); // 删除 3，后续元素（4,5）前移

    cout << *it << endl; // g++ 下输出 4
    while(it != v.end()) {
        cout << *it << " "; // 输出 4 5
        ++it;
    }
}

在g++下正常运行

例三

int main() {
    vector<int> v{1,2,3,4,5}; // 第一组数据：运行“正常”
    // vector<int> v{1,2,3,4,5,6}; // 第二组数据：崩溃

    auto it = v.begin();
    while(it != v.end()) {
        if(*it % 2 == 0)
            v.erase(it); // 删除偶数后，it 失效
        ++it; // 对失效迭代器自增
    }
}

第一组正常是巧合，删除最后一个偶数4之后，it恰好指向5，循环结束，未触发越界

第二组数据崩溃，删除最后一个偶数6之后，it指向end()之外，++it导致访问非法内存

vector在oj中的应用

只出现一次的数

#include<iostream>
#include<vector>
using namespace std;
int singleNumber(vector<int>& nums)
{
  int result=0;
  for(int num:nums)
  {
    result^=num;
  }
  return result;
}

int main()
{
  vector<int> nums={1,2,3};
  cout<<singleNumber(nums)<<endl;
  return 0;
}

杨辉三角

用二维vector<vector<int>>存储杨辉三角

每行初始化时，先push1，中间元素通过上一行计算，最后再push1

vector的核心结构

vector通过三个关键指针管理连续内存

1 start：指向数组的起始位置

2 finish：指向数组的有效元素的末尾的下一个位置（即最后一个元素的下一个地址）

3 end_of_storage:指向数组的容量末尾（即分配内存的最后一个位置的下一个地址）

通过这三个指针，可以推导出：

1有效元素个数（size）：finish-start

2容量：end_of_storage-start

vector的扩容机制

当push_back后，capacity==size，会触发扩容机制

1 分配新内存，通常扩容为原容量的2倍或1.5倍

2复制旧元素：将旧元素的内存拷贝到新内存

3释放旧空间：会把旧空间的元素拷贝到新空间

3释放旧内存，回收原来的内存空间

4更新start,end,end_of_storage指针

用memcpy拷贝vector的问题

容易引发浅拷贝问题

memcpy是浅拷贝，只会复制指针，而不会复制指针指向的内存，旧对象的指针和新对象的指向同一块内存，当旧对象析构的时候，新对象的指针变为野指针，后续访问新对象的指针或者析构内容，会触发非法内容访问。

正确操作：

对于动态内存的自定义类型，需要采用深拷贝。vector标准库的标准是深拷贝。

动态二维数组

动态二维数组的本质是：容器的容器。外层 vector 存储内层 vector，内层 vector 存储每行的元素

以杨辉三角为例子讲解：

void test(size_t n)
{
   vector<vector<int>> vv(n);//包含n个空的vector
   //初始化每行的长度并设置为1
   for(size_t i=0;i<n;++i)
   {
      vv[i].resize(i+1,1);//第i行有i+1个元素，并初始化为1
   }
//填充杨辉三角（从第2行开始）
   for(int i=2;i<n;++1)
   {
     for(int j=1;j<i:++j)
     {
        vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
      }
     }
  }