变异算法

定义与作用

变异算法（modifying algorithms）修改容器中元素的内容或顺序，包括拷贝、移动、变换、填充、替换和移除。核心原则：算法不直接改变容器大小（需要配合 erase）。

#include <algorithm>

std::vector<int> src{1, 2, 3, 4, 5};
std::vector<int> dst(5);
std::copy(src.begin(), src.end(), dst.begin());  // 拷贝
std::transform(src.begin(), src.end(), dst.begin(),
               [](int x) { return x * 2; });      // 变换

核心原理

变异算法分类

remove-erase 惯用法（核心）

完整示例

示例一：飞翔科技数据清洗管道

场景说明：高英用变异算法清洗飞翔科技的用户行为数据。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <random>

struct UserAction {
    std::string userId;
    std::string action;
    double duration;  // 秒
};

void printActions(const std::string& title, const std::vector<UserAction>& acts) {
    std::cout << title << " (" << acts.size() << " 条):\n";
    for (const auto& a : acts)
        std::cout << "  " << a.userId << " | " << a.action
                  << " | " << a.duration << "s\n";
}

int main() {
    std::vector<UserAction> actions = {
        {"大翔", "登录", 2.5},
        {"",     "浏览", 0.0},      // 无效数据
        {"白歌", "登录", 3.0},
        {"小崔", "提交代码", 12.5},
        {"高英", "导出报表", 8.0},
        {"",     "",      0.0},      // 无效数据
        {"黄俪", "登录", 1.5},
        {"小崔", "登录",     0.5},
    };

    printActions("原始数据", actions);

    // 1. 拷贝：提取登录行为到另一个容器
    std::vector<UserAction> logins;
    std::copy_if(actions.begin(), actions.end(),
                 std::back_inserter(logins),
                 [](const UserAction& a) { return a.action == "登录"; });
    printActions("\n登录行为 (copy_if)", logins);

    // 2. 变换：提取用户 ID 列表
    std::vector<std::string> userIds;
    std::transform(actions.begin(), actions.end(),
                   std::back_inserter(userIds),
                   [](const UserAction& a) { return a.userId; });
    std::cout << "\n用户ID列表: ";
    for (const auto& id : userIds) std::cout << "'" << id << "' ";

    // 3. 替换：将空用户 ID 替换为 "匿名"
    std::replace_if(actions.begin(), actions.end(),
        [](const UserAction& a) { return a.userId.empty(); },
        UserAction{"匿名用户", "匿名行为", 0.0});

    // 4. 移除：过滤掉时长为 0 的无效数据（remove-erase 惯用法）
    actions.erase(
        std::remove_if(actions.begin(), actions.end(),
            [](const UserAction& a) { return a.duration <= 0.0; }),
        actions.end());
    printActions("\n清洗后数据 (remove_if + erase)", actions);

    // 5. 去重：按用户 ID 去重（先排序、再 unique）
    std::sort(actions.begin(), actions.end(),
        [](const UserAction& a, const UserAction& b) {
            return a.userId < b.userId;
        });
    actions.erase(
        std::unique(actions.begin(), actions.end(),
            [](const UserAction& a, const UserAction& b) {
                return a.userId == b.userId;
            }),
        actions.end());
    printActions("\n去重后数据 (sort + unique + erase)", actions);

    // 6. 翻转和平移
    std::reverse(actions.begin(), actions.end());
    std::cout << "\n翻转后首条: " << actions.front().userId
              << " | " << actions.front().action << "\n";
}

预期输出：

原始数据 (8 条):
  大翔 | 登录 | 2.5s
   | 浏览 | 0s
  白歌 | 登录 | 3s
  小崔 | 提交代码 | 12.5s
  高英 | 导出报表 | 8s
   |  | 0s
  黄俪 | 登录 | 1.5s
  小崔 | 登录 | 0.5s

登录行为 (copy_if) (3 条):
  大翔 | 登录 | 2.5s
  白歌 | 登录 | 3s
  黄俪 | 登录 | 1.5s

用户ID列表: '大翔' '' '白歌' '小崔' '高英' '' '黄俪' '小崔' 

