1. 顺序表删除的代价账：先把内存布局算明白

顺序表（sequential list）在课本里的定义是"用一组地址连续的存储单元依次存放线性表的数据元素"，翻成人话就是：底层是个数组，逻辑上挨着的元素，在内存里也挨着。C++ 里我们平时最常用的顺序表实现就是std::vector，它在堆上维护一块连续内存，size()告诉你当前装了几个元素，capacity()告诉你这块内存最多能装几个。

"连续"这两个字是顺序表所有优点的来源，也是它所有缺点的来源。查找快，因为v[i]直接算地址首地址 + i * sizeof(T)，一次访存就够；但删除麻烦，因为在中间挖掉一个元素之后，后面所有元素都得整体往前挪一格，否则连续性就断了。

所以"删除顺序表中指定值的所有元素（C++，vector）"这个题目，本质上考的不是你会不会写erase，而是三件事：

• 你是否清楚一次erase到底动了多少次内存；
• 你是否知道在循环里连续删元素时，迭代器/下标会失效或者跳元素；
• 你是否能在"保序"和"不保序"之间做出正确的工程取舍。

很多同学第一次做这题，写出来是这样的：

for (int i = 0; i < v.size(); i++) { if (v[i] == val) v.erase(v.begin() + i); }

代码能编译，小数据也能跑出个看起来对的结果，但它是错的——删掉一个元素后，后面的元素整体前移一位，而i照样自增，于是紧跟在被删元素后面的那个元素被跳过了。如果输入是{1, 2, 2, 3}要删2，这份代码会留下一个2。这就是最经典的"漏删"。

1.1 一次 erase 的真实移动次数

假设顺序表长度是 n，你要删掉下标为 i 的元素。std::vector::erase的内部动作分三步：先把[i+1, n)这段元素整体左移一位，然后把最后一个位置的元素析构掉，最后把 size 减一。左移用的是std::move或者拷贝赋值，元素个数是n - i - 1。

所以：

• 删第一个元素，移动n - 1次；
• 删最后一个元素，移动 0 次；
• 如果是随机位置删除，平均移动(n-1)/2次。

这也是课本上那个结论的来历：顺序表插入和删除的平均时间复杂度都是 O(n)，因为移动是绕不过去的。

1.2 为什么"删除所有指定值"比"删除一个"更值得单独练

删一个元素，你只要写对一次erase就完了。删所有指定值，麻烦的地方在于"删"这个动作会改变容器的形态，而你正在遍历它。遍历依赖的结构（迭代器、下标）在删除的一瞬间就可能失效，于是你要么学会"删完之后重新定位"，要么换一种根本不在遍历中删除的写法。

这两条路对应了后面要讲的两种主流解法：迭代器安全推进（循环里erase，但用返回值接住新迭代器）和快慢指针原地覆盖（先整体搬运，最后一次性收缩）。前者直观，后者性能最好，也是考研/笔试卷面上更受青睐的写法，因为它在纯数组上同样成立——毕竟顺序表不只有vector一种实现，考场上给你的可能就是一个int a[]加一个int n。

顺带提一句，顺序表这类结构的基础操作在题库里非常密集，像洛谷上那些"询问学号"之类的入门题，练的就是按下标随机访问；而"删除指定值"练的是移动和边界控制。两者合起来，才算把顺序表的读写两面都摸过一遍。

2. 三个高频翻车点：迭代器失效、下标跳元素、误以为 remove 会删除

我见过太多人在这一题上卡住，卡的位置高度集中。把这三个点讲透，比背十份代码有用。

2.1 坑一：erase 之后，原来的迭代器就是"野指针"

std::vector的erase会让被删位置及其之后的所有迭代器失效。原因很直白：元素整体前移了，原来it指向的那块地址上现在装的可能是别的值，也可能已经越过了end()。

所以这种写法必须判死刑：

