C++ vector 添加与删除元素的底层原理：erase 返回值与倒序遍历删除

一、先理解 vector 的内存模型

std::vector 是 C++ 标准库中最常用的动态数组容器。它的本质是一块连续的堆内存，内部通常维护三个指针（不同实现命名略有差异，libstdc++ 中为 _M_start、_M_finish、_M_end_of_storage）：

• begin：指向已使用内存的起始位置。
• end：指向最后一个有效元素的下一个位置，size() = end – begin。
• capacity_end：指向已分配内存的末尾，capacity() = capacity_end – begin。

正因为内存连续，vector 支持 O(1) 的随机访问，但也意味着一旦容量不足，就必须重新分配整块内存并搬迁所有元素。这是理解所有添加、删除操作性能差异的关键。

// 简化后的内存布局示意
// [ begin ][ ][ ][ ][ end ][ 空闲 ][ 空闲 ][ capacity_end ]
// ↑ 已构造元素 ↑ ↑ 未使用但已分配 ↑

二、添加元素的底层原理

2.1 push_back：尾部追加

push_back 是最常用的添加方式，其内部逻辑可以概括为两步：

#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
std::cout << "初始 capacity: " << v.capacity() << "\\n";
for (int i = 0; i &lt; 10; ++i) {
v.push_back(i);
std::cout &lt;&lt; "size=" &lt;&lt; v.size()
&lt;&lt; " capacity=" &lt;&lt; v.capacity() &lt;&lt; "\\n";
}
return 0;
}

在 libstdc++ 中，扩容策略是按 2 倍增长（size() + max(size(), 1)），MSVC 的 STL 则约为 1.5 倍。无论哪种策略，都保证了 push_back 的均摊时间复杂度为 O(1)：虽然单次扩容是 O(n)，但扩容次数是对数级的，总代价被均摊到每次插入上。

2.2 扩容为什么是 2 倍或 1.5 倍

如果每次只扩容固定大小（比如 +1），那么 n 次插入的总拷贝次数是 O(n²)。而按倍数增长时，第 k 次扩容拷贝的元素数量构成等比数列，总和为 O(n)，因此均摊 O(1)。

选择 1.5 倍还是 2 倍是一个工程权衡：2 倍增长更快，但更容易造成内存碎片和浪费；1.5 倍增长后，之前释放的内存块有机会被后续分配复用。

2.3 emplace_back：原地构造

emplace_back 与 push_back 的扩容逻辑完全一致，区别在于它直接在容器内存上构造对象，省去了一次临时对象的构造与移动：

#include <vector>
#include <string>
struct Person {
std::string name;
int age;
Person(std::string n, int a) : name(std::move(n)), age(a) {}
};
int main() {
std::vector<Person> people;
people.push_back(Person("Alice", 20)); // 构造临时对象 + 移动
people.emplace_back("Bob", 25); // 直接原地构造，更高效
return 0;
}

2.4 insert：中间插入

在中间位置插入元素时，vector 必须把插入点之后的所有元素整体向后移动一位，然后在新位置构造元素。移动使用 std::move_backward 完成，对于可移动类型效率较高，但时间复杂度仍是 O(n)。

#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
// 在下标 2 处插入 99，元素 3、4、5 需要整体后移
v.insert(v.begin() + 2, 99);
// 结果：1 2 99 3 4 5
return 0;
}

如果插入导致容量不足，还会先触发一次扩容，此时所有元素都要搬迁，代价更高。因此频繁在中间插入应优先考虑 std::list 或 std::deque。

三、删除元素的底层原理

3.1 pop_back：尾部删除

pop_back 是最轻量的删除操作：它只需对最后一个元素调用析构函数，然后 –end，不释放内存，也不改变 capacity，时间复杂度 O(1)。

#include <vector>
#include <iostream>
int main() {
std::vector<int> v{1, 2, 3};
std::cout << "capacity before: " << v.capacity() << "\\n";
v.pop_back();
std::cout << "size: " << v.size()
<< " capacity after: " << v.capacity() << "\\n";
return 0;
}

注意：pop_back 不会缩容，这是为了避免频繁的重新分配。如果确实需要释放多余内存，可以使用 shrink_to_fit()（非强制）或「swap 技巧」。

3.2 erase：中间删除

erase 删除中间元素时，会把被删元素之后的所有元素整体向前移动一位，覆盖掉被删除的位置，然后对末尾多余的元素调用析构并 –end。时间复杂度 O(n)。

#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
// 删除下标 1 处的元素 2，后面的 3、4、5 依次前移
v.erase(v.begin() + 1);
// 结果：1 3 4 5
return 0;
}

删除区间 erase(first, last) 的原理相同，只是把 [last, end) 的元素整体前移到 first 开始的位置，移动距离为 end – last。

3.3 erase-remove 惯用法

由于 erase 每次只能删除一个元素，循环删除满足条件的元素会导致 O(n²) 的复杂度。标准做法是先用 std::remove / std::remove_if 把要保留的元素前移，再一次性 erase 尾部无效区间：

