C++ STL vector
本文全面解析C++ STL中的vector容器，从基础使用到深度实现。主要内容包括：1. vector基础使用：构造函数、迭代器、容量管理(resize/reserve)、增删查改操作；2. 核心原理：扩容机制(1.5/2倍增长)、二维vector实现、迭代器失效问题及解决方案；3. 模拟实现：手写vector类模板，详解深拷贝与memcpy陷阱；4. 典型应用：结合OJ题目讲解异或运算、摩尔投票
vector 作为 STL 最常用的动态数组，是面试与刷题的高频考点。本文从接口使用、扩容机制、迭代器失效到模拟实现，带你彻底吃透 vector。
1. vector 的介绍与使用
1.1 学习 STL 的三个境界
• 能用：会调用接口
• 明理：理解底层原理
• 能扩展：能模拟实现或改造
1.2 vector 的使用
1.2.1 vector 的定义（构造函数）
| 构造函数 | 接口说明 |
| vector()（重点） | 无参构造 |
| vector(size_type n, const value_type& val = value_type()) | 构造并初始化 n 个 val |
| vector(const vector& x);（重点） | 拷贝构造 |
| vector(InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
示例：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// 1. vector() —— 无参构造（重点）
vector<int> v1;
cout << "v1 size: " << v1.size() << endl;
// 2. vector(size_type n, const value_type& val)
// 构造并初始化 n 个 val
vector<int> v2(10, 1);
cout << "v2: ";
for (auto e : v2) cout << e << " ";
cout << endl;
// 3. vector(const vector& x) —— 拷贝构造（重点）
vector<int> v3(v2);
cout << "v3: ";
for (auto e : v3) cout << e << " ";
cout << endl;
// 4. vector(InputIterator first, InputIterator last)
// 使用迭代器区间进行初始化构造
vector<int> v4(++v2.begin(), --v2.end());
cout << "v4: ";
for (auto e : v4) cout << e << " ";
cout << endl;
return 0;
}输出结果
v1 size: 0
v2: 1 1 1 1 1 1 1 1 1 1
v3: 1 1 1 1 1 1 1 1 1 1
v4: 1 1 1 1 1 1 1 1遍历方式
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1. 空容器
vector<int> v1;
// 2. 初始化 10 个值为 1 的元素
vector<int> v2(10, 1);
// 3. 使用迭代器区间构造：v2[1] ~ v2[8]
// 去掉第一个和最后一个元素
vector<int> v3(++v2.begin(), --v2.end());
// 4. 拷贝构造：用 v3 拷贝构造 v4
vector<int> v4(v3);
// 方式1：普通for循环 + []访问
cout << "v3 普通for循环：";
for (size_t i = 0; i < v3.size(); ++i) {
cout << v3[i] << " ";
}
cout << endl;
// 方式2：迭代器遍历
cout << "v3 迭代器遍历：";
vector<int>::iterator it = v3.begin();
while (it != v3.end()) {
cout << *it << " ";
++it;
}
cout << endl;
// 方式3：范围for
cout << "v3 范围for遍历：";
for (auto e : v3) {
cout << e << " ";
}
cout << endl;
// 验证拷贝构造的 v4 内容
cout << "v4 范围for遍历：";
for (auto e : v4) {
cout << e << " ";
}
cout << endl;
return 0;
}输出结果
v3 普通for循环：1 1 1 1 1 1 1 1
v3 迭代器遍历：1 1 1 1 1 1 1 1
v3 范围for遍历：1 1 1 1 1 1 1 1
v4 范围for遍历：1 1 1 1 1 1 1 11.2.2 vector iterator 的使用
| 迭代器接口 | 接口说明 |
| begin() / end()（重点） | 获取第一个数据位置的 iterator/const_iterator；获取最后一个数据的下一个位置的 iterator/const_iterator |
| rbegin() / rend() | 获取最后一个数据位置的 reverse_iterator；获取第一个数据前一个位置的 reverse_iterator |
迭代器示意图：
• begin() 指向第一个元素
• end() 指向最后一个元素的下一个位置
• rbegin() 指向最后一个元素
• rend() 指向第一个元素的前一个位置
代码示例：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v = { 10,20,30,40,50 };
// ============================
// 1. begin() / end() 正向迭代器（重点）
// begin()：指向第一个元素
// end() ：指向最后一个元素的下一个位置
// ============================
cout << "begin()/end() 正向遍历：";
vector<int>::iterator it;
for (it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
// ============================
// 2. rbegin() / rend() 反向迭代器
// rbegin()：指向最后一个元素
// rend() ：指向第一个元素的前一个位置
// ============================
cout << "rbegin()/rend() 反向遍历：";
vector<int>::reverse_iterator rit;
for (rit = v.rbegin(); rit != v.rend(); ++rit)
{
cout << *rit << " ";
}
cout << endl;
return 0;
}输出结果
begin()/end() 正向遍历：10 20 30 40 50
rbegin()/rend() 反向遍历：50 40 30 20 10• begin()/end()：正向遍历，从头到尾
• rbegin()/rend()：反向遍历，从尾到头
• 迭代器遍历是 STL 容器通用遍历方式
1.2.3 vector 空间增长问题
| 容量接口 | 接口说明 |
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize（重点） | 改变 vector 的 size，会初始化新空间 |
| reserve（重点） | 改变 vector 的 capacity，不初始化 |
扩容机制：
• VS（PJ版STL）：按 1.5倍 增长
• g++（SGI版STL）：按 2倍 增长
• reserve 只负责开辟空间，可缓解扩容代价缺陷
• resize 开空间同时初始化，影响 size
测试默认扩容机制代码：
// 测试vector的默认扩容机制
void TestVectorExpand()
{
size_t sz;
vector<int> v;
sz = v.capacity();
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}VS 运行结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
g++ 运行结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
提前设置容量避免扩容：
// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
vector<int> v;
size_t sz = v.capacity();
v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
cout << "making bar grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}代码示例：
#include <iostream>
#include <vector>
using namespace std;
void test_vector_capacity()
{
cout << "===== vector 容量接口测试 =====" << endl;
vector<int> v;
// 1. empty 判断是否为空
cout << "empty: " << v.empty() << endl;
// 2. size 数据个数 capacity 容量
v.resize(10, 1);
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << endl;
cout << endl;
// 3. reserve（重点）：只改容量，不改size，不初始化
v.reserve(20);
cout << "reserve(20)" << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << endl;
cout << endl;
// reserve 不会缩容
v.reserve(15);
cout << "reserve(15)" << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << endl;
cout << endl;
// 4. resize（重点）：改size，会初始化新空间
v.resize(15, 2);
cout << "resize(15, 2)" << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << endl;
cout << endl;
v.resize(5);
cout << "resize(5)" << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << endl;
}
int main()
{
test_vector_capacity();
return 0;
}输出结果
===== vector 容量接口测试 =====
empty: 1
size: 10
capacity: 10
reserve(20)
size: 10
capacity: 20
reserve(15)
size: 10
capacity: 20
resize(15, 2)
size: 15
capacity: 20
resize(5)
size: 5
capacity: 20• size：实际有多少个元素
• capacity：最多能存多少个元素
• empty：判断是否为空
• reserve：只扩容量，不改大小，不初始化
• resize：改元素个数，会初始化，变大扩容，变小删元素
reserve和resize的核心区别
#include <iostream>
#include <vector>
using namespace std;
// 测试 reserve：只改容量 capacity，不改大小 size
void test_vector1()
{
cout << "===== test_vector2: reserve 演示 =====" << endl;
vector<int> v(10, 1);
v.reserve(20); // 扩容到容量 20
cout << "size: " << v.size() << endl; // 10
cout << "capacity: " << v.capacity() << endl;// 20
cout << endl;
v.reserve(15); // 比当前容量小，**不会缩容**
cout << "size: " << v.size() << endl; // 10
cout << "capacity: " << v.capacity() << endl;// 20
cout << endl;
v.reserve(5); // 比当前容量小，**不会缩容**
cout << "size: " << v.size() << endl; // 10
cout << "capacity: " << v.capacity() << endl;// 20
cout << endl;
}
// 测试 resize：改大小 size，可能影响容量 capacity
void test_vector2()
{
cout << "===== test_vector3: resize 演示 =====" << endl;
vector<int> v(10, 1);
v.reserve(20);
cout << "size: " << v.size() << endl; // 10
cout << "capacity: " << v.capacity() << endl;// 20
cout << endl;
v.resize(15, 2); // size 变大到 15，新增用 2 初始化
cout << "size: " << v.size() << endl; // 15
cout << "capacity: " << v.capacity() << endl;// 20
cout << endl;
v.resize(25, 3); // size 超过 capacity，自动扩容
cout << "size: " << v.size() << endl; // 25
cout << "capacity: " << v.capacity() << endl;// ≥25
cout << endl;
v.resize(5); // size 变小到 5，删后面元素，**容量不变**
cout << "size: " << v.size() << endl; // 5
cout << "capacity: " << v.capacity() << endl;// ≥25
cout << endl;
}
int main()
{
test_vector1();
test_vector2();
return 0;
}1. reserve(n)
只改变 capacity，不改变 size； 只扩容、不缩容； 不初始化新空间
2. resize(n, val)
改变 size，可能改变 capacity； 变大：新增元素用 val 初始化； 变小：删除尾部元素，容量不变
会真正构造/销毁对象
1.2.4 vector 增删查改
| 接口 | 接口说明 |
| push_back（重点） | 尾插 |
| pop_back（重点） | 尾删 |
|
find |
查找（算法模块实现，非vector成员） |
| insert | 在 position 之前插入 val |
| erase | 删除 position 位置的数据 |
| swap | 交换两个 vector 的数据空间 |
| operator[]（重点） | 像数组一样访问 |
代码示例：
#include <iostream>
#include <vector>
#include <algorithm> // find 需要
using namespace std;
void test_vector_modify()
{
cout << "===== vector 增删查改接口测试 =====" << endl;
vector<int> v;
// 1. push_back 尾插（重点）
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
cout << "尾插后：";
for (auto e : v) cout << e << " ";
cout << endl;
// 2. pop_back 尾删（重点）
v.pop_back();
cout << "尾删后：";
for (auto e : v) cout << e << " ";
cout << endl;
// 3. operator[] 像数组一样访问（重点）
cout << "operator[] 访问：v[0] = " << v[0] << ", v[1] = " << v[1] << endl;
// 4. find 查找（算法，非vector成员函数）
vector<int>::iterator pos = find(v.begin(), v.end(), 20);
if (pos != v.end())
{
cout << "找到 20" << endl;
// 5. insert 在 position 之前插入
v.insert(pos, 99);
cout << "insert 99 后：";
for (auto e : v) cout << e << " ";
cout << endl;
}
// 6. erase 删除 position 位置的数据
if (pos != v.end())
{
v.erase(pos);
cout << "erase 删除后：";
for (auto e : v) cout << e << " ";
cout << endl;
}
// 7. swap 交换两个vector的空间
vector<int> v2{ 100, 200, 300 };
cout << "交换前 v2：";
for (auto e : v2) cout << e << " ";
cout << endl;
v.swap(v2);
cout << "swap 交换后 v：";
for (auto e : v) cout << e << " ";
cout << endl;
cout << "swap 交换后 v2：";
for (auto e : v2) cout << e << " ";
cout << endl;
}
int main()
{
test_vector_modify();
return 0;
}输出结果
===== vector 增删查改接口测试 =====
尾插后：10 20 30 40
尾删后：10 20 30
operator[] 访问：v[0] = 10, v[1] = 20
找到 20
insert 99 后：10 99 20 30
erase 删除后：10 99 30
交换前 v2：100 200 300
swap 交换后 v：100 200 300
swap 交换后 v2：10 99 30operator[] 和 at
• operator[]：不做越界检查
• at()：会做越界检查，越界抛异常
详细对比
1. operator[] v[i];
• 不检查边界，越界直接崩溃、乱码、踩内存，效率高，像数组一样用
2. at() v.at(i);
• 会检查边界，越界抛出异常 out_of_range，更安全，效率稍低一点点
代码示例（一看就懂）
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v{1,2,3};
// 1. operator[] 不检查，越界直接乱码/崩溃
// cout << v[100] << endl;
// 2. at() 检查，越界抛异常
try {
cout << v.at(100) << endl;
}
catch (const exception& e) {
cout << "at越界：" << e.what() << endl;
}
return 0;
}• []：不检查，快，不安全 at()：检查，安全，抛异常
vs系列编译器，debug模式下：at() 和 operator[] 都是根据下标获取任意位置元素的，在debug模式下两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 内部的assert会触发。
拓展
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void test_vector4()
{
cout << "===== test_vector4 =====" << endl;
vector<int> v(10, 1);
v.push_back(2); // 尾插 2
v.insert(v.begin(), 0); // 头插 0
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
// 在 begin+3 位置插入 10
v.insert(v.begin() + 3, 10);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
// 键盘输入到 vector
vector<int> v1(5, 0);
for (size_t i = 0; i < 5; i++)
{
cin >> v1[i];
}
// 逗号分隔输出
for (auto e : v1)
{
cout << e << ",";
}
cout << endl;
// 与 string 配合使用场景示例（网络发送常用）
vector<char> v2;
string s2;
// v2 可以用来接收 s2 的数据，处理不含 \0 的场景
vector<int> v3;
// 网络发送场景：send(s2.c_str(), ...)
}
void test_vector5()
{
cout << "===== test_vector5 =====" << endl;
// vector 存放 string
vector<string> v1;
string s1("xxxx");
v1.push_back(s1);
v1.push_back("yyyyy");
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
// 二维 vector：10 行 5 列，初始全 1
vector<int> v(5, 1);
vector<vector<int>> vv(10, v);
// 修改第 2 行第 1 列为 2
vv[2][1] = 2;
// 本质：vv.operator[](2).operator[](1) = 2;
// 打印二维数组
for (size_t i = 0; i < vv.size(); i++)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
int main()
{
test_vector4();
test_vector5();
return 0;
}输出结果
===== test_vector4 =====
0 1 1 1 1 1 1 1 1 1 1 2
0 1 1 10 1 1 1 1 1 1 1 1 2
1 2 3 4 5
1,2,3,4,5,
===== test_vector5 =====
xxxx yyyyy
1 1 1 1 1
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1.2.5 vector operator[] 与二维 vector 原理
一、原始模板类（通用 vector）
template<class T>
class vector
{
public:
T& operator[](int i)
{
assert(i < _size);
return _a[i];
}
private:
T* _a; // 指向存储数据的数组
size_t _size; // 有效数据个数
size_t _capacity;// 容量
};二、vector 实例化后（编译器替换）
// vector<int> 本质
class vector
{
public:
int& operator[](int i)
{
assert(i < _size);
return _a[i];
}
private:
int* _a;
size_t _size;
size_t _capacity;
};三、vector<vector> 实例化后（重点！）
// vector<vector<int>> 本质
class vector
{
public:
// 返回值是 vector<int>&，因为 T = vector<int>
vector<int>& operator[](int i)
{
assert(i < _size);
return _a[i];
}
private:
// 数组里存的是 vector<int> 对象
vector<int>* _a;
size_t _size;
size_t _capacity;
};四、核心原理（一句话讲透）
vector<vector<int>> vv(10, vector<int>(5, 1));
• vv 是一个 vector，里面存的是 10 个 vector<int> 对象
• vv._a 的类型是：vector<int>*
• vv[i] 返回：vector<int>&
• vv[i][j] 本质：vv.operator[](i).operator[](j)
第一次 [i] → 拿到第 i 行的 vector& ；第二次 [j] → 拿到这一行里第 j 个 int&
这就是 二维 vector 支持 [][] 访问的底层原理。
总结：
1. vector 是模板类，T 是什么，底层就存什么。
2. vector<int>： _a 是 int* operator[] 返回 int&
3. vector<vector<int>>： _a 是 vector<int>* operator[] 返回 vector<int>&
4. vv[i][j] 是连续两次调用 operator[]，第一次取行，第二次取列。
1.2.6 vector 迭代器失效问题（重点）
迭代器本质：
迭代器是对原生指针的封装，迭代器失效 = 底层指针指向的空间被释放，继续使用会导致程序崩溃。
会导致迭代器失效的操作：
• 引起底层空间改变的操作：resize、reserve、insert、assign、push_back 等
• erase 删除任意位置元素（VS 下一定失效；Linux 下若删除最后一个元素，it 会变成 end()，再 ++it 会崩溃）
迭代器失效示例代码：
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
// v.resize(100, 8);
// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
// v.reserve(100);
// 插入元素期间，可能会引起扩容，而导致原空间被释放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 给vector重新赋值，可能会引起底层容量改变
v.assign(100, 8);
/*
出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块
已经被释放的空间，而引起代码运行时崩溃。
解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给
it重新赋值即可。
*/
while(it != v.end())
{
cout<< *it << " " ;
++it;
}
cout<<endl;
return 0;
}#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
// 都会导致扩容 → 旧空间释放 → 迭代器 it 失效
// v.resize(100, 8);
// v.reserve(100);
// v.insert(v.begin(), 0);
// v.push_back(8);
v.assign(100, 8);
// 这里 it 还是指向原来已经被释放的空间！
// 下面的循环会崩溃：迭代器失效
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}运行结果：程序直接崩溃 / 乱码 / 死循环，因为迭代器 it 已经失效。
vector 底层是一块连续的数组
v = [1,2,3,4,5,6]
↑
it（指向这块内存的开头）
v.assign(100, 8);
vector 发现：现在空间只有 6 个位置，要存 100 个，不够了 → 必须扩容
扩容：新开一块更大的空间（比如100个位置），把数据拷贝到新空间，释放旧的空间！
//it 还指向已经被释放的旧空间！it 现在就是野指针。
旧空间：已被系统回收
it ——→ 【无效内存】
新空间：[8,8,8,...8]
↑
新的 begin()，it 根本不知道它在哪正确写法（修复迭代器失效）
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
v.assign(100, 8);
// 清空vector原有所有元素，重新放入n个值为val的元素，可能会扩容/重新开辟空间
// 把v原来的{1,2,3,4,5,6}全部删掉，换成100个8，底层空间不够就扩容，旧空间释放
// 所以原来的迭代器 it 直接失效！
// ✅ 修复：迭代器失效后，重新获取
it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}assign、operator=、resize
• v = {1,2,3}; 整体赋值
• v.assign(5,10); 清空 → 换新内容
• v.resize(5,10); 改变大小，不清空前面内容
assign = 清空旧数据 → 分配新数据 → 可能扩容 → 迭代器失效
迭代器失效原因：
• resize/reserve/insert/push_back/assign 等操作可能引起扩容；扩容会释放旧空间
• 原来的迭代器还指向已释放空间 → 变成野指针 → 程序崩溃
解决方法：
• 凡是可能引起扩容的操作后，迭代器必须重新获取
erase 导致迭代器失效示例：
#include <iostream>
#include <vector>
#include <algorithm> // find 需要
using namespace std;
int main()
{
int a[] = { 1, 2, 3, 4 };
// 用数组区间构造 vector
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 查找值为 3 的迭代器
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
if (pos != v.end()) // 一定要先判断！
{
// 删除 pos 位置元素：3 被删掉
v.erase(pos);
// ❌ 错误：pos 已经失效！
// erase 之后，pos 指向的空间已经被删除或移动
// 再访问 *pos 就是非法访问，程序崩溃
// cout << *pos << endl;
}
// 正确遍历
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
return 0;
}输出：1 2 4
核心知识点
1. erase 为什么会让迭代器失效？
erase(pos) 删除某个元素后，后面的元素会往前移动，原来的迭代器 pos 已经不再指向有效元素，再使用 *pos 就是未定义行为（崩溃/乱码）
2. 正确使用 erase 的写法
pos = v.erase(pos);• erase 会返回下一个有效迭代器，接收回来，迭代器就恢复有效
总结：erase 会导致迭代器失效，必须用返回值重新接收，不能继续用旧迭代器！
删除偶数代码对比：
❌ 错误写法：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it); // ❌ erase 后 it 已经失效
++it; // ❌ 继续使用失效迭代器，崩溃/越界
}
return 0;
}问题：erase(it) 后 it 失效，++it 访问非法空间。
erase(it) 会删除元素，后面元素前移，被删位置的迭代器 it 直接失效，再写 ++it → 未定义行为（程序崩溃、死循环、越界）
v = [ 1 , 2 , 3 , 4 ]
↑
it
v.erase(it); // 删除 2
[ 1 , 3 , 4 ]
↑
原来it还指向这里
it 还站在原来的位置，但数据已经整体前移了，it 现在指向的是无效位置/非法数据
erase 之后，原来的 it 已经废了，不能再用！✅ 正确写法：
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;
}原因：erase 返回被删除元素之后的第一个有效迭代器。
Linux vs VS 迭代器失效差异：
• VS：对迭代器失效检测严格，erase 任意位置后迭代器都失效
• Linux（g++）：erase 后若空间未变，迭代器仍有效；但删除最后一个元素后 it 变为 end()，++it 会崩溃
string 迭代器失效：string 在插入/扩容/erase 后，迭代器也会失效，解决方法同样是重新赋值。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s = "123456";
string::iterator it = s.begin();
// 1. 扩容/插入会导致迭代器失效（和 vector 一样）
s.resize(100, 'x');
// ❌ it 已经失效，访问会崩溃/乱码
// cout << *it << endl;
// ✅ 解决：重新获取迭代器
it = s.begin();
while (it != s.end())
{
cout << *it;
++it;
}
cout << endl;
// 2. erase 也会失效
it = s.begin();
it = s.erase(it); // ✅ 必须接收返回值
cout << s << endl;
return 0;
}1.3 vector 在 OJ 中的使用
1. 只出现一次的数字
情况一
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 二次 。请你找出并返回那个只出现了一次的元素。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int value = 0;
for(auto e : nums)
{
value ^= e;
}
return value;
}
};1. 任何数和 0 异或 → 还是它自己
2. 任何数和自己异或 → 等于 0
3. 异或满足交换律、结合律
所以：出现两次的数，两两抵消变成 0， 最后剩下的就是只出现一次的那个数
情况二
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 1. 初始化一个长度为32的数组，记录每个二进制位上1出现的次数
vector<int> cnt(32, 0);
// 2. 遍历数组中的每个数字
for (auto &x : nums) {
// 3. 遍历当前数字的每一位（0~31位）
for (int i = 0; i < 32; ++i) {
// (x >> i)：把x的第i位移到最低位
// & 1：提取最低位的0或1
// 把结果累加到cnt[i]，统计第i位上1的总次数
cnt[i] += (x >> i) & 1;
}
}
// 4. 初始化答案为0
int ans = 0;
// 5. 遍历每个二进制位
for (int i = 0; i < 32; ++i) {
// 如果第i位上1的次数不是3的倍数，说明该位属于目标数字
if (cnt[i] % 3 != 0) {
// 把1左移i位，再和ans进行或运算，把该位设置为1
ans |= (1 << i);
}
}
// 6. 返回结果
return ans;
}
};举个例子（输入 nums = [2,2,3,2]）
第一步：先理解二进制和十进制的对应
• 十进制的 2 → 二进制是 10（意思是：1个2 + 0个1）
• 十进制的 3 → 二进制是 11（意思是：1个2 + 1个1）
• 这里的第0位是最右边的那一位（对应十进制的1），第1位是右数第二位（对应十进制的2）。
第二步：统计每一位上1的次数
输入是 [2,2,3,2]，我们把每个数字的二进制写出来：
• 第1个数字 2 → 10 → 第0位是0，第1位是1
• 第2个数字 2 → 10 → 第0位是0，第1位是1
• 第3个数字 3 → 11 → 第0位是1，第1位是1
• 第4个数字 2 → 10 → 第0位是0，第1位是1
现在统计每一位上1出现的次数：
• 第0位：0+0+1+0 = 1 → 1除以3余1，不是3的倍数 → 保留
• 第1位：1+1+1+1 = 4 → 4除以3余1，不是3的倍数 → 保留
第三步：把保留的位组合成结果
• 第0位保留 → 对应十进制的1
• 第1位保留 → 对应十进制的2
• 把它们加起来：2 + 1 = 3 → 就是最终答案
这里的 10 | 01 是二进制的或运算，10 对应2，01 对应1，或运算后得到 11，也就是十进制的3。
最终答案：通过统计二进制每一位1的出现次数，筛选出目标数字的二进制位，组合后得到十进制3
nums = [4,4,4,1] 只有 1 出现 1 次，别的都出现 3 次。
1. 先把数字写成二进制
• 4 → 二进制 100 1 → 二进制 001
我们只看 第 0 位、第 1 位、第 2 位：
| 数字 | 二进制 | 第2位（4） | 第1位（2） | 第0位（1） |
| 4 | 100 | 1 | 0 | 0 |
| 4 | 100 | 1 | 0 | 0 |
| 4 | 100 | 1 | 0 | 0 |
| 1 | 001 | 0 | 0 | 1 |
2. 统计每一位上 1 出现多少次
第 0 位（最右边）：0 + 0 + 0 + 1 = 1 次
第 1 位：0 + 0 + 0 + 0 = 0 次
第 2 位：1 + 1 + 1 + 0 = 3 次
3. 看哪些位 不是 3 的倍数
规则：出现 3 次 → 抵消（不要） 不是 3 次 → 这一位是答案的位
• 第0位：1 次 → 保留 第1位：0 次 → 不保留 第2位：3 次 → 抵消
4. 组合答案
只有 第0位 保留：二进制：1 十进制：1 最终答案：1
超级简单总结
1. 每个数字拆成 32 位二进制
2. 统计每一位 1 出现多少次
3. 次数 %3 != 0 → 这一位是答案
4. 把这些位拼起来 → 就是只出现一次的数字
情况三
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
// 1. 初始化异或结果为0
unsigned int xor_all = 0;
// 2. 遍历数组，计算所有元素的异或
for (int x : nums) {
xor_all ^= x;
}
// 3. 找到异或结果中最低位的1，作为分组依据
int lowbit = xor_all & -xor_all;
// 4. 初始化答案数组
vector<int> ans(2);
// 5. 再次遍历数组，按最低位的1分组异或
for (int x : nums) {
if ((x & lowbit) == 0) { // x 在第一组
ans[0] ^= x;
} else { // x 在第二组
ans[1] ^= x;
}
}
// 6. 返回结果
return ans;
}
};整体思路
这道题的核心是利用异或运算的性质，把数组中出现两次的数字抵消，从而找到只出现一次的两个数字。
1. 整体异或：先把数组中所有元素异或，得到结果 xor_all，它等于两个只出现一次的数字的异或结果（记为 a ^ b）。
2. 找区分位：找到 xor_all 中任意一个为 1 的二进制位（说明 a 和 b 在这一位上不同），用这个位把数组分成两组。
3. 分组异或：对两组分别进行异或，每组的结果就是 a 和 b。
逐行解释
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
// 1. 初始化异或结果为0
unsigned int xor_all = 0;
// 2. 遍历数组，计算所有元素的异或
for (int x : nums) {
xor_all ^= x;
}
• unsigned int xor_all = 0;：使用 unsigned int 是为了避免在计算 -xor_all 时出现溢出问题，特别是当 xor_all 为 INT_MIN 时。
• for (int x : nums) { xor_all ^= x; }：遍历数组，将所有元素依次异或。
◦ 异或的性质：x ^ x = 0，x ^ 0 = x。
◦ 数组中出现两次的元素会相互抵消，最终 xor_all 就是两个目标数字 a 和 b 的异或值，即 a ^ b。
// 3. 找到异或结果中最低位的1，作为分组依据
int lowbit = xor_all & -xor_all;
• lowbit = xor_all & -xor_all;：这个操作可以快速得到 xor_all 中最低位的1。
例如 xor_all = 6（二进制 110），-xor_all 是补码形式 ...11111010，两者按位与后得到 2（二进制 10），也就是最低位的1。
◦ 这个位是 a 和 b 二进制表示中不同的位，可用于将数组分成两组。
// 4. 初始化答案数组
vector<int> ans(2);
// 5. 再次遍历数组，按最低位的1分组异或
for (int x : nums) {
if ((x & lowbit) == 0) { // x 在第一组
ans[0] ^= x;
} else { // x 在第二组
ans[1] ^= x;
}
}
• vector<int> ans(2);：初始化一个大小为2的数组，用来存储两个只出现一次的数字。
• for (int x : nums) { ... }：再次遍历数组，根据每个数字与 lowbit 的按位与结果分组：
若 (x & lowbit) == 0，则 x 的二进制中 lowbit 对应位为0，分到第一组，异或到 ans[0]。
若 (x & lowbit) != 0，则 x 的二进制中 lowbit 对应位为1，分到第二组，异或到 ans[1]。
◦ 每组内出现两次的数字会抵消，最终 ans[0] 和 ans[1] 就是 a 和 b。
示例验证（输入 nums = [1,2,1,3,2,5]）
• 异或整体：1^2^1^3^2^5 = 3^5 = 6(110)
• 最低位的1：2(10)
• 分组：
该位为0的数：1,1,5 → 异或结果 5
该位为1的数：2,2,3 → 异或结果 3
• 最终结果：ans = [5, 3]（顺序可以交换）✅
总结： 时间复杂度：O(n)，只需要两次遍历数组。 空间复杂度：O(1)，只使用了常量额外空间。
• 核心原理：利用异或运算抵消重复元素，再通过分组异或分离出两个只出现一次的数字。
2. 杨辉三角
// 涉及resize / operator[]
// 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv(numRows);
for (size_t i = 0; i < numRows; i++)
{
vv[i].resize(i + 1, 1);
//vv[i][0] = vv[i][vv[i].size()-1] = 1;
//vv[i].front = vv[i].back() = 1;
}
for (int i = 2; i < vv.size(); i++)
{
for (int j = 1; j < vv[i].size() - 1; j++)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
return vv;
}
};3. 删除排序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。
nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。
解法一：计数后安置--对非重复元素计数，然后放入指定位置即可。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int cnt = 1; // 先计入 nums[0]
for(int i = 1; i < nums.size(); i++){
if(nums[i] != nums[i-1]){ // 发现非重复元素
cnt++; // 计数
nums[cnt - 1] = nums[i]; // 放入 cnt - 1 处
// 以上两行可以简化合并，但个人更倾向于可读性
}
}
return cnt;
}
};解法二：循环不变量--跳过后续重复的元素，将其他元素向左偏移。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int l = 0;
for(int r = 0; r < nums.size(); r++){
if(nums[l] != nums[r]){
// 可以合并成 nums[++l] = nums[r]
l++;
nums[l] = nums[r];
}
}
// 返回不同数字的数量，即 k
return l + 1;
}
};解法二：快慢指针
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
};4. 数组中出现次数超过一半的数字
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
解析1：
摩尔投票法的通俗理解，我们可以把这个过程想象成投票竞选：
• 数组里的每个数字都是一个选民，他们要选一个“超级候选人”（出现次数超过一半的数字）。
• 我们先随便选一个候选人，然后开始“拉票”：
◦ 遇到和候选人一样的选民，就给他加一票（count += 1）。
◦ 遇到不一样的选民，就相当于“抵消”一票（count -= 1）。
◦ 如果票数被抵消到0，就换当前这个选民当新的候选人。
因为目标数字的数量超过一半，所以最后剩下的候选人一定是它✅
#include <iostream>
#include <vector>
using namespace std;
// 找出现次数超过一半的数字
int findMajorityElement(vector<int>& nums) {
int candidate = 0; // 候选数字
int count = 0; // 候选人的票数
for (int num : nums) { // 遍历数组里的每个数字
if (count == 0) { // 如果票数为0，换当前数字当候选人
candidate = num;
count = 1;
} else {
// 如果当前数字和候选人相同，票数+1；否则-1
count += (num == candidate) ? 1 : -1;
}
}
return candidate; // 最后剩下的候选人就是答案
}
int main() {
int n;
cin >> n; // 输入数组长度
vector<int> nums(n); // 创建一个长度为n的数组
for (int i = 0; i < n; ++i) {
cin >> nums[i]; // 输入数组的每个元素
}
cout << findMajorityElement(nums) << endl; // 输出结果
return 0;
}举个例子：比如输入数组[1,2,3,2,2,5,4,2]：
1. 开始count=0，选1当候选人，count=1。
2. 遇到2，和候选人不同，count=0。
3. 遇到3，count=0，选3当候选人，count=1。
4. 遇到2，和候选人不同，count=0。
5. 遇到2，count=0，选2当候选人，count=1。
6. 遇到5，和候选人不同，count=0。
7. 遇到4，count=0，选4当候选人，count=1。
8. 遇到2，和候选人不同，count=0。
9. 遍历结束，最后一次有效的候选人是2，就是答案。
解析2:
因为题目保证存在一个数字出现次数超过数组长度的一半，所以将数组排序后：
• 这个数字一定会占据数组的中间位置（下标为numbers.size()/2）。
• 比如长度为9的数组，中间位置是下标4；长度为8的数组，中间位置是下标4。
这个方法的时间复杂度是O(n\log n)（主要来自排序），空间复杂度是O(1)（如果使用原地排序）。
int MoreThanHalfNum_Solution(vector<int>& numbers) {
sort(numbers.begin(),numbers.end());
return numbers[numbers.size()/2];
}严谨写法：
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
sort(numbers.begin(), numbers.end());
int cond = numbers[numbers.size() / 2];
// 先对数组排序，取出中间位置的元素作为候选值。
// 遍历数组，统计候选值的出现次数。
int cnt = 0;
for (const int k :numbers) {
if (cond == k) ++cnt;
}
// 如果候选值的出现次数超过数组长度的一半，就返回它；否则返回0
if (cnt > numbers.size() / 2) return cond;
return 0;
}
};时间复杂度
• 排序的时间复杂度为O(n\log n)，遍历统计的时间复杂度为O(n)，整体时间复杂度为O(n\log n)。
• 空间复杂度为O(1)（原地排序）。
5. 电话号码字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
// 数字到字母的对应表，0和1没有字母
const string map[] = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
// 存储结果，初始为空字符串，后面所有组合都是从这个空字符串开始拼出来的
vector<string> res = {""};
// 如果输入为空，直接返回空结果
if (digits.empty()) {
return {};
}
// 遍历每个数字
for (char c : digits) {
int num = c - '0'; // 把字符变成数字
string letters = map[num];
vector<string> temp;
// 把当前结果里的每个字符串，和当前数字的每个字母拼接
for (string s : res) { // 遍历现在已有的所有字符串
for (char letter : letters) { // 遍历当前数字的每个字母
temp.push_back(s + letter); // 拼接
}
}
res = temp; // 更新结果
}
// 返回结果，把新拼好的所有结果，覆盖旧结果。下一轮继续拼。
return res;
}
};
// 测试代码
int main() {
Solution s;
vector<string> result = s.letterCombinations("29");
for (string str : result) {
cout << str << " ";
}
return 0;
}第一层循环：拿之前拼好的每一段
比如之前是 ["a", "b", "c"] 它会一个一个拿： 先拿 "a"， 再拿 "b"， 再拿 "c"
旧 res 一开始是：res = { "" }
然后两层循环拼出 a、b、c，放到 temp 里：temp = { "a", "b", "c" }
然后执行：res = temp; 意思就是：把 res 扔掉，换成 temp 的内容。
现在 res 就变成了：res = { "a", "b", "c" }
第二层循环：给每一段，加上当前所有字母，当前字母是 w x y z
所以： a + w → aw， a + x → ax， a + y → ay， a + z → az， b + w → bw， b + x → bx ...
所有拼好的都放进 temp。
旧 res 是：{ "a", "b", "c" }
两层循环拼完后，temp 变成：{ "aw","ax","ay","az","bw","bx","by","bz","cw","cx","cy","cz" }
然后再执行：res = temp; 意思还是：把旧 res 扔掉，换成新的 temp。现在 res 就是最终答案了。
2. vector 深度剖析及模拟实现
2.1 std::vector 的核心框架
vector 底层由三个指针构成：
start：指向空间起始位置； finish：指向最后一个有效元素的下一个位置
end_of_storage：指向已分配空间的末尾
扩容过程：开辟新空间； 拷贝旧空间元素到新空间； 释放旧空间； 更新三个指针
2.2 使用 memcpy 拷贝问题
问题代码：
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
memcpy(tmp, _start, old_size * sizeof(T));
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}正确代码：
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}为什么 memcpy 不行？
核心一句话：memcpy 是内存拷贝，只拷贝二进制数据，不调用构造/析构函数。
for 循环赋值 tmp[i] = _start[i] 会调用 operator=，是深拷贝。
如果 T 是int、double这种简单类型 → memcpy 没问题。
但如果 T 是string、vector、自定义类 → memcpy 直接爆炸！
用 string 举个例子，假设我们存的是 string：
vector<string> v;
v.push_back("hello");
v.push_back("world");
string 内部大概长这样：
class string
{
char* _str; // 指向堆上的字符
...
};如果你用 memcpy 拷贝 tmp[i] 内存拷贝 _start[i]
结果是：tmp[i]._str 和 _start[i]._str 指向同一块堆内存！这叫浅拷贝。
然后你执行：delete[] _start;
一 delete，原来的 string 释放内存。新的 tmp 里的 string 就变成野指针了！程序直接崩溃。
string 对象
┌──────────┐
│ char* ptr ───→ 堆内存 "hello"
└──────────┘
memcpy(tmp, _start, old_size * sizeof(T));
旧空间 _start[i]
┌──────────┐
│ ptr ────────┐
└──────────┘ │
↓
"hello" 堆内存
↑
新空间 tmp[i] │
┌──────────┐ │
│ ptr ────────┘
└──────────┘
两个 string 指向同一块内存！（浅拷贝） 执行 delete[] _start;
→ 旧string析构，把堆内存释放了。→ 新tmp[i]的ptr变成 野指针。→ 程序崩溃。但用 for 循环 tmp[i] = _start[i] 就完全不同 tmp[i] = _start[i]; 这句话会调用：
string& operator=(const string& s)
{
// 深拷贝！
// 新开一块内存，把内容复制过去
}结果： tmp[i] 有自己独立的内存； 旧空间释放不影响新空间； 安全、正确、不崩溃
旧空间 _start[i]
┌──────────┐
│ ptr ───→ "hello"
└──────────┘
新空间 tmp[i]
┌──────────┐
│ ptr ───→ "hello" // 新开一块内存！
└──────────┘
两个 string 各指向自己的内存，互不影响。再 delete 旧空间，新空间完全安全。超级总结：memcpy：内存拷贝 → 浅拷贝 → 复杂类型会炸
for 循环赋值：调用 operator= → 深拷贝 → 所有类型都安全
vector 要支持任意类型 T，所以绝对不能用 memcpy。
2.3 动态二维数组理解
以杨辉三角为例：
// 以杨辉三角的前n行为例：假设n为5
void test2vector(size_t n)
{
// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>
gxy::vector<gxy::vector<int>> vv(n);
// 将二维数组每一行中的vector<int>中的元素全部设置为1
for (size_t i = 0; i < n; ++i)
vv[i].resize(i + 1, 1);
// 给杨辉三角出第一列和对角线的所有元素赋值
for (int i = 2; i < n; ++i)
{
for (int j = 1; j < i; ++j)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}内存结构：
• 外层 vector 存储多个 vector<int>
• 每个内层 vector 独立管理自己的空间
• 填充后形成杨辉三角结构
2.4 vector 模拟实现
vector.h
#pragma once
#include <assert.h>
#include <list>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
namespace gxy
{
template <class T>
class vector
{
public:
typedef T *iterator;
typedef const T *const_iterator;
/*vector()
{}*/
// C++11 前置生成默认构造，显式要求编译器生成默认构造函数，初始化三个指针为 nullptr。
vector() = default;
vector(const vector<T> &v) // 拷贝构造函数
{
reserve(v.size());
for (auto &e : v)
{
push_back(e);
}
}
// 类模板的成员函数，还可以继续是函数模版
template <class InputIterator>
vector(InputIterator first, InputIterator last) // 迭代器范围构造函数
{
while (first != last)
{
push_back(*first);
++first;
}
}
// 提供了 size_t 和 int 两个重载，避免类型歧义。
// T() 是默认值，代表类型 T 的默认构造值（如 int 是 0，string 是空串）。
vector(size_t n, const T &val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T &val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
void clear()
{
_finish = _start;
}
// v1 = v3
/*vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
clear();
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
return *this;
}*/
// 交换两个 vector 的内部指针，实现高效“交换内容”，时间复杂度 O(1)。
void swap(vector<T> &v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// v1 = v3
// vector& operator=(vector v)
vector<T> &operator=(vector<T> v)
{
swap(v);
return *this;
}
// 形参是传值，会先调用拷贝构造生成一个临时副本 v。用 swap 把当前对象和 v 的内部指针交换。
// 函数结束时，v 会被销毁，原来的旧内存也被释放。
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T *tmp = new T[n];
// memcpy(tmp, _start, old_size * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
bool empty() const
{
return _start == _finish;
}
void push_back(const T &x)
{
// 扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
iterator insert(iterator pos, const T &x)
{
assert(pos >= _start);
assert(pos <= _finish);
// 扩容
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
}
T &operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T &operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
/*void print_vector(const vector<int>& v)
{
vector<int>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}*/
// 用迭代器和范围 for 两种方式打印 vector 内容。
template <class T>
void print_vector(const vector<T> &v)
{
// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator
// 是类型还是静态成员变量
// typename vector<T>::const_iterator it = v.begin();
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
// 这是一个更通用的模板，只要容器有 begin/end，就能打印，不限于我们自己的 vector。
template <class Container>
void print_container(const Container &v)
{
/*auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;*/
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
print_vector(v);
vector<double> vd;
vd.push_back(1.1);
vd.push_back(2.1);
vd.push_back(3.1);
vd.push_back(4.1);
vd.push_back(5.1);
print_vector(vd);
}
void test_vector2()
{
std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
print_container(v);
/*v.insert(v.begin() + 2, 30);
print_vector(v);*/
int x;
cin >> x;
auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{
// insert以后p就是失效，不要直接访问，要访问就要更新这个失效的迭代器的值
/*v.insert(p, 20);
(*p) *= 10;*/
p = v.insert(p, 40);
(*(p + 1)) *= 10;
}
print_container(v);
}
void test_vector3()
{
std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_container(v);
// 删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
print_container(v);
}
void test_vector4()
{
int i = int();
int j = int(1);
int k(2);
vector<int> v;
v.resize(10, 1);
v.reserve(20);
print_container(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
v.resize(15, 2);
print_container(v);
v.resize(25, 3);
print_container(v);
v.resize(5);
print_container(v);
}
void test_vector5()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
print_container(v1);
vector<int> v2 = v1;
print_container(v2);
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
v1 = v3;
print_container(v1);
print_container(v3);
}
void test_vector6()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(4);
v1.push_back(4);
vector<int> v2(v1.begin(), v1.begin() + 3);
print_container(v1);
print_container(v2);
list<int> lt;
lt.push_back(10);
lt.push_back(10);
lt.push_back(10);
lt.push_back(10);
vector<int> v3(lt.begin(), lt.end());
print_container(lt);
print_container(v3);
vector<string> v4(10, "1111111");
print_container(v4);
vector<int> v5(10);
print_container(v5);
vector<int> v6(10, 1);
print_container(v6);
}
void test_vector7()
{
vector<string> v;
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
print_container(v);
v.push_back("11111111111111111111");
print_container(v);
}
}
test.cpp
#include "vector.h"
int main()
{
gxy::test_vector7();
return 0;
}3. 核心总结
1. vector 本质：动态数组，支持随机访问，自动扩容。
2. 迭代器失效：扩容、插入、删除等操作可能导致迭代器失效，使用前需重新赋值。
3. 扩容效率：提前使用 reserve 可避免频繁扩容，提升性能。
4. 拷贝注意：资源管理类对象不能用 memcpy，应使用深拷贝。
5. OJ 使用：遍历优先用 operator[]，插入删除用 push_back/erase 等接口。
vector 是 C++ 开发与刷题中最基础也最重要的容器。熟练掌握它的用法、底层原理与迭代器失效问题，不仅能写出更高效、稳定的代码，也是进阶 STL 与面试的必备基础。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
20
0- 0
已为社区贡献3条内容
所有评论(0)