c++ vector去重方法_c++ unique函数使用详解

std::unique不能直接给vector去重，因为它只移除相邻重复元素并返回新逻辑尾迭代器；若vector未排序或重复元素不相邻，则无效，必须先排序或改用unordered_set配合remove_if保序去重。

为什么 std::unique 不能直接给 vector 去重？

std::unique 并不是真正删除重复元素，它只把**相邻重复元素压缩成一个**，并返回新逻辑结尾的迭代器。如果 vector 未排序或重复元素不相邻，unique 完全无效。

• 常见错误现象：

  std::vector v = {1, 3, 2, 3, 1};
  auto it = std::unique(v.begin(), v.end());
  v.erase(it, v.end()); // 结果仍是 {1, 3, 2, 3, 1}，没变

• 根本原因：unique 只比较 *it 和 *(it-1)，不扫描全局
• 正确前提：必须先调用 std::sort（或保证输入已有序）

标准去重三步写法（保留原顺序）

若需去除所有重复项且保持首次出现的顺序（如 {1,3,2,3,1} → {1,3,2}），unique 不适用，得换思路：

• 用 std::unordered_set 记录已见元素，单次遍历过滤
• 避免 std::set（会自动排序，破坏原序）
• 注意：该方法时间复杂度 O(n)，空间 O(n)

std::vector v = {1, 3, 2, 3, 1};
std::unordered_set seen;
auto new_end = std::remove_if(v.begin(), v.end(), [&seen](int x) {
    if (seen.count(x)) return true;
    seen.insert(x);
    return false;
});
v.erase(new_end, v.end());

用 unique + sort 实现去重（不保序）

这是最常被文档示例采用的方式，适合允许结果排序的场景：

• 先 std::sort(v.begin(), v.end())
• 再 auto it = std::unique(v.begin(), v.end())
• 最后 v.erase(it, v.end())
• 对自定义类型，需提供严格弱序比较函数（operator 或 lambda）

std::vector v = {"apple", "banana", "apple", "cherry"};
std::sort(v.begin(), v.end());
auto it = std::unique(v.begin(), v.end());
v.erase(it, v.end()); // 得到 {"apple", "banana", "cherry"}

自定义类型去重时 unique 的陷阱

若用 unique 处理结构体或类，必须确保相等判断逻辑与 operator== 或传入的二元谓词一致；否则行为未定义：

• 错误写法：std::unique(v.begin(), v.end()) 但没重载 operator==
• 正确做法：显式传入谓词，例如 [](const auto& a, const auto& b) { return a.id == b.id; }
• 注意：谓词参数是“前一个”和“当前”，不是任意两两比较
• 若结构体含浮点字段，慎用 == 判断，优先用 std::abs(a.x - b.x)

真正去重前，先问自己：要保序吗？数据是否已排好？重复是相邻还是分散？选错方法比写错代码更难调试。