#include <vector>
#include <algorithm>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
// 删除所有偶数
v.erase(std::remove_if(v.begin(), v.end(),
[](int x) { return x % 2 == 0; }),
v.end());
// 结果：1 3 5
return 0;
}

这种写法只做一次线性扫描和一次尾部截断，整体复杂度 O(n)。C++20 起还可以直接使用 std::erase_if(v, pred)。

3.4 clear 与缩容

clear() 会对所有元素调用析构函数并把 end 重置为 begin，但不释放已分配的内存，capacity 保持不变。若想真正释放内存，常用做法是：

#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
// swap 技巧：与临时空 vector 交换，原内存随临时对象析构而释放
std::vector<int>().swap(v);
// 此时 v 的 size 和 capacity 都为 0
return 0;
}

四、erase 的返回值是什么

这是很多人在写循环删除时容易忽略的细节。erase 有两个重载，返回值类型都是 iterator：

• iterator erase(const_iterator pos)：返回被删除元素的下一个元素的迭代器。如果删除的是最后一个元素，则返回 end()。
• iterator erase(const_iterator first, const_iterator last)：删除区间 [first, last)，返回区间之后第一个元素的迭代器；如果 last == end()，则返回 end()。

之所以要返回迭代器，是因为删除操作会让被删位置及其之后的迭代器全部失效，调用方必须用返回值重新获得一个有效迭代器，才能继续遍历。这也是「it = v.erase(it)」这种写法的由来：

#include <vector>
#include <iostream>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
// 正确写法：用 erase 的返回值更新迭代器，不额外 ++it
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) {
it = v.erase(it); // 返回下一个元素的位置
} else {
++it;
}
}
for (int x : v) std::cout &lt;&lt; x &lt;&lt; " "; // 1 3 5
return 0;
}

常见错误是写成 v.erase(it); ++it;：erase 之后 it 已经失效，再自增属于未定义行为，可能崩溃也可能跳过元素。另外要注意，erase 的返回值在 C++11 之前是 void，C++11 起才统一为返回迭代器。

五、删除所有指定元素，为什么建议从后往前遍历

如果不用 erase-remove 惯用法，而是自己写循环逐个删除，那么从后往前遍历是更稳妥的写法。原因主要有三点：

5.1 避免下标错位导致漏删

erase 会把后面的元素整体前移一位。如果从前往后按下标遍历，删除下标 i 的元素后，原本下标 i+1 的元素会移动到 i，而循环又执行了 ++i，这个元素就被跳过了。

#include <vector>
#include <iostream>
int main() {
std::vector<int> v{1, 2, 2, 3, 2, 4};
// 错误示范：从前往后删除，会漏删相邻的重复元素
for (size_t i = 0; i &lt; v.size(); ++i) {
if (v[i] == 2) {
v.erase(v.begin() + i);
// 此处 i 已经指向了下一个元素，再 ++i 就跳过了它
}
}
// 结果可能是 1 2 3 4，仍残留一个 2
return 0;
}

5.2 从后往前遍历不受前移影响

倒序遍历时，删除下标 i 的元素只会影响 i 之后的元素，而这些元素已经处理过了，因此不会漏删，也不需要修正下标：

#include <vector>
#include <iostream>
int main() {
std::vector<int> v{1, 2, 2, 3, 2, 4};
// 正确写法：从后往前删除，逻辑简单且不会漏删
for (int i = static_cast&lt;int&gt;(v.size()) – 1; i &gt;= 0; –i) {
if (v[i] == 2) {
v.erase(v.begin() + i);
}
}
for (int x : v) std::cout &lt;&lt; x &lt;&lt; " "; // 1 3 4
return 0;
}

5.3 迭代器失效风险更小

用迭代器删除时，erase 会使删除点及之后的迭代器失效。倒序遍历时，被删除位置之后的迭代器虽然失效，但那些位置已经访问完毕，不会再被使用；而正向遍历必须依赖 it = v.erase(it) 才能保证安全。倒序写法把「失效」的影响范围限制在已经处理过的区域，心智负担更低。

不过要强调：倒序遍历只是「手写循环删除」时的一种稳妥写法，并不是最优解。真正高效的做法仍是 erase-remove 惯用法或 C++20 的 std::erase_if，它们只做一次线性扫描，复杂度 O(n)；而逐个 erase 即使倒序，每次删除仍要移动后续元素，最坏情况仍是 O(n²)。

六、关键结论与性能对照

总结起来，vector 的设计哲学是用连续内存换取随机访问性能：尾部增删极快，中间增删代价高，扩容是隐藏的成本。实际开发中，如果能预估元素数量，提前调用 reserve() 可以避免多次扩容；频繁中间插入删除的场景则应考虑其他容器。

#include <vector>
int main() {
std::vector<int> v;
v.reserve(1000); // 一次性分配足够容量，避免后续扩容
for (int i = 0; i < 1000; ++i) {
v.push_back(i); // 全程不会触发 reallocation
}
return 0;
}