Chapter 27: Modifying Algorithms

修改类算法处理的核心问题，是在已有 iterator range 上完成写入、搬运、替换、压缩或重排，并把“算法能改什么”和“容器负责什么”分开。读完本章后，读者应能判断一个算法调用会写入哪些位置、是否需要预先准备目标区间、是否会改变容器长度、是否会改变元素顺序，以及异常或重叠输入出现时对象会处在什么状态。

本章贯穿一个事件缓冲 std::vector<Event>。输入缓冲里混有有效事件、无效事件、需要归一化的字符串字段和待随机抽样的数据。算法层只看 [first, last) 和目标 iterator；容器层负责容量、生命周期、erase、iterator 失效和对象销毁。这个分层决定了修改类算法的第一条判断：算法可以通过 iterator 写元素值，容器结构变化要么由 output iterator 触发，要么由容器成员函数完成。

#include <algorithm>
#include <cctype>
#include <iterator>
#include <random>
#include <string>
#include <utility>
#include <vector>

struct Event {
    int id{};
    int priority{};
    bool valid{};
    std::string tag;
};

bool is_valid(const Event& event) {
    return event.valid && !event.tag.empty();
}

Event normalize(Event event) {
    for (char& ch : event.tag) {
        ch = static_cast<char>(std::tolower(static_cast<unsigned char>(ch)));
    }
    return event;
}

void compact_and_prepare(std::vector<Event>& events) {
    std::vector<Event> scratch;
    scratch.reserve(events.size());

    std::copy_if(events.begin(), events.end(), std::back_inserter(scratch), is_valid);
    std::transform(scratch.begin(), scratch.end(), scratch.begin(), normalize);

    auto logical_end = std::remove_if(
        scratch.begin(), scratch.end(),
        [](const Event& event) { return event.priority < 0; }
    );
    scratch.erase(logical_end, scratch.end());

    if (!scratch.empty()) {
        auto middle = scratch.size() == 1 ? scratch.end() : scratch.begin() + 1;
        std::rotate(scratch.begin(), middle, scratch.end());
    }

    events = std::move(scratch);
}

这段代码展示了修改类算法的四类写入路径：copy_if 通过 std::back_inserter 让容器追加新元素；transform 原地覆盖已有元素；remove_if 把保留元素压到前段并返回新的逻辑末尾；rotate 把首个事件轮转到尾部。贯穿材料的关键点在于：算法每次只拿到 iterator 和可调用对象，它没有直接看到 std::vector 的 size、capacity 或 allocator。容器长度变化出现在 back_inserter 和 erase 这两个容器相关入口。

下面这张图把本章的判断路径固定下来。它覆盖 copy、fill、remove、reverse、rotate 和 shuffle 这类算法的共同入口：先看算法需要写哪里，再看目标区间和容器结构是否匹配，最后处理重叠、生命周期和异常边界。

图中的“写入目标”是本章最稳定的阅读入口。std::copy 之类算法写入目标区间，目标容量不足会导致越界写入；std::fill 之类算法覆盖已有位置；std::remove 之类算法把同一段区间内部的保留元素向前移动；std::reverse 和 std::rotate 通过交换或移动改变相对顺序。标准库参考资料把这些算法归入 modifying sequence operations，并分别给出写入、复杂度、重叠和 iterator 要求；本文后续解释采用这些标准语义与常见实现形状，不声称对应某个本地 STL 文件或内部符号。

27.1 copy、copy_if、move 与 transform

copy、copy_if、move 和 transform 的共同结构是“读一个或两个输入区间，向输出 iterator 写结果”。它们的区别在于写入值从哪里来：copy 写入源元素的拷贝，copy_if 先用谓词筛选，move 写入源元素的移动结果，transform 写入可调用对象的返回值。判断这组算法时，第一步看输出 iterator 指向已有元素，还是像 std::back_inserter 一样把赋值转成容器插入。

std::copy 的接口语义可以直接读成一个循环：从 first 到 last 逐个解引用源 iterator，然后对 d_first 所在位置赋值，再同时推进两个 iterator。cppreference 的 std::copy 页面明确给出 [first, last) 到 d_first 开始的目标区间写入关系，并说明目标起点落在源区间内部时会形成未定义行为。这个规则解释了为什么算法调用前必须先准备目标位置。

std::vector<Event> source{{1, 10, true, "A"}, {2, 0, true, "B"}};
std::vector<Event> target(source.size());

