批量修改容器：copy、fill、replace与remove

从生活中的例子引入

想象你有一本作业本，老师要求你：

复制（copy）：把课本上的例题抄到自己的本子上。如果本子太小，抄不下，就需要先准备好足够大的本子，或者用活页纸加页。
填充（fill）：把整张白纸都涂上蓝色背景，用于画画。如果你只涂前几格，就是“填充前几个”。
替换（replace）：把你的名字里的“小明”改成“小红”。如果还有别的“小明”，一起改掉；或者按条件改——比如把所有两字的名字改成“小红”。
删除（remove）：从一张名单上去掉所有请假同学的名字（但格子还在，只是名字被移到了末尾）。要彻底清掉那些格子，还得用橡皮擦掉或撕掉那部分纸。

在编程中，我们经常需要批量修改容器里的数据，比如把全班同学的成绩复制一份、把游戏背包里所有空格子填满药水、把所有怪物名字中的“小怪”换成“精英”、或者从任务列表中移除所有已完成的任务。STL 提供了一组“修改算法”，它们可以通过迭代器对容器中的元素进行操作。注意，这些算法通常不改变容器的大小（除非你使用特殊的 erase 配合），它们只是改变元素的值或位置。

各算法的原理和使用方法

1. copy —— 复制区间

生活例子：你有一张购物清单（源列表），想抄一份给妈妈（目标列表）。如果妈妈的手写本只有 5 行，但你有 10 项，就写不下（越界）。最好先确保她的本子足够大，或者用可以自动加页的活页本（像 back_inserter）。

原理：copy 将源区间（两个迭代器 first, last）中的元素逐个复制到目标迭代器 result 开始的位置。目标区间必须有足够的空间（通常通过 resize 或确保大小足够），否则会越界导致程序崩溃。如果目标空间不够，可以用 back_inserter 或 front_inserter 等插入迭代器自动扩展容器。

时间复杂度：O(n)，n 为源区间长度。
注意：如果源区间和目标区间有重叠（比如把数组的前半部分复制到后半部分），使用 copy_backward（从后向前复制）或 copy_n 可避免覆盖问题。

用法：

#include <algorithm>
#include <vector>
#include <iterator>  // 为了 back_inserter

vector<int> src = {1, 2, 3, 4, 5};          // 源列表
vector<int> dst(5);                         // 目标，提前分配5个位置
copy(src.begin(), src.end(), dst.begin());  // 从 src 开头到结尾，复制到 dst 开头

// 用 back_inserter 动态扩展：目标为空，自动加元素
vector<int> dst2;                           // 目标，初始为空
copy(src.begin(), src.end(), back_inserter(dst2));  // 每复制一个，dst2 就 push_back 一个

常见错误：

忘记给目标容器分配足够空间，导致越界写入。解决方法：要么 resize，要么用 back_inserter。
源和目标迭代器写反，比如 copy(dst.begin(), dst.end(), src.begin()) 可能把目标内容覆盖到源上。

2. fill —— 填充

生活例子：你有一整排铅笔（容器），想把每支笔都涂成红色（统一值）。或者只涂前三支——这就是 fill_n。

原理：fill 将区间 [first, last) 内的所有元素设置为给定的值。它不改变容器大小，只是修改已存在的元素。注意 fill 不会创建新元素，所以容器必须已有至少 last - first 个元素。

时间复杂度：O(n)
同样，fill_n 可以只填充从某个位置开始的前 n 个元素。

用法：

vector<int> v(5);               // 创建5个元素，默认初始化为0
fill(v.begin(), v.end(), 42);   // 全部变为 42

// fill_n 只填充前3个
fill_n(v.begin(), 3, 99);       // 前三个变为 99，后面两个不变（仍为42？注意：上一步已全部42，现在前三个改成99）

常见错误：

用 fill 来“创建”新元素——不行，它只覆盖已有的。如果想生成一整个新容器，可以用 vector<int> v(10, 5) 或 assign。
对空容器（size=0）调用 fill，因为没有元素可覆盖，不会报错但无效果。

3. replace —— 替换

生活例子：老师批改作业，把所有错别字“他”改成“她”（指定值替换）。或者把所有偶数（按条件）改成“偶”字，这就是 replace_if。

原理：replace 将区间内所有等于 old_value 的元素替换为 new_value。replace_if 可以根据条件（一元谓词，返回 true 则替换）替换。

时间复杂度：O(n)
注意：这两个算法都是原地修改，会改变原容器。如果不想修改原容器，可以用 replace_copy 和 replace_copy_if，它们把结果复制到目标区间。

用法：

vector<int> v = {1, 2, 3, 2, 5};
replace(v.begin(), v.end(), 2, 99);  // 所有等于2的元素变成99

