C++如何实现高效的数组元素去重(不改变顺序)-C++-PHP中文网

最常用且兼顾效率与顺序的方案是用std::unordered_set配合遍历标记重复位置后批量erase，而非边遍历边删；原地去重应采用双指针+unordered_set判断，最后resize截断，时间复杂度接近o(n)，空间o(k)。

c++如何实现高效的数组元素去重(不改变顺序)

用 `std::unordered_set` 配合 `std::vector::erase` 迭代器删除

最常用且兼顾效率与顺序的方案：遍历原数组，用哈希集合记录已见元素，对重复项标记后批量擦除。关键不是边遍历边删（会破坏迭代器），而是先收集重复位置再统一处理。

std::unordered_set 查重平均 O(1)，总时间复杂度接近 O(n)；比 std::set（O(log n)）更合适纯去重场景
别用 std::vector::remove_if 直接配 unordered_set —— 它内部是“移动非匹配项”，但你无法在 lambda 里安全更新集合状态（闭包捕获需 mutable，且逻辑易错）
正确做法：用索引或反向迭代器记录待删位置，最后调用 erase + remove_if 组合，或直接倒序删（避免索引偏移）

原地去重且保持顺序的 in-place 写法（不额外分配 vector）

如果内存敏感、明确要求复用原容器空间，可用双指针：一个读位置 i，一个写位置 write，遇到新元素就拷贝到 write 并递增。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

必须配合 unordered_set 判断是否见过，否则无法保证 O(n) 时间
注意：vector 的 resize 要放在最后，否则中间 resize 会触发多余内存分配

示例片段：

std::unordered_set<int> seen;<br>size_t write = 0;<br>for (size_t i = 0; i     if (seen.insert(vec[i]).second) { // insert 返回 pair<iterator bool><br>        vec[write++] = vec[i];<br>    }<br>}<br>vec.resize(write);</iterator></int>

当元素类型不可哈希（如自定义结构体）时怎么处理

std::unordered_set 失效，得退回到 std::set 或手写哈希函数。但前者 O(n log n)，后者要确保散列质量，否则退化成 O(n²)。

优先尝试为结构体提供 operator== 和 std::hash 特化 —— 不要只重载 == 就以为能进 unordered_set
若无法控制类型定义，改用 std::set<t></t> + count() 判断，但注意 count 在 set 中是 O(log n)，整体 O(n log n)
极端情况（小数组、低频调用）：用 std::find 在已写区间线性查找 —— 简单但 O(n²)，仅作保底