std::copy(source.begin(), source.end(), target.begin());

这段代码成立的前提是 target 已经有 source.size() 个有效元素。target.begin() 指向第一个可赋值对象，后续每次 ++d_first 都会落在一个已经存在的 Event 上。std::copy 在这里执行的是赋值操作；它没有给 target 扩容，也没有在未初始化存储上构造对象。std::vector<Event> target; std::copy(source.begin(), source.end(), target.begin()); 会把 target.begin() 当成可写位置使用，空 vector 没有任何有效元素，写入路径直接越界。

追加式写入要把普通 iterator 换成 output iterator adapter。std::back_inserter(target) 返回的对象在赋值时调用 target.push_back(value)，容器在这个入口完成容量检查、元素构造、可能的扩容和 iterator 失效。

std::vector<Event> target;
target.reserve(source.size());

std::copy(source.begin(), source.end(), std::back_inserter(target));

这个版本把“写入已有元素”改成“追加新元素”。算法层仍然只做 *out = value，但 out 的赋值运算被 adapter 改写成容器成员调用。reserve 只降低扩容概率，真正增加 size 的动作来自 push_back。因此，分析 output iterator 时要看它的赋值语义，普通 iterator 表示覆盖已有对象，insert iterator 表示转入容器插入路径。

copy_if 在 copy 的基础上增加谓词判断。谓词接收源元素，返回 true 的元素被写入目标区间，返回 false 的元素只推进输入 iterator。它保持被复制元素的相对顺序，所以可用于从事件缓冲中提取有效事件。

std::vector<Event> valid_events;
valid_events.reserve(events.size());

std::copy_if(events.begin(), events.end(), std::back_inserter(valid_events), is_valid);

这段代码的输出长度在调用前无法只靠区间长度得到，因为谓词决定最终写入次数。使用 back_inserter 可以把“不确定输出数量”交给容器增长路径；使用预分配数组时，则要么先计算数量，要么接受多余默认元素并额外维护写入末尾。copy_if 的返回值是目标区间的 one-past-last iterator，保留它可以知道实际写入了多少元素。

std::move 在算法库中是 range move algorithm，和类型转换工具 std::move(obj) 名字相同，语义层级不同。range move algorithm 逐个读取源元素，并把 std::move(*first) 的结果赋给目标位置。源区间中的对象仍然处在有效生命周期内，后续可析构、可重新赋值；具体值满足 moved-from 状态的类型约定。

std::vector<Event> old_events{{1, 10, true, "A"}, {2, 0, true, "B"}};
std::vector<Event> new_events(old_events.size());

std::move(old_events.begin(), old_events.end(), new_events.begin());

这段代码结束后，new_events 获得移动赋值后的元素值，old_events 的 size 保持不变。对 std::string 成员来说，移动后字符串仍然是有效对象，内容由类型保证决定；工程代码应把源对象当作待销毁或待重新赋值的对象处理。这个判断比“移动后还能不能读取原值”更稳定，因为标准库类型只承诺 moved-from 对象有效，具体内容通常没有业务意义。

std::transform 把“搬运元素”改成“计算后写入”。一元版本从一个输入区间读元素，二元版本从两个输入区间读对应元素，结果写到目标区间。transform 允许 d_first 等于输入起点，这使它适合原地归一化。

std::transform(events.begin(), events.end(), events.begin(), normalize);

这里 normalize 接收一个 Event 值并返回修改后的 Event，算法把返回值赋回原位置。原地 transform 的安全边界在可调用对象上：可调用对象应只根据当前输入元素生成结果，不在内部插入、删除容器元素，也不让 iterator 失效。标准参考资料对 std::transform 的说明强调，可调用对象若让相关 range 的 iterator 失效或修改相关 range，会进入未定义行为；这条规则把 transform 的职责限定在逐元素计算和结果写入上。

transform 还有一个容易影响工程判断的细节：它适合表达“每个位置的结果只依赖当前位置输入”的变换。如果变换需要严格的访问顺序、副作用累积或跨元素状态更新，应改用显式循环或 std::for_each 并把顺序依赖写清楚。算法接口虽然像循环，标准语义给实现保留了优化空间，尤其在 execution policy 重载存在时，副作用顺序更需要独立审查。

