17370845950

用std::unordered_set边遍历边查重插入是保持顺序且O(n)平均复杂度的首选，关键在于只保留首次出现元素；原地去重需双指针配合unordered_set，避免erase导致O(n²)退化。

用 std::unordered_set 遍历去重最常用也最稳

直接边遍历边查重插入，是保持顺序 + O(n) 平均复杂度的首选。关键不是“删重复”，而是“只保留第一次出现的元素”。

常见错误是先排序再 unique，那顺序就没了；或者用 std::set 导致 O(n log n)，没必要。

• std::unordered_set 存已见元素值，哈希查找均摊 O(1)
• 遍历原 vector，遇到没在 set 里的才 push 到结果 vector
• 注意：元素类型必须支持 operator== 和哈希（内置类型、std::string 都 OK；自定义类需提供 std::hash 特化）

std::vector vec = {1, 2, 3, 2, 4, 1, 5};
std::unordered_set seen;
std::vector result;

for (int x : vec) {
    if (seen.find(x) == seen.end()) {
        seen.insert(x);
        result.push_back(x);
    }
}

原地去重（不额外分配结果 vector）用 erase + remove_if 不行，得手写循环

std::remove_if 依赖谓词，但判断“是否为首次出现”需要状态（已见过哪些），无法无状态表达。强行用它会出错或逻辑混乱。

真正安全的原地去重，还是得用双指针思路：一个读位置 i，一个写位置 write，配合 unordered_set 判断。

• 避免反复调用 erase —— 每次都移动后续元素，O(n²) 退化
• 最后用 vec.resize(write) 截断多余部分
• 如果 vector 很大且内存敏感，这个方案比新建 vector 更省空间

std::vector vec = {1, 2, 3, 2, 4, 1, 5};
std::unordered_set seen;
size_t write = 0;

for (size_t i
 = 0; i < vec.size(); ++i) {
    if (seen.find(vec[i]) == seen.end()) {
        seen.insert(vec[i]);
        vec[write++] = vec[i];
    }
}
vec.resize(write); // now vec = {1, 2, 3, 4, 5}

字符串或小对象用 std::unordered_set<:string> 没问题，但要注意移动语义

对 std::string、std::vector 等可移动类型，插入 unordered_set 时建议用 std::move 避免深拷贝——尤其当字符串很长或 vector 元素很多时。

• 插入前用 std::move(x)，set 内部会 move 构造
• 但注意：move 后原变量进入有效但未定义状态，别再读它
• 如果只是去重 const std::string&，那不用 move，引用传参即可

std::vector strs = {"a", "bb", "a", "ccc"};
std::unordered_set seen;
std::vector result;

for (auto& s : strs) {
    if (seen.find(s) == seen.end()) {
        seen.insert(std::move(s)); // move into set
        result.emplace_back(std::move(s)); // but s is now invalid — don't use it again
    }
}

上面这段有隐患：第二次迭代时 s 可能已被 move。更安全写法是用值捕获或索引访问。

性能临界点：元素少于 10 个时，std::find + vector 查重反而更快

哈希表有常数级开销：建桶、计算 hash、处理冲突。当元素极少（比如配置项、枚举名列表），用 std::vector 当临时 set，配合 std::find，实测可能更快、更省内存、无哈希冲突风险。

• 适用于编译期可知的小规模数据（
• 代码更简单，无头文件依赖（不用 ）
• 注意：std::find 是 O(k) 每次，总复杂度 O(n·k)，k 是已见元素数，所以只适合 k 极小

std::vector vec = {1, 2, 1, 3};
std::vector seen;
std::vector result;

for (int x : vec) {
    if (std::find(seen.begin(), seen.end(), x) == seen.end()) {
        seen.push_back(x);
        result.push_back(x);
    }
}

真正要压榨性能时，别迷信“哈希一定快”——测一下你的典型数据规模再说。