for (auto it = v.begin(); it != v.end(); ++it) { if (*it == val) v.erase(it); // it 立刻失效，下一轮 ++it 是未定义行为 }

在 Debug 版的 MSVC 或 libstdc++ 上，你大概率能看到一个断言崩溃；在 Release 下它可能"安静地"跑完并给出错误结果，也可能直接段错误。这种"有时对有时错"的 bug 最难查，因为它和内存布局、编译器优化等级都有关。

正确的姿势是利用erase的返回值——它返回被删元素之后那个元素的新位置：

for (auto it = v.begin(); it != v.end(); ) { if (*it == val) it = v.erase(it); // 接住新位置，不额外自增 else ++it; // 没删才往前走 }

这段代码的精髓在于for的第三段是空的，自增动作拆进了循环体里，删和不删走不同的分支。

2.2 坑二：下标删除少写一个 i--

如果你坚持用下标，那正确的写法是二选一：

// 方案一：删除后不自增 for (size_t i = 0; i < v.size(); ) { if (v[i] == val) v.erase(v.begin() + i); else ++i; } // 方案二：删除后回退一步 for (int i = 0; i < (int)v.size(); ++i) { if (v[i] == val) { v.erase(v.begin() + i); --i; } }

方案二里那个--i是很多人漏掉的一步，漏了就漏删。注意方案二里我写了(int)v.size()这个强制转换，这不是多此一举：v.size()返回的是size_t（无符号），拿它和int i比较时，i会被隐式转成无符号数，一旦i被减到-1，比较结果会瞬间变成"真"，循环直接失控甚至越界访问。这个坑在删除场景里特别容易触发，因为删除恰恰是唯一会让下标倒退的操作。

方案一更干净，我个人更推荐，因为它不依赖int和size_t的隐式转换规则。但要注意，方案一每次erase都是 O(n) 的移动，整个循环最坏是 O(n²)——数据量到 10^5 就会明显超时。

2.3 坑三：以为 std::remove 真的把元素"移除"了

这是最反直觉的一个。<algorithm>里的std::remove名字叫 remove，但它不改变容器大小，一个元素都不会析构。它干的事情是：把不等于val的元素依次搬到前面，返回一个迭代器指向"新的逻辑结尾"。后面那段"垃圾数据"还在内存里躺着，只是你不再关心它了。

画个图理解。容器是{1, 2, 2, 3}，要删2：

所以标准写法必须两步走，这就是著名的erase-remove 惯用法：

v.erase(std::remove(v.begin(), v.end(), val), v.end());

std::remove负责"搬"，erase负责"缩"。少了后面那半句，你的v.size()根本不会变，OJ 上直接判错。

理解了这个机制，你也就理解了为什么它的复杂度是 O(n)：remove做的是恰好n次比较和最多n次移动，erase删的是尾部区间，压根不需要移动任何元素，只做析构。整条链路没有 O(n²) 的影子。

3. 四种能一次跑通的写法，以及该怎么选

把可用的方案摆在一起比较，选型才有依据。下面四种写法都能正确删除所有等于val的元素，差别在可读性、常数项和适用场景。

3.1 写法一：erase-remove 惯用法，日常首选

#include <algorithm> void removeAll(std::vector<int>& v, int val) { v.erase(std::remove(v.begin(), v.end(), val), v.end()); }

代码量最小，语义最清晰，编译器对它还有额外优化空间。缺点只有一个：它的删除条件必须是"等于某个值"，如果你想删"所有偶数"或者"所有分数小于 60 的"，得换成std::remove_if。

另外提醒一句，C++20 之后标准库给了更省事的封装，定义在<vector>里：

std::erase(v, val); // 删值 std::erase_if(v, [](int x){ return x % 2 == 0; }); // 删条件

这两行是实打实的成员封装，一行搞定。但如果你的编译器还在 C++11/14 或者 OJ 用老标准，就别指望它，写惯用法更稳。

3.2 写法二：快慢指针原地覆盖，性能与笔试的最优解

void removeAll(std::vector<int>& v, int val) { size_t slow = 0; for (size_t fast = 0; fast < v.size(); ++fast) { if (v[fast] != val) { v[slow++] = v[fast]; } } v.resize(slow); }

思路一句话：fast负责扫描全部元素，slow负责指向"下一个该写入的位置"。凡是保留下来的元素，就地往前搬。扫描结束时，slow就是新长度，resize一次性砍掉尾部。

这个写法的好处很实在：

• 每个元素最多被搬运一次，总共 n 次比较 + 最多 n 次赋值，没有 O(n²) 风险；
• 不依赖任何容器接口，换成裸数组照样能用，v.size()换成n，resize换成返回新长度即可；
• slow <= fast恒成立，写入位置永远不越过读取位置，不存在覆盖未读数据的问题。

最后一点值得多说两句，因为它是这个算法正确性的根基。因为slow只在"保留"时才前进，而fast每轮都前进，所以slow增长得永远不会比fast快。写入v[slow] = v[fast]时，被覆盖的位置要么是slow == fast（自己写自己，无副作用），要么是slow < fast（那一格的数据早就被读过并且判定为要删的元素），所以不会误伤还没读到的数据。

resize这一步不能省。如果你只是把slow当时新长度、然后循环里用slow当上界，那是"逻辑上删了，物理上没删"。在要求"返回新长度"的题目里这就够了，但在真实工程里，容器尾巴上挂着一堆已经不该存在的对象，既浪费内存，又可能让后续的size()判断出错。

3.3 写法三：remove_if 加谓词，多条件删除靠它

条件一复杂，std::remove就力不从心了，比如"删除所有小于 60 的分数"：

v.erase(std::remove_if(v.begin(), v.end(), [](int score) { return score < 60; }), v.end());

remove_if和remove的机制完全一样，只是把"是否等于 val"换成了"谓词是否为真"。谓词写成 lambda，捕获外部变量也没问题：

int threshold = 60; v.erase(std::remove_if(v.begin(), v.end(), [threshold](int s) { return s < threshold; }), v.end());

注意我用的是值捕获[threshold]而不是引用捕获[&]。在这种一次性的短谓词里，值捕获更安全，不会因为外部变量生命周期出问题而变成悬垂引用。

3.4 写法四：不保序的交换删除，删除比例很小时最快

如果题目不要求保留剩余元素的相对顺序，还有一个更"暴力"的思路：发现v[i] == val，就把末尾元素换到 i 位置，然后pop_back，并且i不自增（因为换过来的新元素还没检查）。

void removeAllUnordered(std::vector<int>& v, int val) { size_t i = 0; while (i < v.size()) { if (v[i] == val) { v[i] = v.back(); v.pop_back(); } else { ++i; } } }

代价分析：每一次删除只做一次赋值加一次pop_back，总共的搬运次数等于被删元素的个数 k，而不是 n。所以在"删得很少"的场景下（比如从十万条记录里删三条），它比快慢指针还快一个量级。

但它的顺序被打乱了，用之前必须确认业务允许。这一点很多人不假思索就用了，结果在需要稳定输出的场景里翻了车。

把它和前面的方案放在一起对比：

数据规模只要上到 10^5 这个量级，第五行那两种 O(n²) 的写法就该直接淘汰。

4. 手写一份能编译能验证的完整代码

光看不写记不住。下面这份代码把前面几种写法都串起来，并且在同样的输入上互相校验结果，你复制到本地就能跑。

4.1 编译环境与命令

用任何支持 C++11 的标准环境都行，g++ 直接编：

g++ -std=c++11 -Wall -Wextra -O2 remove_all.cpp -o remove_all ./remove_all

-Wall -Wextra这两个警告开关建议常开。在有符号无符号比较这类坑上，编译器其实早就想提醒你了，只是默认不说。

4.2 完整代码

#include <algorithm> #include <iostream> #include <vector> // 写法 A：erase-remove 惯用法 void removeAllA(std::vector<int>& v, int val) { v.erase(std::remove(v.begin(), v.end(), val), v.end()); } // 写法 B：快慢指针原地覆盖 void removeAllB(std::vector<int>& v, int val) { std::size_t slow = 0; for (std::size_t fast = 0; fast < v.size(); ++fast) { if (v[fast] != val) v[slow++] = v[fast]; } v.resize(slow); } // 写法 C：迭代器 + erase，注意用返回值推进 void removeAllC(std::vector<int>& v, int val) { for (auto it = v.begin(); it != v.end(); ) { if (*it == val) it = v.erase(it); else ++it; } } // 写法 D：不保序的交换删除 void removeAllD(std::vector<int>& v, int val) { std::size_t i = 0; while (i < v.size()) { if (v[i] == val) { v[i] = v.back(); v.pop_back(); } else { ++i; } } } // 课本/洛谷风格：裸数组 + 返回新长度 int removeAllArray(int a[], int n, int val) { int slow = 0; for (int fast = 0; fast < n; ++fast) { if (a[fast] != val) a[slow++] = a[fast]; } return slow; } void printVec(const char* tag, const std::vector<int>& v) { std::cout << tag << " size=" << v.size() << " : "; for (int x : v) std::cout << x << ' '; std::cout << '\n'; } int main() { const std::vector<int> origin = {5, 2, 2, 7, 2, 9, 2, 2, 4}; const int target = 2; std::vector<int> a = origin, b = origin, c = origin, d = origin; removeAllA(a, target); removeAllB(b, target); removeAllC(c, target); removeAllD(d, target); printVec("A", a); printVec("B", b); printVec("C", c); printVec("D", d); // 保序的三种写法结果必须完全一致 std::cout << "A/B/C 保序结果一致: " << (a == b && b == c ? "是" : "否") << '\n'; // D 不保序，但排序后多重集应相同 std::vector<int> dSorted = d; std::sort(dSorted.begin(), dSorted.end()); std::vector<int> aSorted = a; std::sort(aSorted.begin(), aSorted.end()); std::cout << "D 与 A 元素集合相同: " << (dSorted == aSorted ? "是" : "否") << '\n'; // 裸数组版本 int arr[] = {5, 2, 2, 7, 2, 9, 2, 2, 4}; int n = static_cast<int>(sizeof(arr) / sizeof(arr[0])); int newLen = removeAllArray(arr, n, target); std::cout << "数组版新长度=" << newLen << " : "; for (int i = 0; i < newLen; ++i) std::cout << arr[i] << ' '; std::cout << '\n'; // 边界用例 std::vector<int> empty; removeAllB(empty, 1); printVec("空表", empty); std::vector<int> allBad = {3, 3, 3}; removeAllB(allBad, 3); printVec("全删", allBad); std::vector<int> noneBad = {1, 4, 5}; removeAllB(noneBad, 9); printVec("无匹配", noneBad); return 0; }

4.3 预期输出与验证思路

跑出来应该是这个样子的：

A size=4 : 5 7 9 4 B size=4 : 5 7 9 4 C size=4 : 5 7 9 4 D size=4 : 4 9 7 5 A/B/C 保序结果一致: 是 D 与 A 元素集合相同: 是 数组版新长度=4 : 5 7 9 4 空表 size=0 : 全删 size=0 : 无匹配 size=3 : 1 4 5

这份验证代码里有几个设计是有意为之的：

• 拿三种保序写法互相对拍。当你怀疑某个写法有 bug，最省时间的办法不是肉眼盯代码，而是找一个你确信正确的实现当参照物。这里 A（标准库惯用法）就是那个可信基准。
• 不保序的 D 用"排序后比较"来验证。因为vector没有重载operator==的集合语义，直接==会因为顺序不同而返回 false，先各自排序再比，等价于比较多重集。
• 三个边界用例一个不能少：空表、全部命中、全部不命中。后两个尤其关键——"全部命中"考的是你循环收缩时的边界是否正确，"全部不命中"考的是slow/fast是否同步前进而没有多搬一次。

5. 性能账要算清楚：O(n²) 和 O(n) 到底差多远

很多人知道"循环里 erase 是 O(n²)"，但没算过具体差多少。算一遍，你对复杂度的敬畏会具体很多。

5.1 移动次数的定量对比

假设 n = 100000，其中一半元素需要删除，并且这些元素均匀散布在表里。

循环 erase 的写法：第 k 次删除时，表里大约还剩n - k/2个元素，平均要搬一半，也就是约(n - k/2)/2次。把 k 从 1 累加到 50000，总量级大约是n²/8，也就是 1.25 × 10^9 次元素移动。每次移动按 1 纳秒粗算，光搬数据就要 1 秒多，实际会因为 cache 不友好更慢。

快慢指针的写法：每个保留下来元素最多被搬一次，总量不超过 5 × 10^4 次赋值。差距是四个数量级。

这就是为什么同样一道题，有人 10 毫秒 AC，有人 30 秒超时。不是机器的问题，是算法把工作量放大了上万倍。

5.2 size 和 capacity 是两本账

还有一件事必须说清楚：删除元素不会释放 vector 已经申请的容量。

std::vector<int> v(100000, 1); v.clear(); std::cout << v.size() << ' ' << v.capacity() << '\n'; // 输出 0 100000

erase和resize只改size，capacity纹丝不动。设计上这是合理的——保留容量，下次插入不用重新分配，避免了反复申请释放内存的开销。但如果你的程序是"加载一个巨大的表，删掉一部分，然后长期只留着这一小份数据"，那这几十兆的内存就一直白占着。

真要还回去，两个办法：

v.shrink_to_fit(); // C++11 起，非强制请求，实现可以不理会 std::vector<int>(v).swap(v); // 经典写法：拷贝一份紧凑的，再和原对象换

第二个写法在 C++11 之前是标准做法：std::vector<int>(v)用拷贝构造出一个容量恰好等于 size 的临时对象，swap之后临时对象接管了那块大内存，出了语句就析构释放。C++11 之后shrink_to_fit更直观，但它是"请求"不是"命令"，标准不保证一定缩容，所以在对内存极其敏感的场景，swap 那一手依然有存在的价值。

注意：shrink_to_fit可能触发一次完整的内存重分配和元素搬迁，是个 O(n) 操作。别把它塞进循环里。

5.3 什么时候"不保序"反而更划算

如果业务上剩余元素的顺序无所谓，前面说的"交换末尾 + pop_back"值得认真考虑。它的搬运成本只和删除个数 k有关，和总长度 n 无关。

举个实际例子：一个日志缓冲区里存了 50 万条记录，你只想清掉其中 20 条被标记为异常的记录。快慢指针要扫 50 万次、可能搬 50 万次；交换删除只扫到那 20 条、搬 20 次。这种场景下"保序"就是纯粹的浪费。

反过来，如果删除比例很高（比如删掉 80%），交换删除的优势就消失了，而且它还有个隐蔽缺点：末尾换过来的元素如果也是目标值，会在同一个位置反复触发删除，虽然总次数不变，但分支预测会不太友好。这种时候快慢指针一次顺序扫描反而是最舒服的。

我的经验是这么定的：顺序有语义（比如按时间排的日志、按 id 排的列表）就保序，用快慢指针或 erase-remove；顺序无语义（比如一堆待处理的 id 集合）且删除稀疏，就用交换删除。

6. 进阶场景：自定义类型、浮点数、多值删除

前面都在用int举例，真实项目里类型会复杂得多，选择题里的坑也更多。

6.1 自定义结构体：要不要给 operator==

假设你的顺序表里装的是结构体：

struct Student { int id; std::string name; int score; };

如果要用std::remove或者removeAllA这种按值比较的写法，编译器需要一条operator==。给它加上就行：

bool operator==(const Student& a, const Student& b) { return a.id == b.id; // 只按学号判定"同一个人" }

这里有个设计决策要做：相等到底按什么定义？是按全部字段都比，还是只按主键比？上面这份代码只比id，意味着"学号相同即为同一人，姓名和分数不一致也算相等"。这在做去重时通常是你想要的，但如果有人误以为它比全部字段，就会写出意料之外的删除逻辑。

另一种更安全的做法是不定义operator==，直接上remove_if：

int targetId = 1001; v.erase(std::remove_if(v.begin(), v.end(), [targetId](const Student& s) { return s.id == targetId; }), v.end());

这样比较规则写在调用处，一眼可见，不会有人猜错。而且条件天生就是"按某个字段删"，不需要为了凑operator==而让结构体的语义变得含糊。我在项目里更倾向这条路。

6.2 浮点数别用 == 直接比

顺序表里存double的时候，"删除所有等于 3.14 的元素"这句话本身就是危险的。浮点数在二进制里存不下精确的十进制小数，0.1 + 0.2 != 0.3是常识，比较必须带容差：

#include <cmath> const double target = 3.14; const double eps = 1e-9; v.erase(std::remove_if(v.begin(), v.end(), [target, eps](double x) { return std::fabs(x - target) < eps; }), v.end());

容差取多少要看数据量级。如果表里存的都是 10^6 量级的数，1e-9的绝对容差就没意义了，这时候该用相对容差std::fabs(x - target) <= eps * std::fmax(1.0, std::fabs(target))。选错容差的后果是"该删的没删干净"或者"不该删的被误删"，两者都很难排查，因为在单步调试里每个数看起来都"差不多等于"目标。

6.3 一次删多个指定值

有时候要删的不是一个值，而是一组值。笨办法是循环调用 N 次删除，每次 O(n)，总共 O(n·m)。聪明一点的做法是把要删的值塞进哈希表，一次扫描搞定：

#include <unordered_set> const std::unordered_set<int> bad = {2, 5, 8}; v.erase(std::remove_if(v.begin(), v.end(), [&bad](int x) { return bad.count(x) > 0; }), v.end());

复杂度是 O(n) 加一次哈希查询的常数，比循环删除快得多。小数据量下，如果待删集合的元素个数很少（比如两三个），用x == a || x == b || x == c反而更快，因为省掉了建表和哈希的开销。判断标准很简单：待删集合大于 4 个元素就上哈希表，小于等于 3 个就直接或起来。

6.4 课本接口风格的顺序表怎么写

如果你的场景是要按照数据结构课本那套SqList来写，接口大概长这样：数据域是ElemType data[MAXSIZE]，长度域是int length。"删除所有指定值"的函数签名和实现大致是：

struct SqList { static const int MAXSIZE = 1000; int data[MAXSIZE]; int length; }; bool DeleteAllX(SqList& L, int x) { int slow = 0; for (int fast = 0; fast < L.length; ++fast) { if (L.data[fast] != x) { L.data[slow++] = L.data[fast]; } } L.length = slow; // 关键：把逻辑长度同步回去 return true; }

跟vector版本对照着看，会发现核心逻辑一模一样，区别只有两点：一是"缩短"要靠手动改length，二是没有capacity概念（因为数组是静态的）。能看懂这个对应关系，说明你真的理解了快慢指针，而不是记住了某段代码。

如果题目要求返回被删元素的个数，也很简单，oldLen - newLen就是答案，不需要额外维护计数器。

7. 上机前的自查清单

最后把我自己提交前会过一遍的检查项列出来。这份清单帮我省过不少罚时。

• 删完之后遍历上界用对了吗？如果用下标循环并且边走边删，务必确认是"删了不自增"或"删了要回退"，而不是无脑i++。这是漏删的头号原因。
• 迭代器有没有在用之前先失效？循环里erase必须写it = v.erase(it)，不能写v.erase(it); ++it;。
• 用了 std::remove 有没有跟 erase？只调remove不调erase，size()不变，判题直接错。
• 下标类型是不是有符号的？用int i配合v.size()比较，删除时i--到 -1 会翻车。要么全程size_t，要么显式转成int。
• 需不需要保序？需求里如果有"保持原有顺序"或者输出要求严格比对，就不能用交换删除。
• 是否要真的缩短容器？如果函数签名是"返回新长度"（像很多算法题那样），那么快慢指针之后不需要resize；如果是工程代码，resize或erase尾部一定要补上，否则尾部残留的旧对象会造成size()与实际语义不符。
• 类型有没有operator==？自定义类型用std::remove会编译不过，报错信息还很长，先检查这个再怀疑别的。
• 浮点比较带容差了吗？直接==基本等于埋雷。
• 边界三个用例跑过没有？空表、全命中、全不命中。手动跑一遍花不了两分钟，能挡掉大部分低级错误。

提示：vector<bool>是个特例，它内部按位压缩存储，*it返回的是代理对象而不是真正的bool&，很多模板代码在上面会编译失败。如果你恰好要处理vector<bool>并且碰到莫名其妙的编译错误，先用std::vector<char>顶一下，或者把删除逻辑改成基于下标的快慢指针版本，绕开迭代器代理的问题。

我个人在这题上的体会就一句话：别在遍历的同时去修改容器的结构。想清楚这一点，快慢指针的写法几乎是自然而然地浮现出来的——扫描、筛选、搬运、收缩，四个动作各管一段，互不干扰。真到了线上代码，我会先看能不能用std::erase_if一行解决；不能用的时候，就老老实实写快慢指针，然后把边界用例跑满再提交。