这组算法的最小判断顺序是：先确定输入区间长度，再确定输出 iterator 的赋值语义；接着判断目标是否已有足够元素，或是否通过 inserter 进入容器插入；然后检查源区间和目标区间是否重叠；最后检查元素赋值、移动赋值或变换函数抛异常后的部分写入状态。它们通常提供逐元素进度，不提供整段事务提交。

27.2 fill、generate 与 value production

fill 和 generate 的共同目标是产生新值并覆盖一段已有位置。它们关注输出 range，而输入不来自另一个 iterator range：fill 使用同一个给定值反复赋值，generate 每次调用 generator 取得一个新值。它们改变元素值，容器长度保持不变。

std::fill(first, last, value) 可以读成“把 [first, last) 中每个已有元素赋值为 value”。cppreference 的 std::fill 页面把它描述为对 range 中所有元素赋给定值。这里的“已有元素”是生命周期边界：fill 处理的是可解引用、可赋值的位置，不能把空容器填出元素。

std::vector<int> scores(5);
std::fill(scores.begin(), scores.end(), 100);

这段代码中，scores(5) 已经构造了 5 个 int 对象，fill 只是把它们覆盖成 100。如果写成 std::vector<int> scores; std::fill(scores.begin(), scores.end(), 100);，算法会处理一个空区间，结果仍然为空。需要创建 5 个元素时，应由构造函数、resize、assign、insert 或 std::fill_n(std::back_inserter(scores), 5, 100) 这类路径完成。

fill 使用同一个值对象作为赋值来源。对 int 这样的值类型，读者很少感知差异；对拥有资源或可变状态的类型，理解“同一个 value 被复制赋值多次”可以解释性能和别名风险。容器中的每个元素仍然是独立对象，赋值运算符决定资源如何释放和重建。

struct Payload {
    std::string data;
};

std::vector<Payload> payloads(3);
Payload sample{"ready"};
std::fill(payloads.begin(), payloads.end(), sample);

这段代码会对三个已存在的 Payload 分别执行赋值。sample 本身不会搬进第一个元素后失效，因为 fill 使用的是拷贝赋值路径。若赋值运算抛异常，前面已经被赋值的位置保留新状态，后面的元素保持调用前状态；算法层没有统一回滚点。

std::generate(first, last, gen) 每次写入前调用一次 generator。generator 的返回值被赋给当前位置。它适合生成递增 id、随机数、测试数据或从外部状态读取下一项。cppreference 的 std::generate 页面给出的语义是把 generator 产生的值赋给 range 中的每个元素。

int next_id = 1;
std::vector<Event> events(4);

std::generate(events.begin(), events.end(), [&] {
    Event event;
    event.id = next_id++;
    event.priority = 0;
    event.valid = true;
    event.tag = "new";
    return event;
});

这段代码的 generator 捕获 next_id 并在每次调用时推进状态。算法只要求 generator 可调用并产生可赋给目标元素的结果；generator 的内部状态由调用方负责。使用随机数 generator 时也一样，随机引擎对象通常应在算法外部创建并通过引用捕获，保证多次调用沿着同一条随机序列推进。

generate_n 和 fill_n 把终止条件从 [first, last) 改成“从 first 开始写 n 次”。这两个算法常和 inserter 配合，用来在空容器中追加固定数量元素。

std::vector<Event> events;
events.reserve(4);

int next_id = 1;
std::generate_n(std::back_inserter(events), 4, [&] {
    return Event{next_id++, 0, true, "generated"};
});

这里 std::back_inserter(events) 让每次赋值变成一次 push_back。容器在每次插入时创建新元素，所以 size 从 0 增长到 4。这个例子和上一段 std::vector<Event> events(4) 的区别在生命周期入口：前者由 push_back 构造元素，后者先默认构造元素再赋值覆盖。

这一节的判断顺序是：先看算法是 range 版本还是 _n 版本；再看输出 iterator 是普通 iterator 还是 inserter；然后判断写入动作是赋值已有元素还是插入新元素；最后审查 value 或 generator 的成本、异常和状态依赖。fill 强调同一值的重复赋值，generate 强调每个位置从 generator 取得新值。

27.3 remove、remove_if 与 replace 系列

remove 和 remove_if 的工程意义在于“逻辑删除”。算法扫描 [first, last)，把应保留的元素向前移动，返回新的 logical end。它们不会调用容器的 erase，所以容器 size 保持不变；真正缩短容器需要后续成员函数完成。

std::vector<int> numbers{1, 0, 2, 0, 3, 0};

