vector 的基本使用（大小、容量和位置）的详细阐述（上）

文章目录

• • 一、从 C 数组出发
  • • 1.1 需要管理的，不只是那一段内存
    • 1.2 连续存储很好用，但也有代价
  • 二、创建 vector：参数决定得到什么元素
  • • 2.1 常见构造方式
  • 三、访问和遍历：值、引用与位置
  • • 3.1 访问已有元素，先判断是否存在
    • 3.2 为什么区间通常是左闭右开
    • 3.3 三种遍历方式
  • 四、大小与容量：reserve 与 resize
  • • 4.1 区分两个问题
    • 4.2 容量测试：观察规则，而不是记住一次输出
    • 4.3 最常见的错误：把预留空间当作元素
  • 五、增删查改：先说清位置，再选择操作
  • • 5.1 用一个序列跟踪插入和删除
    • 5.2 移动方向决定元素会不会被覆盖
    • 5.3 查找不是成员函数
  • 六、迭代器失效
  • • 6.1 失效不只发生在释放内存后
    • 6.2 规则表帮助理解，避免只背函数名称
    • 6.3 删除连续偶数，为什么不能删除后再递增
  • 七、二维 vector：每一行独立管理自己的元素
  • • 7.1 `vector` 模拟二维数组
    • 7.2 不要盲目套用 C 二维数组的整体布局
  • 八、练习：从接口到解决问题
  • • 8.1 LeetCode 27「移除元素」
    • 8.2 LeetCode 26「删除有序数组中的重复项」
  • 九、小结

代码仓库: 《vector测试与模拟实现》

一、从 C 数组出发

1.1 需要管理的，不只是那一段内存

在 C 中，如果最多有 100 个成绩，可以写 int scores[100]，再单独记录实际读入了几个。那么这里就已经有两个数量：数组能容纳的数量和目前使用的数量。当数据量超过 100 时，要么拒绝输入，要么重新申请空间、搬移旧数据，并处理旧空间的释放。

std::vector 是 C++ 库提供的顺序容器，可以把它理解为维护一段连续元素序列的动态数组对象。它会自动记录元素数量，在需要时可及时调整存储，并在自身销毁时销毁元素、释放管理的存储。

使用时包含 <vector>，在定义时显式写出元素的类型，如 std::vector<int>、std::vector<double> 等。

std::vector<int> scores;
scores.push_back(80);
scores.push_back(95);
scores[0] = 85;

执行过程：

• 第一次尾插时创建第一个元素；
• 第二次尾插创建第二个元素，必要时先扩容；
• 下标赋值只修改已有元素，不会把序列再增长一格。
• 离开作用域后对象自动清理，不需要也不允许手动 delete[] scores.data()。

1.2 连续存储很好用，但也有代价

对于定义时使用的普通元素类型，元素连续排列，所以按下标访问很快，也便于遍历。

但连续存储的另一面是：中间插入、删除时，后面的元素通常要搬移；扩容时，元素可能全部转移到另一块存储。

图中 size() == 3、capacity( )== 6指的是：只有前三个是容器中的元素，后三个不是可以下标访问的元素。有效下标始终是 [0, size())，不是 [0, capacity())。

其中sizeof(v) 得到的是 vector 对象本身的大小，并不是动态存储大小。使用v.size() * sizeof(int) 可以估算 int 元素的数据字节数，但不包含预留空间和管理开销。

二、创建 vector：参数决定得到什么元素

2.1 常见构造方式

#include <iostream>
#include <vector>

int main()
{
//不同方式初始化
std::vector<int> n1;
std::vector<int> n2(10, 1);
std::vector<int> n3(n2.begin(), n2.end());
//输出此时n1的元素个数以及是否为空（布尔值以0/1值展示）
std::cout << n1.size() << ' ' << n1.empty() << std::endl;
//打印此时n3元素
for (size_t i = 0; i < n3.size(); ++i)
std::cout << n3[i] << ' ';
std::cout << std::endl;

int a[] = {3, 4, 5};
//数组区间初始化
std::vector<int> from_array(a, a + 3);
for (int e : from_array)
std::cout << e << ' ';
std::cout << std::endl;

std::vector<int> parentheses(5, 2);
std::vector<int> braces{5, 2};
std::cout << parentheses.size() << ' ' << braces.size() << std::endl;
std::vector<int> copy = n2;
copy[0] = 9;
std::cout << copy[0] << ' ' << n2[0] << std::endl;
}

