c++中如何实现数组的去重并排序_c++ std::set与vector互转技巧【详解】

std::set天然适合去重+排序，因其基于红黑树实现，插入时自动排序且静默去重，时间复杂度为O(n log n)；但无法保持元素首次出现顺序。

直接用 std::set 去重并排序最稳妥，但要注意它自动丢弃重复元素且不保留原始顺序——这恰恰是多数去重+排序场景想要的；若需保持首次出现顺序，则不能只靠 set，得换策略。

为什么 std::set 天然适合去重+排序

std::set 内部基于红黑树实现，插入时自动排序、自动去重，时间复杂度稳定在 O(log n) 每次插入，整体 O(n log n)。它不接受重复键，相同值第二次 insert() 会静默失败，返回 pair 中的 bool 为 false。

常见误用：把 vector 全部塞进 set 后再转回 vector，却忘了 set 的键比较默认是严格小于（），对自定义类型必须提供 operator 或传入比较函数。

• 基本类型（int、double、string）可直接用，无需额外定义
• 结构体或类必须定义 operator，否则编译报错：invalid operands to binary expression ('const MyStruct' and 'const MyStruct')
• 若只想按某字段排序（如只比 id），可传入 lambda：

  std::set s;

vector → set → vector 的标准三步法

这是最常用、最安全的互转路径，适用于「去重+升序」需求：

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

• 构造 set 时直接用 vector 迭代器初始化：std::set s(v.begin(), v.end());
• 转回 vector 时用范围构造：std::vector result(s.begin(), s.end());
• 注意：不要写成 result.assign(s.begin(), s.end())，虽然也能工作，但语义不如构造清晰；更别用循环 push_back，效率低且冗余

完整示例：

std::vector v = {3, 1, 4, 1, 5, 9, 2, 6, 5}; std::set s(v.begin(), v.end()); std::vector sorted_unique(s.begin(), s.end()); // sorted_unique == {1, 2, 3, 4, 5, 6, 9}

需要保持首次出现顺序？别用 set，改用 unordered_set + vector 手动过滤

std::set 排序即“升序”，无法满足“按第一次出现位置排”的需求（例如输入 {5, 1, 3, 1, 5}，期望输出 {5, 1, 3}）。这时必须放弃自动排序，改用哈希去重 + 原序遍历：

• 用 std::unordered_set 记录已见元素，O(1) 平均查找
• 遍历原 vector，遇到未见过的就加入结果 vector 并标记
• 若之后还需排序，单独调用 std::sort(result.begin(), result.end()) —— 此时去重已完成，排序不会引入新重复

示例：

std::vector v = {5, 1, 3, 1, 5}; std::unordered_set seen; std::vector keep_order; for (int x : v) {     if (seen.find(x) == seen.end()) {         seen.insert(x);         keep_order.push_back(x);     } } // keep_order == {5, 1, 3}，未排序 std::sort(keep_order.begin(), keep_order.end()); // → {1, 3, 5}

性能与内存取舍：set vs sort + unique

有人用 std::sort + std::unique 组合替代 set，代码略长但可能更快（尤其数据量大、比较开销高时）：

• sort + unique 是原地操作，空间 O(1) 额外（除排序本身栈/堆开销），set 需额外 O(n) 节点内存
• sort + unique 时间复杂度也是 O(n log n)，但常数项通常更小；unique 只能作用于相邻重复，必须先排序
• 写法：

  std::vector v = {3, 1, 4, 1, 5}; std::sort(v.begin(), v.end()); auto last = std::unique(v.begin(), v.end()); v.erase(last, v.end()); // v 现在是 {1, 3, 4, 5}

真正容易被忽略的是：如果原 vector 需要保留，sort + unique 就得先 copy，反而增加开销；而 set 构造天然不破坏原数据。