auto logical_end = std::remove(numbers.begin(), numbers.end(), 0);

调用结束后，[numbers.begin(), logical_end) 保存被保留的元素，顺序为 1, 2, 3。[logical_end, numbers.end()) 仍然是 vector 中的有效元素位置，但这些位置的值只应当作待覆盖或待擦除的尾部。std::remove 的名字容易让人误判，因为它没有容器所有权，也没有缩短容器的接口。它能做的是在同一段 range 内重新安排元素值。

常见实现形状可以用教学简化代码表示。这个代码只展示核心路径，标准库实现会处理更多 iterator、constexpr、execution policy 或优化细节。

template<class ForwardIt, class T>
ForwardIt teaching_remove(ForwardIt first, ForwardIt last, const T& value) {
    first = std::find(first, last, value);
    if (first == last) {
        return first;
    }

    for (ForwardIt read = std::next(first); read != last; ++read) {
        if (!(*read == value)) {
            *first = std::move(*read);
            ++first;
        }
    }
    return first;
}

这段简化代码说明两个事实。第一，remove 需要 forward iterator，因为它要保留一个写入位置 first，同时继续向后读。第二，保留元素通过移动赋值或等价赋值路径前移，尾部对象仍然存在。对象生命周期没有结束；只有后续 erase 才会销毁尾部元素并改变容器 size。

remove_if 把“等于某个值”换成“满足谓词”。在事件缓冲中，负优先级表示待丢弃事件，remove_if 可以先形成有效前缀。

auto logical_end = std::remove_if(
    events.begin(), events.end(),
    [](const Event& event) { return event.priority < 0; }
);

谓词返回 true 的元素进入尾部待擦除区，返回 false 的元素被压到前段。保留元素相对顺序保持稳定，这使 remove_if 适合“过滤但保留原顺序”的业务场景。异常边界来自谓词、比较、移动赋值或析构后的 erase；如果谓词抛异常，已经完成的移动赋值不会被算法统一撤销。

replace 系列处理的是值替换，删除语义应交给 remove、remove_if 或容器 erase 路径。replace(first, last, old_value, new_value) 在原区间内覆盖匹配元素；replace_if 用谓词决定位置；replace_copy 和 replace_copy_if 把替换后的结果写入另一个输出区间，源区间保持调用前的值语义。cppreference 的 std::replace 页面将它们归在 transformation operations 下，这个分类强调它们的结果是“某些位置的值发生变化”。

std::replace_if(
    events.begin(), events.end(),
    [](const Event& event) { return event.tag == "unknown"; },
    Event{0, 0, false, "dropped"}
);

这段代码直接覆盖匹配位置，vector 长度和元素顺序都不变。若业务语义是“把 unknown 事件删除”，正确工具是 remove_if 后接 erase，或 C++20 的 std::erase_if。如果业务语义是“保留位置但改成占位事件”，replace_if 正好表达这个需求。

replace_copy 适合保留原始输入，同时产生清洗后的输出版本。

std::vector<Event> sanitized;
sanitized.reserve(events.size());

std::replace_copy_if(
    events.begin(), events.end(),
    std::back_inserter(sanitized),
    [](const Event& event) { return event.tag.empty(); },
    Event{0, 0, false, "missing-tag"}
);

这里的输出长度等于输入长度，因为每个输入元素都会产生一个输出元素。区别只在匹配位置写 new_value，其他位置写原值拷贝。和 copy_if 相比，replace_copy_if 是一对一映射；和 remove_if 相比，它没有压缩区间。

remove 还有一个别名边界。算法参数 value 通常以引用形式传入，如果传入的是区间内部某个元素的引用，并且该元素在压缩过程中被覆盖，后续比较使用的 value 也可能随之变化。工程代码应把待删除值先复制到独立对象，再传给 remove。

std::vector<int> data{1, 2, 1, 3};
int value = data.front();

auto logical_end = std::remove(data.begin(), data.end(), value);

value 是独立 int 对象，后续元素移动不会改变比较基准。对复杂对象也是同样判断：删除条件应独立于被压缩区间中的可变位置，或者直接使用捕获稳定值的 remove_if 谓词。

27.4 reverse、rotate 与 shuffle

reverse、rotate 和 shuffle 处理的是顺序重排。它们不创建新逻辑元素，也不删除元素；它们通过交换、移动或赋值改变 range 内元素的排列。判断这组算法时，重点从“目标区间容量”转向“iterator 能力、元素可交换性、顺序语义和引用观察结果”。