运行示例：

• 第一行中的 1 表示 empty() 为真。
• 第三行只包含数组的三个元素，因为 a + 3 是尾后位置。
• 最后一行说明改变 copy 不影响 n2；复制的是元素值，而不是让两个 vector 共用同一组 int 元素。

三、访问和遍历：值、引用与位置

3.1 访问已有元素，先判断是否存在

• v[i] = 7 会修改容器中的元素，因为 [] 返回的是元素的引用。
• 空容器调用 front()、back()、pop_back() 都会违反前提；
• v[v.size()] 也是越界行为。VS的Debug 模式下编译运行会检查出错误。

3.2 为什么区间通常是左闭右开

begin() 表示第一个元素的位置，end() 表示最后一个元素之后的位置。 两者相等时区间为空，这恰好可以让同一段循环处理空和非空容器：

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

先判断 it != end()，再解引用。end() 用来标记边界，不指向可读取的元素。同时，vector 的迭代器支持 +n、-n、同一容器有效迭代器之间求差，但需注意移动后仍不能越过合法区间。

rbegin() 从最后一个元素开始，rend() 是反向遍历的结束标记。

3.3 三种遍历方式

#include <iostream>
#include <vector>

int main()
{
std::vector<int> v{1, 2, 3};
//普通循环遍历
for (size_t i = 0; i < v.size(); ++i)
std::cout << v[i] << ' ';
std::cout << std::endl;

//范围for循环
for (auto& e : v)
e *= 2;
for (const auto& e : v)
std::cout << e << ' ';
std::cout << std::endl;

//迭代器循环
std::vector<int>::iterator it = v.begin();
while (it != v.end())
{
std::cout << *it << ' ';
++it;
}
std::cout << std::endl;
return 0;
}

运行示例：

• 下标循环适合需要位置编号的问题；
• 迭代器适合与查找、插入、删除衔接；
• 范围 for 适合逐个处理元素。

auto 只帮助推导类型，不自动引入引用，要修改原元素必须明确写 &。

还有两个“const”不能混淆：

• const_iterator 不能通过它修改元素，但自身可以递增；
• const auto it = v.begin() 固定的是迭代器变量，不能递增，而它若仍是普通 iterator，通常依然可以通过 *it 修改元素。需要只读位置时，可以使用 v.cbegin()、v.cend()。

四、大小与容量：reserve 与 resize

4.1 区分两个问题

size() 回答“现在有多少个元素”；capacity() 回答“在不重新分配存储的情况下，最多能容纳多少个元素”。所以始终有 size() <= capacity()，容量不是单独可访问的元素范围。

4.2 容量测试：观察规则，而不是记住一次输出

#include <iostream>
#include <vector>

int main()
{
std::vector<int> v(10, 1);
// size：有效元素个数；capacity：容器总容量；此时size = 10，容量至少为10
std::cout << v.size() << ' ' << (v.capacity() >= 10) << std::endl;
// reserve(n)：预分配内存，只改capacity，不改变size，容量至少20，会发生内存重新分配
v.reserve(20);
std::cout << v.size() << ' ' << (v.capacity() >= 20) << std::endl;

// 保存当前容量，以及底层数组首地址
const size_t saved_capacity = v.capacity();
const int* saved_data = v.data();
v.reserve(10);
// 容量不变，等于之前保存的容量
std::cout << (v.capacity() == saved_capacity) << std::endl;
// 底层内存地址不变，不会触发重新分配
std::cout << (v.data() == saved_data) << std::endl;

// reserve再次传入更小的值5，依旧不会缩减容量，容量维持不变
v.reserve(5);
std::cout << (v.capacity() == saved_capacity) << std::endl;

// size扩大到15，新增的5个元素初始化为2；capacity不会主动缩小，保持原有容量
v.resize(15, 2);
std::cout << v.size() << ' ' << v.back() << std::endl;
// resize缩小size到5：只销毁后面元素，不会释放内存，capacity保持不变
v.resize(5);
std::cout << v.size() << ' ' << (v.capacity() == saved_capacity) << std::endl;

std::vector<int> zeros(3);
// clear()：销毁全部元素，size置0；不释放内存，capacity保持不变
v.clear();
std::cout << v.size() << ' ' << (v.capacity() == saved_capacity) << std::endl;
// shrink_to_fit()：请求把capacity缩减到等于size(此时size为0)，释放多余内存；
v.shrink_to_fit();
std::cout << v.size() << ' ' << v.empty() << std::endl;
return 0;
}