清洗后数据 (remove_if + erase) (6 条):
  大翔 | 登录 | 2.5s
  小崔 | 提交代码 | 12.5s
  白歌 | 登录 | 3s
  小崔 | 提交代码 | 12.5s
  高英 | 导出报表 | 8s
  黄俪 | 登录 | 1.5s

去重后数据 (sort + unique + erase) (4 条):
  大翔 | 登录 | 2.5s
  白歌 | 登录 | 3s
  高英 | 导出报表 | 8s
  黄俪 | 登录 | 1.5s

翻转后首条: 黄俪 | 登录

逐段分析：

  • std::back_inserter：输出迭代器适配器，调用 push_back 动态扩展目标容器
  • remove_if 将不需要的元素"移到末尾"，返回新的逻辑末尾迭代器
  • erase(new_end, end()) 真正删除元素，两者组合即为 remove-erase idiom
  • unique 去重需要先排序，类似 remove 只"标记"重复元素到末尾
  • std::reverse 原地翻转元素顺序

示例二：shuffle 抽奖系统

场景说明：杨英用 shuffle 实现飞翔科技年会抽奖。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>

int main() {
    std::vector<std::string> participants = {
        "大翔", "白歌", "小崔", "黄俪", "李眉",
        "孔蓝", "赵鸣", "孙鹤", "高英", "杨英",
        "朱璐", "林鸥"
    };

    std::cout << "=== 飞翔科技 2026 年会抽奖 ===\n\n";

    // 使用随机设备生成真随机种子
    std::random_device rd;
    std::mt19937 gen(rd());

    // 一等奖：1名
    std::shuffle(participants.begin(), participants.end(), gen);
    std::cout << "一等奖: " << participants[0] << "\n";

    // 二等奖：2名
    std::cout << "二等奖: " << participants[1] << ", " << participants[2] << "\n";

    // 三等奖：3名
    std::cout << "三等奖: " << participants[3] << ", "
              << participants[4] << ", " << participants[5] << "\n";

    // generate_n：生成随机编号
    std::vector<int> ticketNumbers(5);
    std::generate_n(ticketNumbers.begin(), 5,
        [&gen, dist = std::uniform_int_distribution<>(1000, 9999)]() mutable {
            return dist(gen);
        });

    std::cout << "\n抽奖券编号: ";
    for (int n : ticketNumbers) std::cout << n << " ";
    std::cout << "\n";
}

预期输出（示例，每运行结果不同）：

=== 飞翔科技 2026 年会抽奖 ===

一等奖: 林鸥
二等奖: 大翔, 朱璐
三等奖: 杨英, 白歌, 孔蓝

抽奖券编号: 7382 4921 8803 2156 6047

逐段分析：

  • shuffle（C++11）替代已被弃用的 random_shuffle，需要提供随机数引擎
  • std::random_device 提供真随机种子（如果硬件支持）
  • generate_n 用函数对象填充指定数量的元素
  • uniform_int_distribution 控制随机数分布范围

易错场景与面试考点

易错场景

1. remove 后不 erase

std::vector<int> v{1, 2, 2, 3, 2, 4};
auto newEnd = std::remove(v.begin(), v.end(), 2);
// v 现在是 {1, 3, 4, ?, ?, ?}，大小仍是 6！
v.erase(newEnd, v.end());  // 必须 erase

2. copy 时目标容量不足

std::vector<int> src{1, 2, 3, 4, 5};
std::vector<int> dst(3);  // 只有 3 个元素空间
// std::copy(src.begin(), src.end(), dst.begin());  // ❌ 越界
std::copy(src.begin(), src.end(), std::back_inserter(dst));  // ✅

3. unique 前没排序

std::vector<int> v{1, 3, 2, 1, 3};
auto it = std::unique(v.begin(), v.end());  // 只移除相邻重复！结果是 {1,3,2,1,3}
// 正确做法：先 sort 再 unique

面试考点

考点要点
remove-erase idiom标准删除模式，两步完成
copy vs copy_ifcopy_if C++11 引入，按条件拷贝
transform一元/二元变换，可改变输出类型
shuffle vs random_shuffleC++11 shuffle 使用现代随机引擎
unique 前提必须先排序，只移除相邻重复
back_inserter输出迭代器，调用 push_back
move 算法C++11，将元素移动到目标区间