std::reverse(first, last) 把 [first, last) 中的元素顺序反转。它需要 bidirectional iterator，因为算法要从两端向中间推进并交换对应位置。std::vector、std::deque、std::list 都能提供这种能力；std::forward_list 的 iterator 只能向前走，无法满足通用 std::reverse 的要求。

std::vector<int> values{1, 2, 3, 4, 5};
std::reverse(values.begin(), values.end());

调用后 values 变成 5, 4, 3, 2, 1。vector 的存储容量、size 和元素对象数量不变。已有 iterator 仍指向同一位置，但该位置上的值可能已经与别的位置交换。这个区别在调试中很常见：iterator 有效性和“它观察到的业务值是否仍是原来的值”属于两个问题。

对 std::list，通用 std::reverse 通过 iterator 交换元素值；成员函数 list::reverse 可以重连节点。二者都能得到反转顺序，但对象移动成本、引用观察和实现路径不同。对节点式容器，优先检查是否存在容器成员算法，因为成员函数能利用节点结构，通用算法只能通过 iterator 看到元素值。

std::rotate(first, middle, last) 把 [first, middle) 放到后面，把 [middle, last) 放到前面。调用结果的第一个元素来自旧的 middle。这个算法适合把一段前缀移动到尾部，或把某个迭代器指向的元素转成新区间开头。

std::vector<int> values{1, 2, 3, 4, 5};
std::rotate(values.begin(), values.begin() + 2, values.end());
// values: 3 4 5 1 2

rotate 的三个 iterator 必须来自同一段有效 range，并满足 first <= middle <= last 的区间关系。标准接口要求至少 forward iterator；常见实现会根据 iterator 能力选择不同策略，例如三次 reverse、循环交换或块交换。工程判断无需绑定某一种实现，关键是知道它会在同一段 range 内重排元素值，并返回新位置相关 iterator。

rotate 能替代某些手写移动循环。比如要把 vector 中已经分区的“低优先级事件”移到前面，可以先找到分界点，再 rotate。它比逐个 erase/insert 更清楚地表达“只重排已有元素”。

auto middle = std::find_if(events.begin(), events.end(), [](const Event& event) {
    return event.priority < 10;
});

std::rotate(events.begin(), middle, events.end());

这段代码的前提是区间已经满足业务上的前后分段，例如前段是高优先级，后段是低优先级。若输入没有分段，rotate 只会按给定 middle 做机械重排，不会替调用方寻找所有低优先级元素。需要按谓词分组时，应使用 partition 或 stable_partition。

std::shuffle 使用随机数引擎打乱随机访问区间。它要求 random access iterator，并要求调用方提供 uniform random bit generator。C++11 引入 shuffle；旧的 random_shuffle 已在 C++17 移除，现代代码应使用显式随机引擎，便于复现实验和控制随机源。cppreference 的 std::shuffle 页面记录了 random_shuffle 和 shuffle 的版本边界。

std::vector<int> sample{1, 2, 3, 4, 5};
std::mt19937 rng{42};

std::shuffle(sample.begin(), sample.end(), rng);

固定种子 42 可以让测试结果可复现；生产系统通常把随机源和种子策略放在调用层设计。shuffle 改变元素顺序，元素数量和容器容量不变。由于它要求随机访问 iterator，std::list 不能直接使用通用 shuffle；如果确实要打乱链表，常见做法是先把 iterator 或值收集到 vector，再根据成本选择重建链表或处理索引映射。

这组算法的判断顺序是：先确认 iterator category 是否满足算法要求；再确认元素是否可交换、可移动或可赋值；然后判断重排后已有 iterator、reference 和业务 id 的观察结果；最后确认算法是否能表达业务分组语义。reverse 表达完全反转，rotate 表达按分界点旋转，shuffle 表达随机排列，它们都不承担查找、筛选或删除责任。

27.5 remove-erase idiom 与重叠边界

remove-erase idiom 把逻辑删除和物理删除分成两步：先用 remove 或 remove_if 得到 logical end，再调用容器的 erase 缩短实际范围。它是理解修改类算法和容器责任边界的集中案例。

std::vector<Event> events{{1, 10, true, "A"}, {2, -1, false, "B"}};

auto logical_end = std::remove_if(
    events.begin(), events.end(),
    [](const Event& event) { return !is_valid(event); }
);

