C++ std::unique算法详解：高效移除相邻重复元素

1. 项目概述为什么我们需要std::unique在C的日常开发中尤其是在处理容器数据时我们经常会遇到一个看似简单却让人头疼的问题如何高效地移除一个序列比如数组或std::vector中连续的重复元素想象一下你从数据库里拉取了一长串用户操作日志里面有很多连续重复的“点击”事件记录或者你处理一个排序后的整数列表需要保证每个数字只出现一次。手动写循环去比较和删除代码冗长且容易出错特别是涉及到迭代器失效的问题时新手很容易掉进坑里。这时std::unique就该登场了。它是C标准库algorithm头文件中的一个算法函数专门用来解决“移除相邻重复项”这个特定问题。我刚开始学STL时觉得它名字起得真好——“Unique”独一无二它的任务就是让序列中的元素变得“唯一”在相邻范围内。但请注意它并不直接删除容器中的元素而是通过“覆盖”和“移动”的方式将不重复的元素移动到序列的前部并返回一个指向新的“逻辑末尾”的迭代器。理解这一点是正确使用std::unique的关键。对于C小白或者从C语言转过来的开发者来说理解并熟练运用std::unique能极大提升代码的简洁性和效率。它背后涉及了迭代器、算法复杂度、以及STL“不直接操作容器”的设计哲学。这篇文章我就结合自己多年踩坑和使用的经验带你彻底搞懂std::unique从原理、用法到避坑指南保证你看完就能用用了不出错。2.std::unique的核心原理与行为剖析2.1 它到底做了什么—— “覆盖”而非“删除”这是理解std::unique最核心也最容易误解的一点。很多人包括当年的我望文生义以为调用std::unique(vec.begin(), vec.end())之后vec的大小就自动变小了重复元素被“删除”了。大错特错std::unique是一个作用于迭代器范围的算法它不拥有也不直接修改容器的内部存储结构比如容量capacity。它的工作流程可以类比为在一个队列中整理物品遍历它从序列的起始位置开始用两个“指针”实际上是迭代器进行遍历。我们称它们为“读指针”read和“写指针”write初始都指向开头。比较与移动read指针不断向后移动检查当前元素是否与“写指针”write前一个位置的元素相等默认用比较。如果不相等说明这是一个新的唯一元素那么就把read指向的元素赋值或移动到write指向的位置然后write指针也向后移动一位。跳过重复如果read指向的元素与write-1位置的元素相等即连续重复read指针就继续后移write指针原地不动。这样重复的元素就被“跳过”了。返回新终点当read指针走到原始序列的末尾时遍历结束。此时write指针指向的位置就是所有唯一元素都紧凑排列在前部之后的下一个位置。std::unique函数返回的就是这个write迭代器。这个过程结束后从序列开始到返回的迭代器我们称之为new_end这个区间内包含了所有相邻唯一的元素。而从new_end到原始end()的区间里面的元素状态是“未指定”的通常是被移走的元素留下的“残骸”但具体值不可依赖。容器的size()并没有改变注意这个过程形象地说是把不重复的元素“挤”到了前面后面空出来的位置还占着坑但里面的东西已经没用了。要想真正让容器变小需要配合容器的erase方法。2.2 复杂度与前提为什么通常要先排序std::unique的算法复杂度是线性O(n)其中n是序列长度。因为它只遍历一次。但它的“唯一性”判断仅限于相邻元素。这意味着[1, 2, 1, 3, 3, 2]经过std::unique处理后会变成[1, 2, 1, 3, 2, ...]只有连续的两个3被移除了分散的1和2依然存在。所以如果你想移除序列中所有的重复元素而不仅仅是连续的一个标准的做法是先排序后去重。排序例如std::sort会将所有相同的值放到相邻位置这样std::unique就能一次性将它们全部移除。这个“排序去重”的组合操作非常高效是处理无序列表去重的经典模式。std::vectorint vec {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}; // 第一步排序让相同元素相邻 std::sort(vec.begin(), vec.end()); // vec 变为 {1, 1, 2, 3, 3, 4, 5, 5, 6, 9} // 第二步去除相邻重复项 auto new_end std::unique(vec.begin(), vec.end()); // new_end 指向逻辑新结尾 // 第三步真正删除尾部多余元素 vec.erase(new_end, vec.end()); // vec 变为 {1, 2, 3, 4, 5, 6, 9}2.3 自定义比较准则std::unique默认使用operator来判断两个元素是否“相等”。但很多情况下我们的“重复”标准并非如此。例如对于一个存储自定义Person结构体的容器我们可能认为身份证号相同即为同一个人尽管其他字段不同。为此std::unique提供了重载版本允许传入一个**二元谓词Binary Predicate**作为自定义比较函数。这个函数接受两个元素返回一个bool值表示它们是否应该被视为“相等”即是否重复。struct Person { std::string id; std::string name; int age; }; bool isSamePerson(const Person a, const Person b) { return a.id b.id; // 仅凭ID判断是否为同一人 } std::vectorPerson people {...}; // 先按ID排序确保相同ID的人相邻 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.id b.id; }); // 使用自定义谓词去重 auto last std::unique(people.begin(), people.end(), isSamePerson); people.erase(last, people.end());实操心得自定义谓词必须满足等价关系即自反、对称、传递。简单说如果comp(a, b)为真那么comp(b, a)也应为真并且如果comp(a, b)和comp(b, c)为真那么comp(a, c)也应为真。使用不满足等价关系的谓词会导致未定义行为结果不可预测。3. 从入门到精通std::unique的完整使用指南3.1 基础用法处理内置类型和字符串对于整数、浮点数、字符、标准字符串等已经定义了操作符的类型使用std::unique最为直接。#include iostream #include algorithm #include vector #include string int main() { // 示例1整数数组已排序 std::vectorint nums {1, 1, 2, 2, 2, 3, 4, 4, 5}; auto it_num std::unique(nums.begin(), nums.end()); nums.erase(it_num, nums.end()); for (int n : nums) std::cout n ; // 输出1 2 3 4 5 std::cout \n; // 示例2字符串处理连续相同字符 std::string str Hellooo, World!!!; // 注意这里直接对字符串使用去除连续重复字符 auto it_str std::unique(str.begin(), str.end()); str.erase(it_str, str.end()); std::cout str \n; // 输出Helo, World! (连续重复的o、空格、!被移除) // 示例3未排序的情况效果不符合通常预期 std::vectorint unsorted {5, 2, 5, 1, 2}; auto it_unsorted std::unique(unsorted.begin(), unsorted.end()); unsorted.erase(it_unsorted, unsorted.end()); for (int n : unsorted) std::cout n ; // 输出5 2 5 1 2 无变化因为没有连续重复 std::cout \n; return 0; }3.2 进阶用法处理自定义对象与复杂逻辑当容器内存放的是我们自定义的类或结构体对象时我们需要为其定义“相等”的逻辑。方法一重载operator如果“相等”是你这个类的一个核心逻辑重载操作符是最规范的做法。这样std::unique的默认版本就能直接工作。class MyClass { public: int id; std::string data; bool operator(const MyClass other) const { // 定义你的相等逻辑例如ID相同即认为相等 return id other.id; // 注意如果这样定义那么std::sort也需要相应的比较通常用id或者保证数据已按id排序。 } }; // 使用前需要保证容器按id排序否则std::unique的相邻比较无意义 std::vectorMyClass items ...; std::sort(items.begin(), items.end(), [](const MyClass a, const MyClass b) { return a.id b.id; }); items.erase(std::unique(items.begin(), items.end()), items.end());方法二使用自定义比较函数对象推荐更多时候去重的标准只是特定场景下的需求并非类的全局属性。这时传递一个函数对象lambda表达式、函数指针、仿函数更灵活。struct Point { int x, y; // 不重载 operator }; std::vectorPoint points {{1,1}, {1,1}, {2,3}, {1,1}, {2,3}}; // 目标去除完全相同的点x和y都相等 // 1. 排序需要定义严格的弱序例如先比x再比y std::sort(points.begin(), points.end(), [](const Point a, const Point b) { return std::tie(a.x, a.y) std::tie(b.x, b.y); }); // 2. 去重使用lambda定义“相等” auto last std::unique(points.begin(), points.end(), [](const Point a, const Point b) { return a.x b.x a.y b.y; }); points.erase(last, points.end()); // 现在points里只有 {1,1}, {2,3}注意事项std::tie来自tuple头文件它能方便地创建元组来比较多个成员是实现多字段比较的常用技巧。3.3 与不同容器配合的注意事项std::unique操作的是迭代器范围理论上所有支持前向迭代器的容器都可以用。但不同容器的特性决定了使用细节。std::vector,std::deque,std::string, C风格数组最常用的组合。可以安全地使用erase来删除尾部元素。std::liststd::list有自己专用的成员函数unique()它的作用是移除容器中所有连续重复的元素。使用成员函数list.unique()或list.unique(pred)通常比std::unique算法更高效因为它能利用链表的结构特性直接操作节点指针进行删除无需“覆盖-擦除”两步。std::listint myList {1,1,2,3,3,2}; myList.sort(); // list需要先排序 myList.unique(); // 直接移除重复项size()会改变关联容器std::set,std::map等它们本身就不允许重复键所以根本不需要std::unique。如果你有一个vector想得到无重复集合直接用它构造一个set更简单std::setT s(vec.begin(), vec.end());。4. 深入底层手写一个my_unique来加深理解要真正掌握一个算法没有比自己实现一遍更好的方法了。下面我们来尝试实现一个简化版的my_unique它只处理前向迭代器并展示核心逻辑。templatetypename ForwardIt ForwardIt my_unique(ForwardIt first, ForwardIt last) { if (first last) // 空范围 return last; ForwardIt result first; // “写指针”指向当前唯一序列的末尾 first; // “读指针”从第二个元素开始 while (first ! last) { // 关键比较当前元素(*first)是否与结果序列的最后一个元素(*result)相等 if (!(*result *first)) { result; // 移动写指针 *result std::move(*first); // 将不重复的元素移动/赋值过来 } // 如果相等读指针继续前进写指针不动重复元素被跳过 first; } // 返回的是唯一序列末尾的下一个位置 return result; } // 带自定义谓词的版本 templatetypename ForwardIt, typename BinaryPredicate ForwardIt my_unique(ForwardIt first, ForwardIt last, BinaryPredicate p) { if (first last) return last; ForwardIt result first; first; while (first ! last) { // 使用传入的谓词 p 代替 if (!p(*result, *first)) { result; *result std::move(*first); } first; } return result; }这个实现清晰地展示了“双指针”覆盖的过程。注意几点我们使用了std::move这允许对支持移动语义的类型进行高效移动避免不必要的拷贝。函数返回前对result进行了因为它指向的是最后一个有效元素我们需要返回其下一个位置。标准库的实现会更加复杂和健壮考虑了迭代器类别、异常安全等但核心逻辑与此一致。5. 实战中的典型问题与解决方案即使理解了原理在实际项目中用错std::unique的情况依然屡见不鲜。下面我总结几个最常见的“坑”和解决方案。5.1 忘记erase—— “幽灵数据”问题这是新手最常犯的错误。调用std::unique后容器大小不变尾部遗留的“未指定”元素就像幽灵一样存在。如果你后续基于size()进行遍历或操作会访问到这些无效数据导致逻辑错误或崩溃。错误示例std::vectorint vec {1, 1, 2, 3}; std::unique(vec.begin(), vec.end()); std::cout vec.size(); // 输出依然是4 for (int i 0; i vec.size(); i) { // 会循环4次 std::cout vec[i] ; // 可能输出 1 2 3 3 (最后一个3是脏数据) }正确做法务必使用“擦除-删除”惯用法Erase-Remove Idiom的变体。// 标准三步曲 vec.erase(std::unique(vec.begin(), vec.end()), vec.end());一行代码清晰表达了“去除重复项并调整容器大小”的意图。5.2 未排序导致去重不彻底前面已经强调过std::unique只处理相邻重复。如果你拿到一个无序列表直接用它结果往往不是想要的。解决方案明确你的需求。如果要去除所有重复必须先排序。std::sort(container.begin(), container.end()); container.erase(std::unique(container.begin(), container.end()), container.end());如果想去重但不改变原始顺序即保留每个元素第一次出现的位置就不能用排序因为排序会打乱顺序。这时需要更复杂的逻辑例如使用std::unordered_set来辅助std::vectorint vec {5, 2, 5, 1, 2, 5}; std::unordered_setint seen; auto new_end std::remove_if(vec.begin(), vec.end(), [seen](const int value) { // 如果已经见过就“移除”返回true return !seen.insert(value).second; }); vec.erase(new_end, vec.end()); // 结果 vec {5, 2, 1}保持了原序这里用std::remove_if配合哈希集效率是O(n)但需要额外空间。5.3 自定义谓词的陷阱自定义谓词如果写得不严谨会引发未定义行为。陷阱1谓词非等价关系。// 错误的谓词想去除绝对值相等的元素但 absEqual 不满足对称性满足但传递性呢 // abs(-1) abs(1) 为真 abs(1) abs(-1) 为真 abs(-1) abs(1) 和 abs(1) abs(1) 为真那么 abs(-1) abs(1) 为真其实满足等价关系。这里举一个更明显的反例 // 假设谓词定义为“两数之差小于1”这就不满足传递性。 // a1, b1.5 (差0.51)为真 b1.5, c2.2(差0.71)为真但 a1, c2.2(差1.21)为假。 // 这样的谓词用于 std::unique 会导致不可预测的结果。陷阱2谓词有副作用。标准要求谓词不应修改其参数也不应有其他副作用。违反此规定可能导致程序行为异常。安全准则确保你的自定义比较函数是纯函数输出仅依赖于输入不改变外部状态并且严格满足等价关系的数学定义。5.4 性能考量与选择std::uniquevsstd::list::unique对于链表优先使用成员函数版本。去重全流程成本“排序(O(n log n)) 去重(O(n))”是处理无序向量去重的标准高效做法。如果容器很小或者几乎已排序这个组合很快。空间换时间如果需要保留原序使用std::unordered_set辅助的方法时间复杂度是O(n)但需要O(n)的额外空间。根据你的数据量和内存约束做选择。std::unique在已排序数据上的优势如果数据本身已排序或插入时即保持有序那么直接调用std::unique是O(n)的极其高效。这在处理实时数据流时很有用。6. 扩展应用std::unique在真实场景中的妙用std::unique不仅仅用于简单的去重。结合其他STL算法和技巧它能解决一些有趣的问题。6.1 统计序列中不同元素的个数在排序后使用std::unique返回的迭代器可以轻松计算出唯一元素的个数。std::vectorint vec {7, 3, 3, 1, 7, 1, 2}; std::sort(vec.begin(), vec.end()); auto unique_end std::unique(vec.begin(), vec.end()); size_t num_unique std::distance(vec.begin(), unique_end); std::cout 不同元素个数: num_unique \n; // 输出 4 // 注意此时vec的内容前4位是 {1, 2, 3, 7}后面是未指定值。6.2 与std::remove_if结合进行复杂清理有时清理规则不仅仅是“相邻重复”。例如我们想移除所有连续出现的、满足某个条件的元素块中的重复项只留一个。这需要结合std::unique的自定义谓词和更外层的逻辑但思路是相通的。假设我们有一个字符串想将连续的空格压缩成一个空格std::string text This is a test.; auto new_end std::unique(text.begin(), text.end(), [](char a, char b) { return a b ; // 仅当两个字符都是空格时才视为“重复” }); text.erase(new_end, text.end()); std::cout text; // 输出This is a test.6.3 处理结构体数组并提取关键信息假设我们有一个庞大的、按时间戳排序的访问日志向量std::vectorAccessLog每个日志包含user_id和timestamp。由于网络抖动同一个用户可能在极短时间内产生多条日志。我们想对每个用户只保留时间戳最早的那条记录去重但数据已按时间排序用户ID是散乱的。这时我们可以先按user_id排序然后用自定义谓词去重保留第一个即时间戳最小的因为整体已按时间排序过同用户的第一条就是最早的最后再按其他规则排序如果需要。std::vectorAccessLog logs ...; // 假设AccessLog有 user_id 和 timestamp 成员 // 1. 按user_id主序timestamp次序排序确保相同用户的日志挨着且第一条时间最早 std::sort(logs.begin(), logs.end(), [](const AccessLog a, const AccessLog b) { if (a.user_id ! b.user_id) return a.user_id b.user_id; return a.timestamp b.timestamp; }); // 2. 去重对于相同user_id的只保留第一条时间戳最小 logs.erase(std::unique(logs.begin(), logs.end(), [](const AccessLog a, const AccessLog b) { return a.user_id b.user_id; }), logs.end()); // 现在logs中每个user_id只出现一次且对应其最早访问时间7. 总结与最佳实践建议经过上面的详细拆解相信你已经对std::unique了如指掌。最后我结合自己的经验再强调几条最佳实践帮你写出更稳健、高效的代码时刻记住“覆盖-擦除”两步走调用std::unique后除非你明确知道后续操作不依赖容器尾部数据否则一定要跟一个erase。可以把它刻在脑子里cont.erase(std::unique(cont.begin(), cont.end()), cont.end());。明确你的“唯一性”定义是基于默认的还是自定义规则自定义规则是否满足等价关系这决定了你是否需要传递自定义谓词以及是否需要先排序。排序是去重的好伙伴但非必需分析你的数据。如果数据本身无序且你需要全局去重先排序。如果数据天然有序如时间序列或你只关心连续重复则可以直接用。选择正确的工具对于std::list用list.unique()。对于需要保留非相邻重复项原序的场景考虑std::unordered_set或std::remove_if。不要试图用std::unique解决所有去重问题。注意迭代器失效std::unique本身不会使迭代器失效因为它不改变容器容量但紧随其后的erase操作会使指向被删除元素及其之后位置的迭代器、指针和引用失效。如果你在循环或复杂逻辑中操作需要小心。性能测试对于性能关键的场景不要想当然。如果对“排序去重”和“哈希集辅助去重”两种方案的性能有疑问用真实数据或模拟数据写个基准测试Benchmark是最可靠的方法。现代C有std::chrono或第三方库如 Google Benchmark 可以方便地进行测试。std::unique是C标准库中一个精巧而强大的工具。它完美体现了STL算法“泛型”和“高效”的设计思想。理解它用好它能让你在处理数据序列时更加得心应手写出更具表现力和效率的C代码。希望这篇超详细的解析能帮你绕过我当年踩过的那些坑真正掌握这个“独一无二”的算法。