运行示例：

• 测试保留原测试中的 reserve(20)、reserve(10)、reserve(5) 顺序，不把某次 capacity 的精确数值当成规则。
• 较小的 reserve 不缩容，也不重分配，因此这里比较保存的有效指针是安全的。
• resize(15,2) 后，原十个 1 保留，新增五个元素是 2；
• resize(5) 后只剩前五个 1。
• clear() 清空元素但保留容量。

4.3 最常见的错误：把预留空间当作元素

std::vector<int> v;
v.reserve(10);
v[0] = 5; // size 仍为 0，违反下标访问前提。

• 如果你准备逐个追加，就在 reserve(10) 后调用 push_back；
• 如果准备马上按下标填写十个位置，就先 resize(10) 或使用数量构造。

五、增删查改：先说清位置，再选择操作

5.1 用一个序列跟踪插入和删除

#include <iostream>
#include <vector>

int main()
{
//初始化4个1
std::vector<int> v(4, 1); //1 1 1 1
//尾插入2
v.push_back(2); //1 1 1 1 2
//开始位置插入0
v.insert(v.begin(), 0); //0 1 1 1 1 2
//开始位置再加三个位置插入3
v.insert(v.begin() + 3, 3); //0 1 1 3 1 1 2
for (int e : v)
std::cout << e << ' ';
std::cout << std::endl << v.front() << ' ' << v.back() << std::endl;

//删除尾部元素
v.pop_back(); //0 1 1 1 3 1
//删除开头元素
v.erase(v.begin()); //1 1 1 3 1
//删除开始位置加一个位置至三个位置的元素（左闭右开）
v.erase(v.begin() + 1, v.begin() + 3); //1 1 1
//重新为数组分配3个元素7
v.assign(3, 7);
for (int e : v)
std::cout << e << ' ';
std::cout << std::endl;
return 0;
}

运行示例：

• insert(pos,x) 是在 pos 之前插入，返回新插入元素的位置。

• insert(end(),x) 合法，相当于尾插；它并没有解引用旧 end。

• pop_back() 移除尾元素，不返回被删的值。若需要被删元素的值，先在非空条件下读取 back()，再调用 pop_back()。

• erase(pos) 移除一个元素，pos 必须指向实际元素，不能是 end()。

• erase(first,last) 移除左闭右开的区间，空区间合法；

• erase(end(),end()) 什么也不删。

• assign(3,7) 替换整个序列，不是尾部追加三个 7；

5.2 移动方向决定元素会不会被覆盖

在进行插入或删除时，通常都需要挪动其它元素的位置来保证其连续，所以此时数据该如何挪动不会造成数据丢失且正确就显得尤为重要。

在 [1,2,3] 的中间插入 9，需要先把 3 向后移动，再把 2 移动，最后写入 9。如果从前向后直接搬移，原来的后续值会被覆盖。删除时则反过来：先用后一个元素补当前空位，继续向前补齐。

这也间接解释了为什么 vector 没有设计 push_front()，当然，头部插入也可以使用 insert(begin(),x) 来实现，但这时所有原元素都要后移，效率就会大幅降低。

swap 交换是交换两个普通 vector 管理的内容，不需要逐个交换其中的元素。

5.3 查找不是成员函数

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
std::vector<int> v{4, 1, 3, 2};
//查找3这个元素在数组中的位置，找到则返回迭代器
auto pos = std::find(v.begin(), v.end(), 3);
if (pos != v.end())
std::cout << *pos << std::endl;
//查找8这个元素在数组中的位置，没找到返回end()位置
auto missing = std::find(v.begin(), v.end(), 8);
std::cout << (missing == v.end()) << std::endl;
return 0;
}

运行示例：

输出依次为找到的 3、未找到的判断 1。

find 返回位置，查找失败返回传入区间的 last；判断失败后不能解引用。 当要删除查到的值时，需先判断再执行 erase(pos)。

六、迭代器失效

6.1 失效不只发生在释放内存后

扩容导致重分配时，元素迁入新存储，指向旧元素的迭代器、指针和引用全部失效。这种情况相对容易理解。

但即使没有重分配，中间插入和删除也会影响位置的有效性。标准规定 erase 删除位置及其后的迭代器、引用失效，其中包括原来的 end。

6.2 规则表帮助理解，避免只背函数名称

以下针对普通 vector 元素类型；操作成功完成后判断:

6.3 删除连续偶数，为什么不能删除后再递增

#include <iostream>
#include <vector>

int main()
{
std::vector<int> v{1, 2, 3, 4, 4, 5, 6};
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
++it;
}
for (int e : v)
std::cout << e << ' ';
std::cout << std::endl;
return 0;
}

运行示例：

• 删除第一个 4 后，第二个 4 补到当前位置。
• erase 返回它的新位置，下一轮应该马上检查它，而不是再递增跳过去。
• 删除最后的 6 时，返回新 end，循环自然结束。

错误写法：

if (*it % 2 == 0)
{
v.erase(it);
}
++it;

这种同时有两个问题：使用失效迭代器，并可能跳过补到当前位置的元素。这就导致当碰到连续的偶数时，删除第一个偶数后可能会跳过第二个偶数进而继续从下一个元素开始，最终导致偶数没有删除干净。

七、二维 vector：每一行独立管理自己的元素

7.1 vector 模拟二维数组

std::vector<std::vector<int>> 的外层元素类型是 std::vector<int>。matrix.size() 是行数，matrix[i].size() 才是第 i 行的列数。matrix[i][j] 先取得第 i 行，再取得这一行的第 j 个元素。

#include <iostream>
#include <vector>

int main()
{
//二层vector模拟二维数组
std::vector<int> row(5, 1);
std::vector<std::vector<int>> matrix(3, row);
matrix[1][2] = 2;
matrix[2][4] = 3;
//与C语言的二维数组遍历方式类似
for (size_t i = 0; i < matrix.size(); ++i)
{
for (size_t j = 0; j < matrix[i].size(); ++j)
std::cout << matrix[i][j] << ' ';
std::cout << std::endl;
}
//直接定义双层vector
std::vector<std::vector<int>> uneven{{1, 2, 3}, {4}, {5, 6}};
for (auto& current : uneven)
{
for (int e : current)
std::cout << e << ' ';
std::cout << std::endl;
}
return 0;
}

运行示例：

• 前三行输出五列，其中第二行第 3 个元素为 2、第三行第 5 个元素为 3；
• 随后输出三行不同长度的序列。

7.2 不要盲目套用 C 二维数组的整体布局

• 外层连续的是“行对象”，每一行内部连续的是自己的 int 元素。
• 不同的行不保证紧挨在同一块整数存储中，因此不能把 matrix[0].data() 当作整个矩阵的首地址，也不能将它当成 int** 传给任意 C 接口。

std::vector<std::vector<int>> matrix(3); 只创建三个空的行对象，不会自动创建每行的列。先 matrix[i].resize(cols)，再访问列元素。

八、练习：从接口到解决问题

8.1 LeetCode 27「移除元素」

LeetCode 27「移除元素」 移除所有等于 value 的元素，将保留值写到前面，返回有效前缀长度 k；题目不要求真的缩小容器。

思路： read 扫描原元素，write 指向下一个保留值应写入的位置。write 始终不超过 read，所以不会覆盖还没读过的元素。

参考答案：

size_t remove_value(std::vector<int>& nums, int value)
{
size_t write = 0;
for (size_t read = 0; read < nums.size(); ++read)
{
if (nums[read] != value)
{
nums[write] = nums[read];
++write;
}
}
return write;
}

[3,2,2,3] 移除 3 后返回 2，前两个元素为 [2,2]，后面无需关心。算法 O(n) 时间、O(1) 额外空间。

8.2 LeetCode 26「删除有序数组中的重复项」

LeetCode 26「删除有序数组中的重复项」 保留每个值一次，返回有效前缀长度。

思路： 有序使相同值相邻。非空时第一个值已经保留，write 从 1 开始；新值与最后一个保留值不同才写入。 参考答案：

size_t unique_sorted(std::vector<int>& nums)
{
if (nums.empty())
return 0;
size_t write = 1;
for (size_t read = 1; read < nums.size(); ++read)
{
if (nums[read] != nums[write – 1])
{
nums[write] = nums[read];
++write;
}
}
return write;
}

例如 [0,0,1,1,1,2] 返回 3，前缀为 [0,1,2]；时间 O(n)，额外空间 O(1)。

九、小结

学习 vector 时，比背下所有重载更有用的是先回答三个问题：这次操作改变 size 吗？可能改变存储吗？原来保存的位置还有效吗？ ，这样接口记忆就能落到实际决策上。

vector标准库参考