events.erase(logical_end, events.end());

第一步结束后，events.size() 没有改变，保留元素位于 [begin, logical_end)。第二步才让 vector 销毁 [logical_end, end) 中的对象，并把 size 缩短。对 vector 来说，erase 会使被擦除位置及其后的 iterator 和 reference 失效；对 list 来说，成员 erase 擦除节点并使指向被擦除节点的 iterator 失效。具体失效规则由容器决定，算法本身没有容器结构视角。

C++20 提供了容器相关的 std::erase 和 std::erase_if 便利函数。它们把 remove-erase 的两阶段动作封装成一个调用，但底层责任仍然相同：算法式筛选决定保留元素，容器成员操作负责缩短和销毁。使用便利函数时也要检查容器类型、谓词成本和 iterator 失效规则。

std::erase_if(events, [](const Event& event) {
    return !is_valid(event);
});

这个写法表达力更强，尤其适合普通“按条件删除”的代码路径。学习源码或排查对象状态时，仍应把它还原成“筛选保留前缀 + 容器擦除尾部”的模型。这样可以解释为什么删除前后 size 改变、为什么尾部对象被析构、为什么某些 iterator 失效。

remove-erase 对关联容器有不同边界。有序 std::set、std::map 的 iterator 解引用结果通常暴露不可修改 key，通用 remove_if 需要通过赋值压缩元素，无法用于这类容器。C++20 的 std::erase_if 对关联容器走的是遍历并调用成员 erase 的路径；手写代码也应使用迭代器循环配合容器 erase。

std::map<int, Event> table{{1, {1, 0, true, "A"}}, {2, {2, 0, false, "B"}}};

for (auto it = table.begin(); it != table.end(); ) {
    if (!is_valid(it->second)) {
        it = table.erase(it);
    } else {
        ++it;
    }
}

这段代码的删除单位是节点，map 的 key 顺序不被破坏。它没有尝试把后面的节点赋值到前面的节点位置，因为有序容器的结构不允许通过元素赋值来改变 key 排列。这里再次体现算法和容器的分工：连续或可赋值区间适合 remove-erase，节点式关联容器适合成员 erase 路径。

重叠边界是修改类算法的另一个集中风险。std::copy 从左到右写入；当目标起点落在源区间内部时，后续还没读取的源元素可能先被覆盖，标准把这类情况规定为未定义行为。向右移动一段元素应使用 copy_backward，向左移动可以使用 copy。

std::vector<int> data{1, 2, 3, 4, 5};

std::copy_backward(data.begin(), data.begin() + 3, data.begin() + 4);
// data: 1 1 2 3 5

这里目标区间是 [data.begin() + 1, data.begin() + 4)，和源区间 [data.begin(), data.begin() + 3) 重叠，并且目标在右侧。copy_backward 从尾部向前写，读取源元素时它还没有被覆盖。相反，向左压缩时 copy 的方向合适，这也是 remove 可以把保留元素向前移动的原因。

std::move 和 move_backward 的方向判断与 copy 类似，只是写入动作使用移动赋值。源对象在移动后仍然有效，尾部或源段中被移动过的位置应按 moved-from 状态处理。对于拥有资源的类型，方向错误不仅会导致值被覆盖，还会让 moved-from 状态传播到读者没有预期的位置。

transform 的重叠边界更细。原地一元 transform 是常见合法用法，因为每个输出位置对应当前输入位置；二元 transform 也允许输出写回某个输入区间，但可调用对象应保持局部计算，不在内部改动 range 或让 iterator 失效。若一个位置的结果依赖后续尚未读取元素，并且输出会覆盖那些元素，就应改用临时缓冲或显式设计访问方向。

std::vector<int> data{1, 2, 3, 4};
std::vector<int> out(data.size());

std::transform(data.begin(), data.end() - 1, data.begin() + 1, out.begin(),
               [](int left, int right) { return right - left; });

这段代码使用独立输出缓冲来计算相邻差值。若把 out.begin() 改成 data.begin()，第一个位置被覆盖后，后续二元输入是否读到旧值要按具体读写顺序审查。独立输出缓冲把读取旧数据和写入新数据分离，是处理跨元素依赖时最稳定的做法。