// replace_if 使用 lambda 表达式判断偶数，替换为0
replace_if(v.begin(), v.end(),
           [](int x){ return x % 2 == 0; },  // 如果 x 是偶数
           0);                                // 则替换成0

常见错误：

混淆 replace 和 replace_copy，以为 replace 也会复制一份到新容器。
在使用 replace_if 的谓词时，忘记写返回值（必须返回 bool 类型）。

4. remove —— 移除（逻辑删除）

生活例子：班级点名册上，老师要把所有请假的同学名字划掉，但格子还在，只是把没请假的同学往前挪，空出来的格子留在末尾。最后，老师撕掉末尾空白的部分，才是真正的删除。

原理：remove 并非真正将元素从容器中删除，而是将不等于给定值的元素搬运到容器前面，然后返回新逻辑结尾的迭代器。容器的大小不变，剩余的元素（从返回位置到 end()）处于“有效但未指定”的状态。通常要配合容器的 erase 方法真正删除（即“erase-remove 惯用法”）。类似地有 remove_if。

时间复杂度：O(n)
为什么需要两步？因为 remove 是算法，只处理迭代器，不知道容器本身（比如 vector 的内部大小管理），所以无法缩小容器。而 erase 是容器的成员函数，可以真正释放空间。

用法：

vector<int> v = {1, 2, 3, 2, 5};
// 第一步：逻辑删除所有值为2的元素
auto new_end = remove(v.begin(), v.end(), 2); // new_end 指向新的逻辑结尾
// 第二步：用 erase 真正删除从 new_end 到 v.end() 的部分
v.erase(new_end, v.end());  // v 变为 {1, 3, 5}

常见错误：

