C++ unique去重原理 C++ 相邻重复元素去除机制【算法】

std::unique只删相邻重复元素，因其仅比较相邻迭代器值、不改变容器大小、需配合erase使用，且要求输入已排序或满足等价规则。

unique 为什么只删相邻重复元素

std::unique 不是真正“去重”，它只把**连续相同元素压缩成一个**，并返回新逻辑结尾的迭代器。底层不移动非相邻重复项，也不改变容器大小——它只是把待保留的元素往前挪，形成一个无相邻重复的前缀段。

原因在于设计定位：它是为配合 erase 使用的“两步操作”中第一步，本身不涉及容器结构调整，时间复杂度稳定在 O(n)，且不依赖元素可比较性以外的额外信息（比如哈希或全局查找表）。

• 输入必须已排序（或至少按某规则排好序），否则 a, b, a 中的两个 a 不会被识别为“可合并”
• 它不比较所有元素对，只比 *it 和 *(it-1)，所以跳过中间不同值后就断开逻辑链
• 返回的是“新逻辑尾”，不是容器新 size；必须手动用 erase 删掉后面冗余部分

正确调用 unique 的三要素

单独写 std::unique(v.begin(), v.end()) 几乎没用——它改了数据布局但没收缩容器。完整流程必须包含三件事：

• 确保输入区间已按去重要求有序（升序、降序，或自定义等价规则）
• 用返回的迭代器接住新逻辑尾，例如：auto new_end = std::unique(v.begin(), v.end())
• 显式擦除多余部分：v.erase(new_end, v.end())

常见错误是漏掉第三步，结果打印时看到“重复项还在”，其实是它们被覆盖到了末尾，但容器长度没变。

立即学习“C++免费学习笔记（深入）”；

知识画家

AI交互知识生成引擎，一句话生成知识视频、动画和应用

下载

自定义判断重复：用 predicate 替换 ==

默认行为用 operator== 判断相等，但你可以传入任意二元谓词，比如忽略大小写、按绝对值、或只看对象某个字段：

std::vector v = {"abc", "ABC", "def"};
auto new_end = std::unique(v.begin(), v.end(), [](const std::string& a, const std::string& b) {
    return std::equal(a.begin(), a.end(), b.begin(), b.end(),
                      [](char x, char y) { return std::tolower(x) == std::tolower(y); });
});

注意：这个 predicate 必须满足“等价关系”（自反、对称、传递），否则行为未定义。例如不能写 a.size() == b.size()，因为两个长度相同的字符串不一定该被当作“重复”来压缩。

unique 对 vector/string/list 的影响差异

std::unique 是个基于迭代器的算法，不关心容器类型，但它和后续 erase 的组合效果因容器而异：

• std::vector 和 std::string：erase 尾部是 O(1)，整体高效；但 erase 中间段仍是 O(n)，所以先 unique 再 erase 尾部是最优解
• std::list：有成员函数 list::unique()，内部直接 unlink 节点，比通用算法 + erase 更快且不复制元素
• std::forward_list：同样有成员版 unique()，适合单向链表场景

别对 std::set 或 std::map 用 unique——它们天然无重复，而且不支持随机访问迭代器，unique 编译不过。