本章最终判断顺序可以压缩成五步。第一，看算法写入已有元素、追加元素、压缩区间还是重排区间。第二，看 iterator category 和 value type 操作是否满足要求。第三，看目标区间容量、插入路径和容器生命周期责任。第四，看源区间和目标区间是否重叠，以及需要正向还是反向算法。第五，看返回 iterator 如何继续进入 erase、后续算法或结果范围。这个顺序能覆盖本章所有修改类算法，也能解释它们与容器成员函数之间的边界。

最小自检任务

阅读下面代码，判断调用结束后 events.size()、events 的有效前缀、archive.size() 和 events 中被移动元素的状态应如何理解。再说明哪些地方由算法负责，哪些地方由容器负责。

#include <algorithm>
#include <iterator>
#include <string>
#include <vector>

struct Event {
    int id{};
    bool valid{};
    std::string tag;
};

int main() {
    std::vector<Event> events{
        {1, true,  "A"},
        {2, false, "B"},
        {3, true,  "C"},
        {4, false, "D"}
    };

    std::vector<Event> archive;
    archive.reserve(events.size());

    std::copy_if(events.begin(), events.end(), std::back_inserter(archive),
                 [](const Event& event) { return event.valid; });

    auto logical_end = std::remove_if(events.begin(), events.end(),
                                      [](const Event& event) { return !event.valid; });

    events.erase(logical_end, events.end());
}

答案要点

std::copy_if 读取 events 全区间，并通过 std::back_inserter(archive) 追加有效事件，所以 archive.size() 变为 2，元素顺序是 id 为 1、3 的事件。追加动作由 archive.push_back 完成，算法只通过 output iterator 赋值。

std::remove_if 在 events 内部把 valid == true 的元素压到前段，并返回 logical end。这个阶段结束时，events.size() 仍然是 4；[events.begin(), logical_end) 是有效前缀，按顺序保存 id 为 1、3 的事件。尾部位置仍然处在有效生命周期内，但它们是待擦除区，业务代码不应再依赖其旧值。

events.erase(logical_end, events.end()) 由 vector 负责销毁尾部元素并缩短 size。调用结束后 events.size() 为 2。vector 的 erase 还决定 iterator 和 reference 失效规则；算法没有容器结构视角。

被 remove_if 移动赋值过的源位置仍然是有效对象。对含有 std::string 的 Event，移动后的字符串成员保持有效但具体内容不应作为业务事实使用。最终 erase 会销毁尾部对象，剩余前缀中的两个事件表达保留结果。

本章知识点总结

修改边界：修改类算法通过 iterator 写元素值，容器长度变化由 inserter 或容器成员函数完成。
目标区间：普通输出 iterator 要求目标位置已有有效元素，insert iterator 会把赋值转成容器插入。
copy 语义：copy 逐个拷贝源元素到目标区间，目标起点落入源区间内部会破坏读取路径。
copy_if 语义：copy_if 用谓词筛选输出元素，并保持被复制元素的相对顺序。
move 语义：range move algorithm 把源元素移动赋值到目标位置，源对象仍处在有效生命周期内。
transform 语义：transform 把可调用对象返回值写入目标区间，适合局部变换和原地覆盖。
fill 边界：fill 覆盖已有元素，创建新元素需要容器构造、resize、insert 或 inserter 路径。
generate 边界：generate 每个位置调用一次 generator，generator 的状态和异常由调用方审查。
逻辑删除：remove 和 remove_if 只返回 logical end，容器 size 在算法阶段保持不变。
replace 边界：replace 系列表达值替换，区间长度和元素顺序保持不变。
顺序重排：reverse、rotate 和 shuffle 改变元素排列，元素数量和容器容量保持不变。
iterator 能力：重排算法依赖 iterator category，reverse 需要双向能力，shuffle 需要随机访问能力。
remove-erase：remove-erase idiom 先压缩保留前缀，再由容器 erase 销毁尾部并缩短 size。
关联容器：有序关联容器的 key 不适合通用 remove 压缩，应使用成员 erase 或 C++20 erase_if 路径。
重叠方向：向右搬运重叠区间使用 backward 算法，向左压缩使用正向写入路径。
判断顺序：先看写入形态，再看 iterator 能力、目标容量、重叠方向、返回 iterator 和容器失效规则。

27.1 copy、copy_if、move 与 transform​

27.2 fill、generate 与 value production​

27.3 remove、remove_if 与 replace 系列​

27.4 reverse、rotate 与 shuffle​

27.5 remove-erase idiom 与重叠边界​

最小自检任务​

答案要点​

本章知识点总结​