只调 remove 不调 erase，结果 v.size() 还是 5，打印时会把后面未指定的元素也打印出来（通常是没有意义的旧值）。这会导致 bug 和困惑。
忘记保存 remove 的返回值，直接用 v.erase(v.end()-??? 或胡乱猜测。
以为 remove 会改变迭代器有效性：实际上在 remove 期间，原迭代器仍然有效，但容器内容移动了，所以建议用返回值。

C++ 完整代码实现

下面的代码演示了所有四种算法，并添加了中文注释，方便理解。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>  // back_inserter

using namespace std;

// 辅助函数：打印容器内容
void print(const string& msg, const vector<int>& v) {
    cout << msg;
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {
    // 1. copy —— 复制
    vector<int> src = {10, 20, 30, 40, 50};        // 源向量
    vector<int> dst(5);                            // 目标向量，大小必须至少 5
    copy(src.begin(), src.end(), dst.begin());     // 把 src 复制到 dst
    print("copy 目标: ", dst);                     // 输出：10 20 30 40 50

    // 使用 back_inserter 动态增长（目标初始为空）
    vector<int> dst2;                              // 空向量
    copy(src.begin(), src.end(), back_inserter(dst2)); // 每复制一个元素，dst2 自动 push_back
    print("copy + back_inserter: ", dst2);         // 输出：10 20 30 40 50

    // 2. fill —— 填充
    vector<int> filled(6);                         // 创建 6 个元素，默认值为 0
    fill(filled.begin(), filled.end(), 7);         // 全部改为 7
    print("fill 7: ", filled);                     // 输出：7 7 7 7 7 7

    // fill_n 只填充前 3 个元素
    fill_n(filled.begin(), 3, 99);                 // 前三个改为 99
    print("fill_n 前3个为99: ", filled);           // 输出：99 99 99 7 7 7

    // 3. replace —— 替换
    vector<int> rep = {1, 2, 3, 2, 4, 2, 5};      // 原始数据
    replace(rep.begin(), rep.end(), 2, 100);        // 所有等于2的替换为100
    print("replace 2->100: ", rep);                // 输出：1 100 3 100 4 100 5

    // replace_if: 将所有偶数替换为 -1
    replace_if(rep.begin(), rep.end(),
               [](int x){ return x % 2 == 0; },    // 谓词：判断偶数
               -1);                                 // 新值
    print("replace_if 偶数-> -1: ", rep);          // 输出：1 -1 3 -1 -1 -1 5? 其中 100 是偶数也被替换

    // 4. remove —— 移除（逻辑删除）配合 erase
    vector<int> rem = {3, 1, 4, 1, 5, 9, 2, 6};   // 原始数据
    cout << "原 rem: ";
    for (int x : rem) cout << x << " ";
    cout << endl;

    // 逻辑删除所有值为1的元素
    auto new_end = remove(rem.begin(), rem.end(), 1);
    // 真正删除
    rem.erase(new_end, rem.end());
    cout << "remove+erase 后: ";
    for (int x : rem) cout << x << " ";
    cout << endl;  // 输出：3 4 5 9 2 6

    // 使用 remove_if 移除所有奇数
    vector<int> rem2 = {1, 2, 3, 4, 5, 6};
    auto it = remove_if(rem2.begin(), rem2.end(),
                        [](int x){ return x % 2 != 0; }); // 移除奇数
    rem2.erase(it, rem2.end());
    print("remove_if 奇数: ", rem2);               // 输出：2 4 6

    return 0;
}

Python 等价功能实现

Python 中列表提供了类似的内置方法，但风格不同。注意 copy 可用切片或 list() 复制，fill 可以用乘法或列表推导，replace 可以用列表推导式（条件表达式），remove 要删除所有匹配项需用推导式或 filter。Python 的 list.remove(x) 只删除第一个匹配项。

def print_list(msg, lst):
    print(msg, lst)

# 1. copy —— 复制
src = [10, 20, 30, 40, 50]
dst = src.copy()  # 或者 dst = list(src)
print_list("copy 目标: ", dst)

# 使用切片复制
dst2 = src[:]
print_list("切片复制: ", dst2)

# 2. fill —— 填充
filled = [7] * 6  # 创建包含6个7的列表
print_list("fill 7: ", filled)

# 修改前3个为99
filled[:3] = [99, 99, 99]  # 注意这需要知道长度，也可以用 for 循环
print_list("前3个改为99: ", filled)

# 3. replace —— 替换
rep = [1, 2, 3, 2, 4, 2, 5]
# 将所有2替换为100
rep = [100 if x == 2 else x for x in rep]  # 列表推导式
print_list("replace 2->100: ", rep)

# replace_if: 将所有偶数替换为 -1
rep = [-1 if x % 2 == 0 else x for x in rep]
print_list("replace_if 偶数-> -1: ", rep)

# 4. remove —— 移除所有值为1的元素
rem = [3, 1, 4, 1, 5, 9, 2, 6]
print("原 rem:", rem)
# 用列表推导式生成新列表（相当于 remove+erase 的合体）
rem = [x for x in rem if x != 1]
print("remove 1 后:", rem)  # [3, 4, 5, 9, 2, 6]

# 移除所有奇数
rem2 = [1, 2, 3, 4, 5, 6]
rem2 = [x for x in rem2 if x % 2 == 0]  # 保留偶数，即移除奇数
print("remove_if 奇数后:", rem2)

# 注意：Python 的 list 也有 remove() 方法，但只删除第一个匹配项
lst = [1, 2, 1, 3]
lst.remove(1)  # 删除第一个1，列表变为 [2, 1, 3]
print("list.remove 第一个1:", lst)

常见错误和注意事项

copy 目标空间不足：C++ 中如果目标容器大小小于源区间，程序会越界写入，结果是未定义的（可能崩溃或数据损坏）。使用 back_inserter 可以避免。
fill 不能增加元素：它只修改已有的元素。如果想增加新元素（比如插入），请用 insert 或 fill_n 配合插入迭代器。
replace 是原地修改：如果你需要保留原容器不变并生成新的替换结果，请用 replace_copy。例如：
```
vector<int> src = {1,2,3,2,5};
vector<int> dst(src.size());
replace_copy(src.begin(), src.end(), dst.begin(), 2, 99);
```
remove 后必须配合 erase：这是“erase-remove 惯用法”。忘记调用 erase 会导致容器中残留无效元素（比如使用 size() 或遍历时）。
重叠区间问题：copy 如果源和目标区域有重叠（比如同一容器的前后部分），建议使用 copy_backward（从后向前复制）或 copy_if 等。例如：
```
vector<int> v = {1,2,3,4,5};
copy(v.begin(), v.begin()+3, v.begin()+2);  // 错误：重叠导致数据覆盖
// 正确：
copy_backward(v.begin(), v.begin()+3, v.end());
```
Python 中 list.remove(x) 只删除第一个匹配：需要删除全部时请用列表推导式或 while x in list: list.remove(x)（效率低）。
算法不检查容器类型：copy 等算法只通过迭代器操作，如果目标迭代器是输出迭代器（如给 ostream_iterator 写入），可以输出到屏幕或文件。例如：
```
vector<int> v = {1,2,3};
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); // 输出：1 2 3
```
性能：这些算法都是 O(n)，对于长列表，Python 的列表推导式比手动循环快；C++ 的 STL 算法通常比手写循环优化更好（特别是 remove 使用移动语义）。

修改算法：copy、fill、replace与remove

批量修改容器：copy、fill、replace与remove

从生活中的例子引入

各算法的原理和使用方法

1. copy —— 复制区间

2. fill —— 填充

3. replace —— 替换

4. remove —— 移除（逻辑删除）

C++ 完整代码实现

Python 等价功能实现

常见错误和注意事项

相关指引

例题精讲