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::vector<int> 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::vector<Person> 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::vector<int> 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::vector<int> 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::vector<MyClass> 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::vector<Point> 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::list：std::list有自己专用的成员函数unique()，它的作用是移除容器中所有连续重复的元素。使用成员函数list.unique()或list.unique(pred)通常比std::unique算法更高效，因为它能利用链表的结构特性，直接操作节点指针进行删除，无需“覆盖-擦除”两步。
```
std::list<int> myList = {1,1,2,3,3,2}; myList.sort(); // list需要先排序 myList.unique(); // 直接移除重复项，size()会改变
```
关联容器（std::set,std::map等）：它们本身就不允许重复键，所以根本不需要std::unique。如果你有一个vector想得到无重复集合，直接用它构造一个set更简单：std::set<T> s(vec.begin(), vec.end());。

4. 深入底层：手写一个`my_unique`来加深理解

要真正掌握一个算法，没有比自己实现一遍更好的方法了。下面我们来尝试实现一个简化版的my_unique，它只处理前向迭代器，并展示核心逻辑。

template<typename 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; } // 带自定义谓词的版本 template<typename 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::vector<int> 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::vector<int> vec = {5, 2, 5, 1, 2, 5}; std::unordered_set<int> 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”，这就不满足传递性。 // a=1, b=1.5 (差0.5<1)为真， b=1.5, c=2.2(差0.7<1)为真，但 a=1, c=2.2(差1.2>1)为假。 // 这样的谓词用于 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::vector<int> 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::vector<AccessLog>，每个日志包含user_id和timestamp。由于网络抖动，同一个用户可能在极短时间内产生多条日志。我们想对每个用户，只保留时间戳最早的那条记录（去重），但数据已按时间排序，用户ID是散乱的。

这时，我们可以先按user_id排序，然后用自定义谓词去重（保留第一个，即时间戳最小的，因为整体已按时间排序过，同用户的第一条就是最早的），最后再按其他规则排序（如果需要）。

std::vector<AccessLog> 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 可以方便地进行测试。