在某个项目里我遇到一位同事拿着代码满脸疑惑地走过来他对着一个std::vectorint调用了std::unique结果遍历容器时发现末尾还躺着重复的值size()也纹丝不动——他一度怀疑是自己用错了编译器。我让他把unique返回的迭代器和end()之间的元素打出来看看他打印完愣了一下原来重复项还在那儿只是没人管它们了。这个故事特别典型因为unique大概是 STL 里名字最容易引起误解的算法之一。它并不真正“删除”任何元素它做的是把相邻重复元素压缩成一份把多出来的副本移动到区间末尾然后返回一个新的逻辑结尾迭代器。真正的物理删除还得靠容器自己的erase来完成。标题里说“源码之前了无秘密”既然要讲透这个函数我们就不能只把它当个黑盒把它拆成源码来看也就是十几行代码的事读懂之后网上那些“unique 就是去重啊”“去重必须配合 sort 啊”的说法到底对在哪、错在哪一眼就能分辨。这篇文章我会从函数行为、源码实现、谓词版本的坑、与erase的配合、以及和list成员函数的对比这几个角度把这个老朋友彻底讲透。适合刚学 STL 的初学者也适合想搞清楚内部机制的进阶读者。1. 先把“去重”说清楚unique 处理的是相邻重复不是全局重复1.1 一个反直觉的输出结果很多人第一次看到unique的输出都会愣一下。看这段代码#include algorithm #include iostream #include vector int main() { std::vectorint v{1, 1, 2, 3, 3, 3, 4, 1, 1}; auto last std::unique(v.begin(), v.end()); std::cout 逻辑区间: ; for (auto it v.begin(); it ! last; it) { std::cout *it ; } std::cout \n; std::cout 容器全部元素: ; for (int x : v) std::cout x ; std::cout \n; std::cout 容器大小: v.size() \n; return 0; }输出结果是逻辑区间: 1 2 3 4 1 容器全部元素: 1 2 3 4 1 1 1 容器大小: 7注意逻辑区间最后那个1。为什么它没有被去掉因为它虽然和开头的1相等但中间隔了2、3、4在“相邻”这个意义上它和前面的4不相等它自己也没有紧接着的重复项所以它不算“相邻重复”被保留了。这就是unique的核心语义它只消除每一组相邻等价元素中除第一个以外的部分。它是一个局部算法扫描的是紧挨着的两个元素不是全局统计。1.2 “不删除元素”到底是什么意思再强调一次unique不改变容器大小。v.size()是 7unique之后还是 7。那它做了什么它把有效元素往前搬把重复的“副本”移到尾部最后返回的迭代器last指向新的逻辑结尾。区间[begin(), last)里的数据是去重后的有效数据区间[last, end())里那些遗留值本质上已经是被“放弃”的元素——内容可能是被移动过的旧值甚至有些值是未指定的你不应该再去读它们。我习惯用一个比喻来解释这件事整理书架的时候把相同封面的书抽出一本留作代表剩下的副本统统堆到书架最右侧然后贴一张便签写上“有效区到此为止”。书架还是那个书架书的数量没变但你知道真正要用的书只到便签为止。右侧那堆书要真的清掉你得自己动手扔。1.3 用在哪里排序 unique erase 的三段式既然unique只处理相邻重复那么想让所有重复值都“聚在一起”前提就是排序。只有当序列有序时所有相等的元素才会连续出现成为合法的“相邻重复”。所以“对一个容器真正去重”的标准姿势是std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end());这个三段式几乎出现在所有 C 去重相关的代码里先排序让相等的元素变成相邻组再用unique把每组压成一份返回新结尾最后用erase把尾部的垃圾清理掉。三步各司其职缺一不可。2. 主流标准库实现里那十几行代码去掉神秘感2.1 源码到底长什么样与其对着文档猜行为不如直接把实现摆出来。我平时阅读的那个 C 标准库实现里std::unique去掉宏、异常处理和内部函数分层之后核心骨架就是下面这个样子template typename ForwardIt ForwardIt unique(ForwardIt first, ForwardIt last) { if (first last) return last; ForwardIt result first; while (first ! last) { if (!(*result *first)) { *result std::move(*first); } } return result; }这段代码对应的是默认版本也就是用operator判断“是否相等”的那个重载。标准库里还实现了带谓词的版本内部通常会把核心逻辑拆成__unique之类的辅助函数C11 之后赋值动作改成std::move避免不必要的拷贝。但不管怎么包装真正的循环就是这个样子。我第一次读到这段实现的时候很震惊一个让无数人误解的函数源码就这么点是的。它朴素得像remove的孪生兄弟没有花哨的技巧就是一个双指针同向扫描。2.2 逐行推演双指针如何一趟完成拿{1, 1, 2, 3, 3, 3, 4, 1, 1}来推演。初始时first指向第一个元素result也指向第一个元素。注意循环条件是first ! last所以first每一次都会先向后走一步再和result指向的元素比较。步骤first 指向result 指向比较结果动作1第二个1第一个1相等跳过22第一个1不等result指向第二个位置写入23第一个32不等result指向第三个位置写入34第二个3第一个3相等跳过5第三个3第一个3相等跳过64第一个3不等result指向第四个位置写入47第一个14不等result指向第五个位置写入18第二个1第一个1相等跳过循环结束返回result指向第六个元素。此时[begin, result)区间就是1 2 3 4 1和 1.1 节的输出一致。有两个细节值得注意。第一result和first都只要求是前向迭代器不需要随机访问所以unique可以作用于list后面讲list成员函数时还会提到。第二比较的对象是“已经保留下来的最后一个元素”和“当前扫描到的元素”而不是“原序列里紧挨着的两个元素”这一点在第 4 节谓词部分会引出很多坑。2.3 为什么它不需要额外内存、为什么是 O(n)这个算法的空间复杂度是 O(1)没有申请任何堆内存全部在原区间内覆写完成。时间复杂度是 O(n)因为first每轮只前进一次每次比较和赋值都是常数操作。对比一下“手动去重”的常见思路很多人会新建一个vector遍历原序列用find判断新容器里是否已存在当前值不存在才push_back。这个做法空间是 O(n)时间最坏是 O(n²)。而unique在算法层面就赢在“一趟、零额外空间”这也是 STL 算法设计的典型风格能用迭代器区间解决的问题绝不引入容器层面的开销。3. 从算法族谱看 unique它和 remove 是亲兄弟3.1 两类算法的共同套路搬移 返回逻辑结尾STL 里有一类算法它们的共同特征是不改变容器大小只把要保留的值往区间前部搬把要丢弃的值留在后部然后返回一个新的逻辑结尾。remove、remove_if、unique都属此类。拿remove来说它的典型用法也是配合erasev.erase(std::remove(v.begin(), v.end(), 0), v.end());这被称为 erase-remove 惯用法。unique走的完全是同一个套路所以erase(std::unique(...), end())也可以理解成 erase-unique 惯用法。这两兄弟的结构几乎一样一个读指针往前扫描一个写指针在安全位置等待遇到“不该要的”就跳过遇到“该要的”就搬过来。3.2 为什么 STL 算法不直接删除元素很多人会问既然都判断出重复了为什么不直接删掉原因有三点都很本质。第一算法只接收迭代器它不知道这个迭代器属于哪个容器。是vector还是list还是原生数组算法层无法得知也就无法调用容器的erase。第二erase会改变容器大小而算法不应该有这种副作用。STL 的核心哲学是“算法操作区间容器管理内存”两者解耦。算法只负责把数据整理成你想要的样子物理内存的增删是容器的事。第三返回迭代器给调用者留了选择空间。你拿到新的逻辑结尾后可以决定是erase掉尾部还是仅仅用这个结尾做后续处理比如只输出前 N 个有效元素。强制删除反而会剥夺这种灵活性。3.3 容器自己也能去重list 与 forward_list 的成员函数有意思的是list和forward_list各自提供了成员函数版本的unique。它们和算法版最大的区别是成员函数版会真正删除节点。链表去重只需要改指针把重复节点的前驱后继重新连接起来再释放多余节点整个过程没有元素搬移。算法版unique虽然也能用在list上因为list的双向迭代器满足前向迭代器要求但算法版只能通过迭代器赋值覆写会产生元素移动开销。所以对链表来说成员函数版是更优选择。对比一下两个版本维度算法版std::unique链表成员函数list::unique是否改变 size否需要手动erase是直接删除节点元素搬移有move赋值无只改指针适用容器所有前向迭代器区间仅 list / forward_list返回值新逻辑结尾迭代器void4. 谓词版本的核心黑坑比较对象到底是什么4.1 带谓词的 unique先定义什么叫“重复”std::unique还有一个重载template typename ForwardIt, typename BinaryPredicate ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate pred);pred(a, b)返回true表示a和b属于同一组。标准对pred的要求是它必须是一个等价关系自反、对称、传递。最常见的用法是按某个字段去重。比如按工资去重v.erase(std::unique(v.begin(), v.end(), [](const auto a, const auto b) { return a.salary b.salary; }), v.end());这里的 lambda 没有状态纯粹判断两个元素的 salary 是否相等这就是pred最该有的样子。4.2 错误示范想自己维护“上一个值”结果翻车我见过有人写出这种代码试图在 lambda 里捕获一个prevSalary自己记录上一份工资然后再判断当前值是不是重复。auto it std::unique(v.begin(), v.end(), [prevSalary std::optionaldouble{}](const auto a, const auto b) mutable - bool { if (!prevSalary) prevSalary a.salary; bool dup (a.salary b.salary || b.salary *prevSalary); prevSalary b.salary; return dup; });这段代码在某个编译器版本上可能“碰巧”工作但它是错误的而且错得很典型。原因在于标准只要求pred是一个等价关系从不保证它的调用顺序和调用次数。实现内部到底是用“已保留的最后一个元素”和“当前扫描元素”比较还是用原始序列里相邻的两个元素比较严格来说都是实现细节。你一旦让谓词带上可变状态、依赖“上一次调用时传入的是谁”就等于把自己绑在了某个实现的行为上换个标准库版本、换个优化选项结果都可能变。正确写法前面已经给了不需要自己记录什么“上一个值”unique的内部逻辑天然保证了“等价组里第一个元素被保留”。因为result初始指向第一个元素循环从来不拿第一个元素和自己比较它只有遇到不等时才会前进所以第一份记录永远不会被“判定为重复”。4.3 谓词必须无副作用、具备传递性除了不能有状态谓词还有一个隐藏要求等价关系要传递。比如你想按“工资差不超过 50 算同一档”来去重这就毁了——a和b差 30b和c差 30但a和c差 60不满足传递性。这种情况下unique的行为就没有明确定义结果完全依赖实现细节。遇到这种“模糊等价”的去重需求正确做法是先把数据聚类或分桶再用unique处理已经严格分好组的序列。让unique做它擅长的事不要把模糊逻辑塞进谓词里。5. 真正删除要联手 erase完整惯用法与效率账5.1 erase-unique 惯用法unique本身不删除元素erase才是真正动手清理的那个。标准写法std::vectorint v{4, 1, 1, 2, 3, 3, 3, 2}; std::sort(v.begin(), v.end()); // 先排序 v.erase(std::unique(v.begin(), v.end()), v.end()); // 再 unique再 erase执行后v变成{1, 2, 3, 4}。std::string里字符去重也一样std::string也有erase成员函数直接套同样句式。为什么erase的第一个参数传unique的返回值而不是last - 1或别的因为unique返回的迭代器恰好是“有效区间结束”的位置从它到end()之间的元素正是那些被移动出来的重复副本这段区间才是要删的。5.2 array 和 C 数组怎么处理std::array没有eraseC 风格数组更不可能改变大小。这时只能做“逻辑去重”用std::distance算出有效元素个数#include array #include algorithm #include iostream int main() { std::arrayint, 8 a{1, 1, 2, 2, 3, 5, 5, 5}; auto last std::unique(a.begin(), a.end()); size_t newSize std::distance(a.begin(), last); for (size_t i 0; i newSize; i) { std::cout a[i] ; } return 0; }newSize是去重后的有效长度写文件、发网络、遍历都只用前newSize个元素。C 数组也是同样的思路只是把std::distance(a, last)换成last - a即可。5.3 搬移成本与容器选择vector上的unique erase最坏情况下每个元素会被move赋值一次这是 O(n) 的搬移成本。对于元素很大的对象比如包含大量字符串的结构体这个成本不可忽视。链表的情况要好得多。list::unique和forward_list::unique是纯指针操作没有任何元素搬移只是重新连接节点然后释放。所以如果你有一个大对象组成的、需要频繁删除重复项的链表直接用成员函数版别用算法版。各容器配合unique的适用性如下容器推荐的去重方式特点vector / stringerase(unique(...), end())元素搬移 O(n)无额外内存list / forward_list成员函数unique()只拆节点无搬移直接改 sizearrayuniquedistance获取有效长度容量固定逻辑去重dequeerase(unique(...), end())可 erase但开销略高于 vector原始数组unique 指针相减容量固定逻辑去重如果只是“去重但不要求保持原始顺序”可以把数据丢进unordered_set再回填时间近似 O(n)但注意结果顺序会变。需要有序且稳定的去重结果还是排序 unique 最稳。6. 边界情况与容易混淆的兄弟函数6.1 空区间和单元素区间unique对空区间返回last对单元素区间也是直接返回last。原因看源码就懂if (first last) return last;空区间直接返回单元素区间first last立刻成立循环不执行返回last。所以调用unique之前不需要特判“元素是否大于 1”它自己就处理了这些边界情况。这也是源码公开的好处你知道它不会越界不需要多余的防御代码。6.2 全部相同、全部不同的极端情况全部相同的序列比如{5, 5, 5, 5}循环里first每步都和result指向的第一个5相等全部跳过最终返回first 1逻辑区间只剩第一个5。全部不同的序列比如{1, 2, 3, 4}每步都不等result每步前进并写入当前值返回last。看起来什么都没变但每个元素其实都被赋值了一遍。了解这个行为有助于理解循环内部的写入逻辑——result前进和写入是配对的每一对“不等”都会产生一次覆写。6.3 unique_copy把结果写到别处如果不想改动原区间又想得到去重后的结果用std::unique_copy。它把结果输出到目标迭代器底层逻辑和unique几乎一样只是写入动作变成了对输出迭代器的赋值。std::vectorint src{1, 1, 2, 3, 3, 4}; std::vectorint dst; std::unique_copy(src.begin(), src.end(), std::back_inserter(dst));dst得到{1, 2, 3, 4}src保持原样。这个函数在需要保留原始数据做后续处理时很实用。6.4 unique 和 adjacent_find一个侦察兵std::adjacent_find会返回第一对相邻相等元素的位置。如果你想判断“排序后的序列是否存在重复”不需要做完整unique只要if (std::adjacent_find(v.begin(), v.end()) ! v.end()) { // 有相邻重复说明存在至少一对相等元素 }这就够用了。unique是“动手整理”adjacent_find是“只看不动手”。两者底层都有“相邻比较”的影子理解了其中一个再看另一个会非常顺畅。我在项目里第一次用unique时也踩过“size 没变”的坑后来发现调试代码里总拿v.end()去遍历逻辑区间把末尾遗留值也打印出来导致结果怎么看都不对。从那以后我养成了一个习惯凡是配合unique或remove使用遍历一律以返回的迭代器为终点绝不用end()。后来帮别人 review 去重代码我也总是先问一句“unique返回值和end()之间的区间你知道里面是什么吗”这些细节看起来小但搞懂之后很多去重相关的代码一眼就能看穿。unique往后延伸还有ranges::unique之类的现代接口不过核心思想没有变——还是那十几行双指针搬移的算法。源码之前了无秘密希望这篇能把unique这个老朋友彻底讲清楚。
