在C的标准模板库STL里unique是一个又常用又容易被低估的算法。说它常用是因为几乎所有写C的人第一次做“数组去重”时都会抄到类似的代码先sort再unique最后erase。说它容易被低估是因为大多数人只把unique当成一个“去重机器”却很少去想它内部到底是怎么跑的、返回值为什么不是void、能不能用来做自定义规则去重、以及它有哪些天然的边界。我写这篇东西的目的就是把unique掰开揉碎从源码层面的执行脉络讲清楚。搞清楚这些你在工程里遇到与“相邻元素去重”“区间压缩”相关的场景时就会有底气得多。先说一个现象很多刚工作两三年的同学对unique的认识停留在“能去掉重复元素”但问到“如果数据不是有序的直接用unique会怎样”往往就答不准。答案是不排序直接执行unique程序不会报错但它只能去掉相邻的重复项全局重复的项一个都去不干净。这不是unique的缺陷而是它的设计定位。理解了这一点你才算真正开始掌握这个函数。1. unique函数到底做了什么——从一段最朴素的去重代码说起1.1 拿到手就能直接用的基础用法unique的声明位于algorithm头文件中标准的两个重载长这样template class ForwardIt ForwardIt unique( ForwardIt first, ForwardIt last ); template class ForwardIt, class BinaryPredicate ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );第一个版本用operator判断两个元素是否相等第二个版本允许你传入一个自定义二元谓词p用来表达“两个元素在该规则下等价”。返回类型是一个迭代器指向“新逻辑容器的尾部”也就是“最后一个未被移除元素的下一个位置”。最常见的用法是配合vector#include algorithm #include vector #include iostream int main() { std::vectorint v{1, 1, 2, 3, 3, 3, 4, 5, 5, 6}; auto last std::unique(v.begin(), v.end()); v.erase(last, v.end()); for (auto x : v) { std::cout x ; } // 输出: 1 2 3 4 5 6 }unique把相邻的重复元素“逻辑删除”后真正缩小容器体型的工作要交给erase完成。很多初学者第一次写std::unique(v.begin(), v.end())之后直接打印容器发现元素还在就以为函数没生效其实是因为没有执行erase这段“清扫尾巴”的动作。1.2 关键认知unique处理的是“相邻重复”不是“全局重复”来看这段代码std::vectorint v{1, 2, 1, 3, 3, 2, 4}; auto last std::unique(v.begin(), v.end()); for (auto it v.begin(); it ! last; it) { std::cout *it ; } // 输出: 1 2 1 3 2 4输入里有三个1和两个2但因为它们没有相邻所以unique只把中间那两个连续的3压缩成了一个其他“重复但不相邻”的元素原封不动保留。如果你要的是“把整个序列里重复的元素全部去掉”就必须先让相同的元素聚在一起——最典型的做法就是先sort。注意unique的前提假设是“重复项彼此相邻”。所以在工程里凡是使用unique做全序列去重前面几乎一定会跟一个sort。这是unique最容易被误解的地方也是面试官特别爱问的考点。1.3 返回值到底有什么用——它为什么不是voidunique返回的是“新逻辑区间的尾部迭代器”。它不是一个“计数器”也不是一个“标记值”而是可以直接参与后续算法的迭代器。这有三个层面上的用途第一配合erase做真正的容器缩短这是标准范式。第二如果不erase只看[first, last)这个区间的元素容器本身没有变的更小但是“有效数据”的集合变成了一段紧凑区间后面可以继续对这段区间做其他算法操作。第三如果想要“被剔除的元素”[last, 原end())区间里残留的值是“曾经的被覆盖元素”但它们的值已经无意义一般没有人去读。如果一个算法函数返回void你是没法把它串联到erase里的。正是因为unique返回迭代器才使一行式去重写法成为可能v.erase(std::unique(v.begin(), v.end()), v.end());2. 源码之前——unique函数的完整执行链路“源码之前了无秘密”这句话讲的其实就是一件事任何看似神秘的库函数拆到内部都很朴素。unique的内部实现思路和remove、remove_if这类“搬移覆盖型算法”如出一辙。2.1 手动模拟unique的内部循环下面我用一个简化的实现来模拟unique的核心执行逻辑。这段代码不是标准库的逐字拷贝但行为语义是一致的templateclass ForwardIt ForwardIt unique_impl(ForwardIt first, ForwardIt last) { if (first last) { return last; } ForwardIt result first; // “守备区”的尾巴 while (first ! last) { if (!(*result *first)) { // 发现新元素向前搬运 *(result) std::move(*first); } } return result; }这里的核心变量有两个first是“巡逻指针”不断向后扫描整个区间result是“守备区指针”指向已确认无重复的最后一个元素。一开始result指向第一个元素因为第一个元素无论如何都会被保留。每次first向前走一步拿新元素和*result做比较。如果相等说明新元素和守备区末尾重复跳过不搬运。如果不相等则把新元素移动到守备区尾部之后的位置同时result前进一步。它的快就在于比较只在相邻的两个位置之间进行每次都是O(1)的赋值或移动没有哈希表的开销也不申请额外堆内存。2.2 为什么不预先reserve也能保持高效有人可能会问vector内部在unique执行过程中会改变 size 吗不会。无论是被“跳过”的元素还是被“搬运”的元素都在同一个容器内部做覆盖vector的size()在整个unique调用期间不变。数据从后面的位置覆盖到前面的位置这个过程不会触发扩容也没有内存重分配。真正改变容量的是后续的erase它会把尾部的“垃圾区间”释放掉。2.3 一个数组的完整变化过程我们用数组{1, 1, 2, 3, 3, 3, 4}来走一遍它的执行轨迹result指向下标0的1。first指向下标1的11 1跳过。first指向下标2的22 ! 1把2赋值给下标1的位置。result指向下标1的2。first指向下标3的33 ! 2把3赋值给下标2的位置。result指向下标2的3。first指向下标4的33 3跳过。first指向下标5的33 3跳过。first指向下标6的44 ! 3把4赋值给下标3的位置。result指向下标3的4。循环结束返回result 1也就是逻辑尾部的下标4。此时数组内容是{1, 2, 3, 4, 3, 3, 4}注意后面三个位置还残留着3, 3, 4但已经不属于有效区间了。如果你不做erase打印整个容器会看到这些“尾巴”这也是许多人产生困惑的来源。提示标准库里的unique实现可能会有if (result ! first)之类的优化判断当result和first指向同一个位置时就不额外做一次自赋值。但这只是细节优化不影响整体逻辑。3. unique的进阶玩法——与sort、erase、自定义谓词的配合3.1 标准去重三板斧sort unique erase全序列去重是unique最经典的组合我直接给出一个完整可运行的例子。这个场景特别常见比如后台统计一批用户ID需要把这个列表变成“唯一用户ID列表”并保持有序。#include algorithm #include vector #include iostream int main() { std::vectorint ids{42, 7, 42, 7, 7, 100, 3, 100}; std::sort(ids.begin(), ids.end()); auto last std::unique(ids.begin(), ids.end()); ids.erase(last, ids.end()); for (int id : ids) { std::cout id ; } // 输出: 3 7 42 100 }注意sort之后相同元素必然相邻unique的“相邻去重”规则就会把后续所有重复项识别出来。在实际工程中我还会提醒一点如果ids后续要频繁做查找可以考虑在erase之后顺手做一个shrink_to_fit或者等价格式。虽然erase不会释放容量但如果是内存敏感的场景std::vectorint(ids).swap(ids)这种写法能真正释放多余内存。不过大多数情况下不必这么做因为shrink_to_fit会带来一次重新分配而如果容器的生命周期不长这笔开销不如省下来。3.2 自定义比较器unique的“同义”判断有时候你需要的不是“完全相等”而是“某种规则下等价”。比如保存了一批订单结构体希望去掉“订单号相同的重复条目”或者保存了一批坐标点希望去掉“x和y都相同”的点。这种场景就要动用第二个重载版本。举例按“姓氏相同即视为重复”来去重。#include algorithm #include vector #include string #include iostream struct Person { std::string name; std::string surname; }; int main() { std::vectorPerson people { {Alice, Smith}, {Bob, Smith}, {Carol, Jones}, {Dave, Smith}, {Eve, Jones} }; // 先按 surname 排序确保同姓相邻 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.surname b.surname; }); auto last std::unique(people.begin(), people.end(), [](const Person a, const Person b) { return a.surname b.surname; }); people.erase(last, people.end()); for (const auto p : people) { std::cout p.name p.surname \n; } // 输出: // Carol Jones // Alice Smith }这个例子的关键点不在unique本身而在sort和unique必须使用“同一套比较规则”。如果sort按surname排而unique按“姓名全相等”判断结果依然是正确的但没有意义因为你已经把所有字段都排在一起了。真正有用的是排序和去重规则一致时才能压缩掉“同姓”的人。再提一个实践细节unique的谓词不能表达“严格弱序”的判断它只回答“a和b在语义上是否相同”。如果你写一个返回a.x b.x的谓词unique的行为将是未定义的因为算法假定该谓词满足等价关系。所以写自定义谓词时务必看清楚你给的是“等价判断”不是“大小判断”。3.3 只去重相邻重复项的场景有时候你不想要全序列唯一只想去掉“连续出现”的重复项。比如一个日志序列里用户连续点击了好几次同一个按钮你只保留一次点击记录但用户点了A按钮又点了B按钮之后再次点A按钮这两次A按钮是要保留的。这个时候sort做不得一排序顺序就乱了直接用unique反而正合适因为它只压缩相邻重复。std::vectorstd::string clicks{A, A, B, C, C, C, A, B}; auto last std::unique(clicks.begin(), clicks.end()); clicks.erase(last, clicks.end()); // 结果: A B C A B很多业务语义本身就关注“相邻事件合并”。unique在这种场景下意外地好用而且代码读起来非常直观。4. 性能分析与实战避坑4.1 复杂度与move语义带来的收益unique的时间复杂度是O(n)其中n是区间长度因为它只需要一趟扫描。对比一下其他去重手段方案时间复杂度额外空间是否保持顺序sort unique eraseO(n log n)O(1)不保持原顺序unordered_set 手动去重平均 O(n)O(n)不保持原顺序两层循环暴力去重O(n^2)O(1)保持原顺序仅 unique 压缩相邻重复O(n)O(1)保持原顺序注意第一行的“O(1)额外空间”指的是std::sort内部通常使用栈递归宏观上不额外申请大规模堆内存。unordered_set方案虽然平均时间复杂度好看但哈希表的内存开销不容小觑。当数据量很大且内存紧张时sort unique是一条非常划算的路线。unique在 C11 之后使用std::move而非拷贝赋值。对于std::string、std::vector这类拥有动态资源的类型move 之后源对象变为“有效但未指定”的状态搬运成本远低于深拷贝。这也是为什么unique能高效处理vectorstring的原因。4.2 四个容易踩的坑第一个坑忘记erase。只调用unique不给erase容器只是“逻辑上缩小”了size()不变打印全部元素时会看到残留尾巴。这个坑最基础也最常见。第二个坑对无序数据直接调用unique。如果没有提前排序你以为在去重其实只是压缩了相邻重复项。结果正确与否完全取决于输入数据是否碰巧把相同元素排在一起。第三个坑erase的位置错误。有些人会把v.erase(v.begin(), last)当成清扫动作这是方向性错误。erase应该清理[last, v.end())这个尾部区间而不是头部区间。写反了会把有效数据清掉留下垃圾。第四个坑自定义类型未实现或未正确实现operator。第一个重载的unique依赖operator如果你在一个自定义结构体上直接用而它没有定义operator编译器直接报错如果定义了但语义不对比如比较了指针地址而非内容unique会给出错误结果。4.3 关于“先unique再erase”的容器选择unique适用于任意前向迭代器ForwardIterator所以标准库容器里vector、deque、list都能用。但要注意list有自己的成员函数unique()成员版本的复杂度同样是线性而且不需要你再调用erase来缩短容器因为它本质上直接修改了链表节点个数。如果你确定用的是list那么lst.unique()是更顺手的写法。array是固定大小容器不能erase但可以做区间压缩然后只对[begin, last)区间做逻辑处理。关联容器如set、map本身就不允许重复就不需要unique了。5. 工程实践一段生产级去重代码示例最后分享一个我在实际项目里用过的写法。当时的需求是从日志中提取一批“事件编码”这些编码可能因为上游重试而产生大量连续重复我要把“连续重复”压缩保留“编码首次出现”的事件并且还要统计不同编码的数量。#include algorithm #include vector #include string #include iostream // 压缩连续重复事件返回压缩后的事件数量 size_t CompressEvents(std::vectorstd::string events) { auto last std::unique(events.begin(), events.end()); events.erase(last, events.end()); // 此时“连续重复”已经被合并接下来按有序统计不同编码数量 std::vectorstd::string sorted_events(events.begin(), events.end()); std::sort(sorted_events.begin(), sorted_events.end()); auto sorted_last std::unique(sorted_events.begin(), sorted_events.end()); return static_castsize_t(std::distance(sorted_events.begin(), sorted_last)); } int main() { std::vectorstd::string logs{ EVT_001, EVT_001, EVT_002, EVT_003, EVT_003, EVT_003, EVT_001, EVT_004 }; size_t distinct_count CompressEvents(logs); for (const auto e : logs) { std::cout e \n; } std::cout distinct count: distinct_count \n; // 输出: // EVT_001 // EVT_002 // EVT_003 // EVT_001 // EVT_004 // distinct count: 4 }这里我先用unique压缩连续重复保留了“事件发生顺序”这一层语义再复制一份做全序列统计虽然多了一次复制和排序开销但整体的时间和空间消耗都在可控范围。如果你连一次复制都不想做也可以改为遍历logs把元素逐个插入一个unordered_set里计数。两种写法各有取舍一份数据循环走多次 vs 多一份内存换简单逻辑。根据我个人的实际体会unique在工程中出现频率最高的组合仍然是把sort unique erase当作“数组全去重”的标准范式。它看起来简单但你越了解它的内部执行方式就越能判断什么时候该用它、什么时候该换哈希表、什么时候该用list::unique。当你明白它是在原地做“覆盖式压缩”、只处理相邻重复、返回值是给后续操作铺路的迭代器时你就不会再写出“调了 unique 但容器没变”或者“没排序却想全去重”的代码了。算法源码的阅读最有意思的地方就在于此很多复杂的面纱下面逻辑往往朴素得像一个双指针循环而问题真正的复杂度其实藏在你对问题域的理解里。