std::unique去重原理与erase-remove惯用法避坑指南

1. 先搞清楚unique到底在干什么std::unique是algorithm头文件里一个特别容易被误用的函数。我带了几个人的代码以后发现十个人里有八个人第一次用它是这样的拿到一个 vector直接unique(v.begin(), v.end())然后一脸困惑地问为什么容器size()没变、后面的元素还是那么脏。问题不在人笨而在于这个函数的命名太有迷惑性——它叫 unique读起来像是“帮我把容器弄成没有重复的样子”实际语义是“把相邻的重复元素压缩掉然后把新的逻辑结尾告诉我”。这个认知差是后面所有坑的源头。所以这篇东西我不打算按教科书的方式讲签名、讲参数、讲返回值而是从“它为什么会设计成这样”切进去把源码级行为、erase-remove 惯用法、谓词写法、list 成员函数的差异、以及我在真实项目里踩过的几个坑全部摊开说。适合刚学 STL 不久想搞明白原理的同学也适合写了几年 C 但一直靠sort unique erase三段式“肌肉记忆”写代码、从没细想过中间那步到底做了什么的开发者。一句话概括它的适用面当你要在一个连续存储的序列里去除“等价”的相邻元素并且愿意自己承担“真正的删除动作”时用它。它不负责排序不负责改变容器大小不负责检查全局重复。它只做一件非常克制的事——前移覆盖。理解了这个克制你就拿到了正确使用它的钥匙。1.1 一个反直觉的事实unique 从不删除任何元素这是最需要先钉死的一点。std::unique的作用范围是[first, last)它做的事情用伪代码描述就是维护一个“写入位置”指针result从first开始往后扫每遇到一个和*result不相等的元素就把result往前推一格然后把当前元素移动或拷贝到*result的位置上。扫描结束后返回result 1。注意全程没有任何erase调用容器的size()从头到尾没变过。它只是把“有效的、去重后的前缀”堆到了容器头部尾部剩下的那段是已经被移走的残留数据也就是所谓的“僵尸元素”。这些元素在语义上无效但对象还活着析构函数还没跑。看一个具体的例子就明白了。假设有vectorint v {1, 1, 2, 2, 2, 3, 1};调用auto it std::unique(v.begin(), v.end());之后位置0123456调用前1122231调用后1231???it指向索引 4[v.begin(), it)是有效区间{1, 2, 3, 1}索引 4 之后的内容是未指定的残留值。注意最后那个1被保留了——因为它和它前面紧挨着的3不相等。这就是“只去相邻重复”的直接后果整个序列里的1出现了两次一次都没被彻底清掉。所以想让容器真正变干净必须补上第二刀v.erase(it, v.end());。这两步合起来才是大家熟悉的erase-remove惯用法虽然严格说 unique 不是 remove但套路完全一致。注意很多人会把unique和remove混为一谈。std::remove是移除所有等于某值的元素std::unique是压缩相邻等价元素。两者共享同一个“前移覆盖 返回新结尾”的实现哲学但触发条件完全不同。别在面试或者 code review 里说错。1.2 为什么标准库要设计成“只去相邻”这个问题值得认真回答因为答案直接决定了你该在什么场景用它。设想另一种设计unique内部自己维护一个哈希表遍历一遍把没见过的元素保留下来。听起来很美好但它有三个绕不过去的代价。第一需要额外的 O(N) 内存而且这个内存从哪来标准库算法不能随便分配堆内存否则在嵌入式或者实时场景下就没法用了。第二时间复杂度从严格的 O(N) 变成期望 O(N)worst case 可能退化得更糟这违背了 STL 算法对复杂度保证的洁癖。第三也是最重要的一点——它必须改变元素的相对顺序语义。哈希去重如果按插入顺序保留实现起来更复杂如果不保留顺序那这个算法就有了“副作用”不再是纯粹的“压缩”操作。相比之下“只去相邻”的设计有几个漂亮的性质。它只需要前向迭代器ForwardIterator意味着链表也能用它是严格 O(N) 的单趟扫描只做一次比较一次赋值它不分配任何内存它对已经有序的序列天然正确。代价就是把“先排序”的锅甩给了调用者。这个取舍在工程上其实很合理。真实项目里的去重需求绝大多数场景下数据本来就有序或者排序的代价可以接受。你先sort再unique总复杂度 O(N log N)内存 O(log N)快排的递归栈。比起哈希表的 O(N) 期望时间慢一点但内存友好得多而且在 N 小于十万这个量级上常数因子的差异完全被缓存命中率抵消掉了。1.3 几种去重方案横向对比为了让选型有据可依我把常见的几种去重路子列一下。这张表是我自己整理在笔记里的每次做性能相关的决策前都会翻一眼方案时间复杂度额外内存是否保序适用容器典型场景sort unique eraseO(N log N)O(log N)否vector / deque / string数据可乱序追求内存效率unordered_set 辅助 remove_ifO(N) 期望O(N)是vector / deque必须保留首次出现顺序set 辅助O(N log N)O(N)是任意数据量小且要保序list::uniqueO(N)O(1)是list链表场景天然相邻手动双指针O(N)O(1)否相对原序数组手写题、面试看清楚这张表你就能回答一个很实际的问题为什么我明明知道unordered_set去重更快还是经常用sort unique因为内存。一个存int的 vector100 万个元素占 4MB配一个unordered_setint光节点开销加桶数组轻松翻到 30MB 以上。在内存吃紧的批处理任务里这个差距是致命的。反过来如果业务要求“保留每个元素第一次出现的位置”那sort unique直接出局因为它把原始顺序打乱了。这时候老老实实用哈希表辅助 remove_if虽然费内存但语义正确。选型从来不是比谁快是比谁在约束条件下最合适。2. 拆开看签名、返回值与谓词这一章往细里钻。很多人用unique用了好几年但从没认真看过它的两个重载长什么样于是写出了unique(v.begin(), v.end());这种丢掉返回值、后续全靠猜的代码。2.1 两个重载与返回值的真实含义标准里std::unique有两个版本templateclass ForwardIt ForwardIt unique(ForwardIt first, ForwardIt last); templateclass ForwardIt, class BinaryPredicate ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate p);返回类型是迭代器指向去重后序列的尾后位置不是最后一个有效元素的位置。这个区别在算删除数量的时候很关键删除的元素个数等于std::distance(newEnd, last)或者更直接地last - newEnd随机访问迭代器情况下。newEnd本身指向的是残留区的第一个位置解引用它是未定义行为的边缘地带——严格说它指向有效内存但那个位置的对象已经处于“被移动后”的状态值不可依赖。我见过一种写法试图通过返回值判断有没有重复元素auto it std::unique(v.begin(), v.end()); if (it ! v.end()) { // 认为有重复 —— 错 }这段代码的逻辑是反的但恰好能跑对it ! v.end()成立说明确实发生了压缩也就是存在相邻重复。但这属于“歪打正着”因为如果原序列全是唯一值unique内部虽然一次赋值都没做返回值恰好也等于last。逻辑上站得住但语义表达很糟糕读代码的人要愣三秒。更清楚的写法是直接比较前后 sizeauto before v.size(); v.erase(std::unique(v.begin(), v.end()), v.end()); auto removed before - v.size();这样意图明确而且removed这个变量名本身就是注释。2.2 谓词不是“相等判断”是“等价关系”第二个重载接受一个二元谓词p语义是当p(a, b)返回true时认为a和b等价其中a是当前保留的最后一个元素b是正在扫描的元素。注意是“等价”不是“相等”这两个词在算法语境下分量完全不同。看一个实际需求一批坐标点距离小于 0.001 的视为同一个点要去重。直觉写法是这样std::sort(points.begin(), points.end(), [](const Point a, const Point b) { return a.x b.x || (a.x b.x a.y b.y); }); points.erase(std::unique(points.begin(), points.end(), [](const Point a, const Point b) { return std::abs(a.x - b.x) 1e-3 std::abs(a.y - b.y) 1e-3; }), points.end());这段代码在绝大多数输入下能跑但它有个隐藏的理论缺陷这个谓词不满足传递性。设想三个点 A(0, 0)、B(0.0008, 0)、C(0.0016, 0)A 和 B 距离 0.0008 等价B 和 C 距离 0.0008 等价但 A 和 C 距离 0.0016 不等价。unique的实现只比较“当前保留元素”和“当前扫描元素”所以结果是 A 保留、B 丢弃、C 和 A 比较后保留。如果输入顺序变成 C、B、A结果就变成 C 保留、B 丢弃、A 和 C 比较后保留——同一批数据排序顺序不同去重结果不同。这不是unique的 bug是谓词不满足等价关系导致的未定义行为标准要求谓词必须是等价关系。但在实践中它不崩溃只是结果不稳定所以特别难查。我个人的经验是涉及浮点数的去重不要用 epsilon 谓词配 unique。要么先把坐标量化到固定精度的整数网格比如乘以 1000 取整用整数精确比较要么改用空间索引结构做邻近查询。前一种做法在工程上简单粗暴且完全可控我基本都走这条路。实操心得判断一个谓词能不能给 unique 用问自己一个问题——“如果 a≈b 且 b≈c是不是一定有 a≈c” 答案是“不一定”那这个谓词就别用在这里。2.3 复杂度与异常安全复杂度这块没什么争议恰好std::distance(first, last) - 1次谓词调用最多同样次数的移动赋值。没有分配没有二次遍历线性。这也是它比remove_if更“便宜”的原因之一——谓词调用次数是严格的下界。异常安全方面标准规定如果元素移动或谓词抛出异常序列处于有效但未指定的状态。翻译成人话就是出异常了容器不会坏但里面是什么内容你别猜要么回滚要么重建。这在写异常安全的代码时值得留意尤其是元素类型是自定义类、移动构造可能抛异常的情况下。还有一个容易忽略的点unique要求元素类型满足MoveAssignable。如果你的类只允许拷贝不允许移动它也能工作走拷贝赋值但如果你手写了一个移动构造函数却标了noexcept(false)编译器在某些容器操作上会倾向拷贝而非移动性能会掉。这个属于周边知识但排查性能问题时经常被翻出来。3. 手写一遍把黑盒变白盒光看文档永远记不牢我建议每个学 STL 的人都动手实现一次。不是为了造轮子是为了下次调试的时候脑子里有画面。3.1 参照实现二十行看完核心标准库具体的实现细节各家不同但核心逻辑高度一致大致是这个形状templateclass ForwardIt, class BinaryPredicate ForwardIt my_unique(ForwardIt first, ForwardIt last, BinaryPredicate p) { if (first last) return last; ForwardIt result first; // result 指向当前保留的最后一个元素 while (first ! last) { // first 是扫描指针 if (!p(*result, *first)) { // 不等价说明是新元素 result; // 先挪写入位置 if (result ! first) { // 位置不同才需要搬 *result std::move(*first); } } } return result; // 返回尾后位置 }这段代码里有三个细节值得停下来品。第一个是if (result ! first)这个判断。当序列没有重复时result和first永远同步前进赋值是自己赋给自己纯属浪费。加上这个判断后全唯一序列的情况下一次赋值都不做这是纯粹的优化也是为什么处理已去重数据的开销极低。第二个是*result std::move(*first)用的是移动而不是拷贝。对std::string、std::vector这类元素移动是 O(1) 的指针交换拷贝是 O(长度) 的深拷贝。一个存字符串的 vector 去重移动语义带来的差距可能是几十倍。这也是为什么unique在 C11 之后的实现在处理大对象时明显更顺手。第三个是返回result。注意result在循环结束时指向的是最后一个有效元素自增之后才是尾后。这个 1 如果漏掉erase 的时候会把最后一个有效元素一起删掉。我第一次手写实现的时候就犯过这个错测试用例刚好是全重复的数组结果容器被清空了愣了半天。3.2 完整可跑的验证代码光有实现不够得有验证。这段是我平时用来检验理解的测试程序覆盖了空序列、单元素、全重复、无重复、部分重复这几种边界#include algorithm #include iostream #include string #include vector templateclass It void dump(const std::string tag, It b, It e) { std::cout tag : ; for (; b ! e; b) std::cout *b ; std::cout \n; } int main() { // 用例1经典场景 { std::vectorint v{1, 1, 2, 2, 2, 3, 1}; auto it std::unique(v.begin(), v.end()); dump(unique后逻辑区间, v.begin(), it); dump(unique后物理容器, v.begin(), v.end()); v.erase(it, v.end()); dump(erase后, v.begin(), v.end()); } // 用例2空容器安全 { std::vectorint v; auto it std::unique(v.begin(), v.end()); std::cout 空容器返回是否等于end: (it v.end()) \n; } // 用例3全唯一返回值等于end { std::vectorint v{1, 2, 3, 4, 5}; auto it std::unique(v.begin(), v.end()); std::cout 全唯一时itend: (it v.end()) \n; } // 用例4全相同 { std::vectorint v{7, 7, 7, 7}; v.erase(std::unique(v.begin(), v.end()), v.end()); dump(全相同去重后, v.begin(), v.end()); } return 0; }跑一遍你会看到用例 1 里“逻辑区间”是1 2 3 1“物理容器”是1 2 3 1 ? ? ?后面几个值取决于实现可能是残留的 2 2 3 之类。这个对比图我建议每个初学的人都亲眼看一下比读十遍文档管用。3.3 场景实战字符串、结构体、链表把unique放到具体场景里一些细节才会浮出来。字符串去重。std::string是连续存储的unique直接用配合erase就是经典的回文重排、字符压缩等题目的标准解法std::string s aabbccddeeff; std::sort(s.begin(), s.end()); s.erase(std::unique(s.begin(), s.end()), s.end()); // s abcdef这里有一处容易踩的坑std::string::erase(iterator, iterator)这个重载是 C11 才加进来的老编译器上得用erase(pos, count)版本。现在基本不用担心但如果你的项目跨老工具链编译报错的时候先想到这一点。结构体去重。假设有个日志记录结构按(level, module)去重保留第一条struct LogEntry { int level; std::string module; std::string message; }; std::sort(logs.begin(), logs.end(), [](const LogEntry a, const LogEntry b) { if (a.level ! b.level) return a.level b.level; return a.module b.module; }); logs.erase(std::unique(logs.begin(), logs.end(), [](const LogEntry a, const LogEntry b) { return a.level b.level a.module b.module; }), logs.end());这里有个非常隐蔽的陷阱排序用的比较器和去重用的谓词必须是“一致的”。具体说如果sort认为 A 排在 B 前面A B那么unique的等价谓词就不能认为 A 和 B 等价否则这两个元素相邻后会被错误地合并。上面这段代码是一致的因为排序键和去重键完全重合。反过来如果排序只按level排去重却按(level, module)判断那么同一个level下不同module的记录会被排序打散到不同位置去重逻辑就乱了。这类 bug 不会崩只会产出“偶尔少几条”的诡异结果排查成本极高。我的经验是去重谓词判断的字段必须是排序比较器里用到的字段的超集或相等集。链表场景。std::unique对std::list也能用因为list的迭代器是双向的满足前向迭代器的要求。但更自然的选择是用成员函数list::unique()std::listint lst{1, 1, 2, 2, 3}; lst.unique(); // 真正删除size 从 5 变 3 lst.unique([](int a, int b) { // 自定义等价 return std::abs(a - b) 1; });两个关键差异必须记住第一list::unique真的会删除节点不需要你再调erase调用后size()立即变小第二它是成员函数作用在整个链表上不接受迭代器区间。这两点和std::unique完全相反混用会导致“erase 一个已经不存在的位置”这种灾难。提示list::unique的设计其实是更“完整”的去重语义但它没法用在 vector 上——因为 vector 上删除元素是 O(N) 的搬移标准库不想让你不知不觉付出这个代价。这个设计选择的背后逻辑和前面讲的“unique 不删元素”是一脉相承的算法只做它擅长的事容器的维护交还给容器。4. 那些年踩过的坑与排查表这一章是我最想写的部分。网上讲 unique 的文章大多止步于“记得 erase”但真实项目里的问题往往更绕。下面这几个问题每一个我都实际遇到过。4.1 忘了 erase 引发的连锁事故最经典的错误形态长这样std::sort(v.begin(), v.end()); std::unique(v.begin(), v.end()); // 忘了接收返回值忘了 erase // 后面代码认为 v 已经去重了后果分几种。如果后面是遍历整个容器你会读到尾部那堆残留数据表现出来就是“去重后反而出现了不该有的值”。如果后面是v.size()做统计数字偏大。如果后面还要继续push_back新增的元素会追加到残留区后面而不是接在逻辑结尾整个容器的数据就彻底乱了。排查这类问题有个笨但有效的方法在unique之后立刻打印v.size()和std::distance(v.begin(), std::unique(...))两个数一对比就知道有没有做 erase。更好的办法是把它封装成一个带名字的函数从源头杜绝templateclass C void dedup_adjacent(C c) { c.erase(std::unique(c.begin(), c.end()), c.end()); } templateclass C, class Pred void dedup_adjacent(C c, Pred p) { c.erase(std::unique(c.begin(), c.end(), p), c.end()); }封装之后调用点只有一行dedup_adjacent(v);想写错都难。这种小工具函数我几乎每个项目都会带一份成本极低收益极高。4.2 数据没排序就调 unique第二高频的错误。给定{1, 2, 1, 3, 1}不排序直接unique结果还是{1, 2, 1, 3, 1}一个都没去掉因为根本没有相邻重复。这时候人的第一反应往往是“unique 坏了”其实是期望错了。这里有个语义上的澄清unique的正确使用前提不是“序列有序”而是“等价元素相邻”。对按整数比较的普通场景等价就是相等那自然需要排序。但对某些特殊场景比如你只想去掉连续重复的日志保留每次状态切换的记录那你恰恰不应该排序直接unique才是对的// 状态序列运行、运行、运行、停止、停止、运行 std::vectorstd::string states{run, run, run, stop, stop, run}; states.erase(std::unique(states.begin(), states.end()), states.end()); // 结果run, stop, run —— 保留了状态切换的时间点这个用法在很多状态机日志压缩、传感器数据降采样里非常常见。所以“sort unique”不是固定搭配是先问“我的数据里什么才算重复”。4.3 问题速查表我把常见症状和对应原因整理成表出问题的时候对着找比盲猜快得多症状最可能的原因处理方式去重后 size 没变忘了调 erase补上c.erase(it, c.end())去重后出现本不该有的值只接收了返回值没 erase残留数据被当成有效数据同上一个重复都没去掉数据未排序等价元素不相邻先 sort或确认本来就不该排序结果比预期多删了元素去重谓词判断的字段少于排序字段或在谓词里写反了逻辑对齐排序与去重的键结果不稳定换输入顺序结果就变谓词不满足传递性常见于浮点 epsilon 比较改用整数化或精确比较对 list 调完 unique 再 erase 崩溃list::unique已经真删除了元素迭代器失效删除多余的 erase 调用编译报错说 unique 不是 std 的成员漏了#include algorithm补头文件性能远低于预期元素类型移动构造代价高或谓词内做了重操作优化移动语义谓词内避免分配这张表里最后两条值得展开说两句。头文件这个问题看着傻但algorithm在某些实现里被其他头间接包含导致你本地能编过、换平台就挂所以别依赖运气该 include 就 include。性能那条更微妙——unique的谓词会被调用 N-1 次如果谓词里每次都构造一个临时字符串或者查一次数据库那整体开销会被放大 N 倍。谓词里只做轻量比较需要预处理的就提前算好缓存起来。5. 工程里的取舍与性能直觉最后聊聊怎么在实际项目里用出水平。会用函数只是入门知道什么时候不该用它才是老手。5.1 几个去重方案的实测倾向我本地做过一轮粗略对比机器是普通的开发笔记本数据是 100 万个随机生成的int取值范围 0~99999所以重复率很高编译器开-O2。这组数据不具备严格的基准测试价值但量级上的结论是稳定的方案相对耗时峰值内存增量sort unique erase1.0基准极小unordered_set remove_if1.3 ~ 1.6约 25MBset 逐个插入3.5 以上约 40MB手动插入排序去重巨大极小结论很反直觉在这个量级上哈希方案并没有赢。原因是排序对 cache 极度友好而unordered_set每个节点都是一次随机内存访问缓存未命中率高得吓人。哈希表理论上的 O(N) 优势被常数因子吃掉了。等到 N 涨到千万级哈希方案才开始扳回一城但那时候内存压力也上来了。所以我的实践建议是没有明确的保序需求默认走sort unique erase。它在内存、可预测性、代码简洁度上全面胜出只有当你需要保留首次出现顺序、或者元素本身不可比较没有定义的时候才换哈希辅助方案。5.2 保序去重的那个写法值得背下来既然提到了保序需求把那个惯用法写清楚它是remove_if的一个漂亮应用std::vectorint v {3, 1, 3, 2, 2, 1, 4}; std::unordered_setint seen; v.erase(std::remove_if(v.begin(), v.end(), [seen](int x) { return !seen.insert(x).second; }), v.end()); // 结果3, 1, 2, 4关键在于seen.insert(x).second这个返回值——insert返回一个 pairsecond是 bool插入成功为 true已存在为 false。取反之后remove_if就会把“已经见过”的元素全部搬到尾部然后erase一刀切掉。整个逻辑一趟扫描不排序保序代码还短。这段代码有个小陷阱谓词持有了seen的引用而remove_if内部可能多次调用它所以seen必须活得比谓词长。用引用捕获没问题用值捕获就会出大问题——每次拷贝一份空的 set去重完全失效。我第一次写的时候就是用值捕获调试了十分钟才反应过来。5.3 一些零散的实战体会用了这么多年零碎的经验攒了不少挑几条最有用的记在这里。判空先于一切。std::unique(v.begin(), v.end())在空容器上是合法的返回v.end()不会崩。但如果你在调用前手动*v.begin()做点什么那就危险了。养成习惯操作前先if (v.empty()) return;。erase 的迭代器版本对 deque 也适用但性能特征和 vector 不同。deque的两端删除 O(1)中间删除 O(N)去重后的 erase 是从中间删到尾所以代价是线性的可以接受。但如果你对deque频繁做这种操作考虑换成vector更划算。已经排序的数据不一定要去重。如果你的下游逻辑本身能处理重复比如用二分查找找范围、用equal_range取等值区间那就别去重省掉一次 O(N) 的搬移。这是很多人在做数据清洗管道的优化点——去重有时候是“为了好看”而不是“为了正确”。测试用例一定要覆盖全唯一和全相同两个极端。这两个边界能暴露 90% 的返回值处理错误。中间状态反而没那么容易出问题。最后分享一个小技巧如果你在写模板代码不确定调用方的容器是vector还是list别硬套unique。写一个两层分派——检测到容器有成员函数unique就用成员的否则走std::unique加erase。这种 traits 分派写法在通用库里很常见templateclass C, class void struct has_member_unique : std::false_type {}; templateclass C struct has_member_uniqueC, std::void_tdecltype(std::declvalC().unique()) : std::true_type {};这么写确实绕绝大多数业务代码根本用不上。但如果哪天你在维护一个跨容器的通用去重工具这段能省掉一堆特化代码。我个人在业务里更倾向于干脆限制死只支持vector简单直接别给自己找麻烦。