Chapter 27: Modifying Algorithms
核心问题与阅读主线
修改类算法的核心问题是:在既定 iterator range 上完成写入、搬运、替换、压缩或重排,并严格切分“算法只写元素值”与“容器负责容量和生命周期”的职责边界。误判目标容量、重叠方向或 erase 时机,会直接引发越界写入、悬空引用与未定义行为。
全章共用代码样本(下文各节持续拆解)
本章贯穿一个事件缓冲 std::vector<Event>,其中混有无效事件、待归一化字符串字段与待重排数据。算法层只读写 [first, last) 和目标 iterator;容量增长、对象构造、析构与 iterator 失效仅通过 output iterator adapter 或容器成员函数发生。
#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);
}
compact_and_prepare 演示了四类写入路径:copy_if 经 std::back_inserter 追加、transform 原地覆写、remove_if 压缩有效前缀并返回 logical_end、rotate 重排顺序。算法全程不感知 std::vector 的 size、capacity 或 allocator,容器长度变化只发生在 back_inserter 与 erase。
边界与误区
标准库将上述算法统称为 modifying sequence operations:它们假定调用方已保证目标区间有效,既不会自动扩容,也不在赋值或谓词抛异常时提供事务回滚(异常发生前已写入的位置会保留新状态)。
27.1 copy、copy_if、move 与 transform
这四个算法都遵循“读取一个或两个输入区间、向输出 iterator 写结果”的模型,核心差异在于写入值来源与重叠约束:
| 算法 | 写入值来源 | 输出长度 vs 输入长度 | 是否允许 d_first == first | 典型用途 |
|---|---|---|---|---|
std::copy | 源元素拷贝赋值 | 相等 | 否(起点落入源区间即 UB) | 原样复制到目标区间 |
std::copy_if | 满足谓词的元素拷贝 | 小于等于(取决于谓词) | 否(输出与输入区间不可重叠) | 按条件筛选并保持相对顺序 |
std::move | 源元素移动赋值 | 相等 | 否(d_first 落入 [first, last) 即 UB) | 批量转移资源所有权 |
std::transform | 一元或二元可调用对象返回值 | 相等 | 允许(常见于一元原地变换) | 逐元素计算与原地归一化 |
cppreference 的 std::copy 页面 将 std::copy 定义为:顺序解引用 [first, last) 并赋值给 d_first 起点的目标对象。普通输出 iterator 要求目标位置已经存在有效对象:
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());
若写成 std::vector<Event> target; std::copy(source.begin(), source.end(), target.begin());,空 vector 没有任何已构造元素,std::copy 既不扩容也不在未初始化存储上构造对象,而是直接越界写入。向空容器或未知尾部追加时,应改用 std::back_inserter 等 output iterator adapter:
std::vector<Event> target;
target.reserve(source.size());
std::copy(source.begin(), source.end(), std::back_inserter(target));
核心判断
普通输出 iterator 执行“覆盖已有对象”;std::back_inserter(target) 把 *out = value 改写成 target.push_back(value),由容器在插入入口完成容量检查、对象构造、可能扩容与 iterator 失效(reserve 只减少扩容次数,真正增加 size 的是 push_back)。
std::copy_if 在拷贝前先执行谓词筛选,并保持被复制元素的相对顺序。由于输出数量在调用前未知,通常配合 std::back_inserter;若写入预分配数组,应保留返回的 one-past-last 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);
算法库的 std::move(first, last, d_first) 与类型转换工具 std::move(obj) 同名但语义层级不同:它逐个把 std::move(*first) 移动赋值给目标位置。
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());
调用结束后 old_events.size() 不变;源元素(包括 std::string 成员)仍处于有效生命周期内(valid-but-unspecified 状态),可安全析构或重新赋值,但不应再读取其旧业务值。
std::transform 提供一元和二元重载,把可调用对象的返回值写入目标区间,且允许 d_first == first 原地覆写:
std::transform(events.begin(), events.end(), events.begin(), normalize);
边界与误区
- 禁止变更容器结构:可调用对象若修改相关 range 或使 iterator 失效,即进入未定义行为;
- 不保证顺序与累积副作用:
transform仅适合“输出只依赖当前位置输入”的局部映射,需要严格访问顺序或跨元素状态累积时应改用显式循环或std::for_each(尤其存在 execution policy 重载时); - 无事务回滚:赋值、移动赋值或变换函数抛异常时,已写入位置保留新状态,后续元素维持调用前状态。
27.2 fill、generate 与 value production
fill 和 generate 不读取另一段输入区间,而是直接向输出区间写入新值,容器长度保持不变:
| 算法 | 写入值来源 | 边界方式 | 空容器配合 back_inserter 的生命周期入口 |
|---|---|---|---|
std::fill / std::fill_n | 同一 value 的重复拷贝赋值 | [first, last) 或 first + n | fill_n 经 push_back 拷贝构造新元素 |
std::generate / std::generate_n | 每次调用 gen() 的返回值 | [first, last) 或 first + n | generate_n 经 push_back 直接构造新元素 |
cppreference 的 std::fill 页面 将 std::fill(first, last, value) 定义为把区间内每个已有元素赋值为 value:
std::vector<int> scores(5);
std::fill(scores.begin(), scores.end(), 100);
对拥有资源的类型,fill 始终以同一个 sample 为源对象执行拷贝赋值,sample 自身不会被移空;每个目标元素的赋值运算符各自负责资源释放与重建:
struct Payload {
std::string data;
};
std::vector<Payload> payloads(3);
Payload sample{"ready"};
std::fill(payloads.begin(), payloads.end(), sample);
边界与误区
- 空容器不能用
fill扩容:std::vector<int> scores; std::fill(scores.begin(), scores.end(), 100);处理的是空区间,结果仍为空;新建元素须通过构造函数、resize、assign、insert或std::fill_n(std::back_inserter(scores), 5, 100); - 赋值异常无回滚:若某次赋值抛异常,前面已写位置保留新状态,后续位置维持调用前状态。
cppreference 的 std::generate 页面 规定每次写入前调用一次 gen(),适合生成递增 ID、随机样本或测试数据:
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 的内部状态由调用方管理。无论是递增计数器还是随机数引擎,通常都应在算法外创建并通过引用捕获,确保多次调用沿同一序列连续推进。
generate_n 和 fill_n 把终止条件改为“从 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::vector<Event> events(4) 配合 generate 会先默认构造 4 个 Event 再逐个赋值覆盖;而 std::generate_n(std::back_inserter(events), 4, ...) 通过 push_back 直接构造新元素并将 size 从 0 增至 4。
27.3 remove、remove_if 与 replace 系列
std::remove 和 std::remove_if 只执行逻辑删除:它们把应保留的元素前移压缩,并返回新的 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()) 仍是合法对象位置,只应视作待覆盖或待擦除的尾部。下面的等价简化实现揭示了 remove 的两个约束:
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;
}
关键事实
- Forward iterator 要求:算法必须同时维护写入位置
first与向后扫描位置read; - 仅移动赋值、未销毁尾部:保留元素通过移动赋值前移,尾部对象生命周期并未结束,只有后续
erase才会销毁对象并缩短size。
std::remove_if 把值匹配改为谓词筛选,适合在保持原有相对顺序的前提下过滤元素。若谓词、比较或移动赋值抛异常,已完成的移动不会被算法撤销:
auto logical_end = std::remove_if(
events.begin(), events.end(),
[](const Event& event) { return event.priority < 0; }
);
当语义是“替换值”而非“删除位置”时,应选用 replace 系列。cppreference 的 std::replace 页面 将其归类为 transformation operations:
| 算法系列 | 作用位置 | 输出长度 vs 输入长度 | 是否保留原顺序 | 适用语义 |
|---|---|---|---|---|
remove / remove_if | 原区间前移压缩 | 逻辑缩短(物理 size 不变) | 是 | 物理删除的前置压缩步骤 |
replace / replace_if | 原区间就地覆写 | 不变 | 是 | 保留槽位、改为占位值 |
replace_copy / replace_copy_if | 写入新输出区间 | 相等(一对一映射) | 是 | 保留原输入并生成清洗副本 |
copy_if | 写入新输出区间 | 小于等于(仅拷贝保留项) | 是 | 不改原区间、过滤输出副本 |
若业务要删除 "unknown" 事件,应使用 remove_if 后接 erase(或 C++20 std::erase_if);若要保留槽位只改为占位事件,则使用 replace_if:
std::replace_if(
events.begin(), events.end(),
[](const Event& event) { return event.tag == "unknown"; },
Event{0, 0, false, "dropped"}
);
需要保留原缓冲不变并生成一份清洗后副本时,使用 replace_copy_if(输出与输入严格一对一映射,不做区间压缩):
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"}
);
边界与误区
std::remove 按 const T& 接收 value;若直接传入区间内部元素的引用(如 data.front()),压缩覆写该位置会中途改变 value 本身并扰乱后续比较。调用前务必先拷贝到独立局部对象,或改用值捕获的 remove_if 谓词。
std::vector<int> data{1, 2, 1, 3};
int value = data.front();
auto logical_end = std::remove(data.begin(), data.end(), value);
27.4 reverse、rotate 与 shuffle
reverse、rotate 和 shuffle 只改变元素排列顺序,不增删元素也不改变容器容量,关注重点转向 iterator 能力要求、可交换/可移动性以及成员算法替代方案:
| 算法 | 最低 iterator 要求 | 排列效果 | 节点式容器适配与替代 |
|---|---|---|---|
std::reverse | Bidirectional | 完全反转 [first, last) | std::forward_list 不可用;std::list 优先用 list::reverse() 重连节点 |
std::rotate | Forward | 将 [middle, last) 移到 [first, middle) 之前 | 可用于链表的通用范围,但不负责查找分界条件 |
std::shuffle | RandomAccess | 使用均匀随机位生成器随机打乱 | std::list 不可直接调用,需先转存到 std::vector 打乱后再重建或映射 |
std::reverse(first, last) 从两端向中间推进并交换元素值,std::vector、std::deque、std::list 均可使用,而单向的 std::forward_list 无法满足双向迭代要求:
std::vector<int> values{1, 2, 3, 4, 5};
std::reverse(values.begin(), values.end());
调用后 values 变为 5, 4, 3, 2, 1,已有 iterator 仍有效且仍指向原槽位,但该槽位上的元素值已交换。对 std::list 而言,通用 std::reverse 交换元素值,成员函数 list::reverse 则直接重连节点指针——对移动成本高或节点绑定的容器,优先检查是否存在成员算法。
std::rotate(first, middle, last) 把 [middle, last) 换到前段、把 [first, middle) 换到后段,要求三个 iterator 来自同一有效区间且满足 first <= middle <= last:
std::vector<int> values{1, 2, 3, 4, 5};
std::rotate(values.begin(), values.begin() + 2, values.end());
// values: 3 4 5 1 2
标准库实现会根据 iterator 能力选择三段反转、循环交换或块交换等策略,并返回原首元素移动后的新位置 iterator。利用 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());
边界与误区
std::rotate 只按给定 middle 做机械轮转,不具备按条件分组能力。上述 find_if + rotate 的前提是区间原本已按优先级分段;若输入未分段,按谓词分组必须使用 std::partition 或 std::stable_partition。
std::shuffle 自 C++11 引入,接收显式 uniform random bit generator(旧 std::random_shuffle 已在 C++17 移除,详见 cppreference 的 std::shuffle 页面):
std::vector<int> sample{1, 2, 3, 4, 5};
std::mt19937 rng{42};
std::shuffle(sample.begin(), sample.end(), rng);
测试中可用固定种子 42 保证结果可复现,生产代码应在调用层统一管理随机源与播种策略。由于 shuffle 要求 random access iterator,std::list 无法直接使用,常见做法是把值或 iterator 收集到 std::vector 打乱后,再按成本重建链表或做索引映射。
27.5 remove-erase idiom 与重叠边界
remove-erase idiom 将逻辑压缩与物理删除拆成两步:先用 remove / remove_if 返回 logical_end,再由容器 erase 销毁尾部并缩短 size。
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());
C++20 的 std::erase 与 std::erase_if 把上述两阶段封装为单次调用,但底层职责与失效边界不变:算法式筛选决定保留项,容器成员操作负责销毁与缩短,调用时仍需审查容器类型、谓词成本与 iterator 失效规则:
std::erase_if(events, [](const Event& event) {
return !is_valid(event);
});
不同容器家族的底层结构决定了删除路径与失效范围:
| 容器类别 | 推荐删除路径 | 能否使用通用 std::remove_if | iterator / reference 失效规则 |
|---|---|---|---|
std::vector / std::deque | remove_if + erase 或 C++20 std::erase_if | 可以 | vector 使被擦除位置及其后全部失效;deque 中间擦除使全部失效 |
std::list / std::forward_list | 成员 remove_if / erase 或 C++20 std::erase_if | 可用但应优先用成员版 | 仅指向被擦除节点的 iterator 失效 |
std::set / std::map | it = table.erase(it) 循环或 C++20 std::erase_if | 不可(key 不可赋值修改) | 仅被擦除节点的 iterator 失效,不破坏 key 序 |
对有序关联容器,手写遍历删除应直接以节点为单位调用成员 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;
}
}
当源区间与目标区间存在重叠时,写入方向决定未读源数据是否会被提前覆写:
| 搬运 / 变换场景 | 重叠条件 | 正确写法 | 原因说明 |
|---|---|---|---|
| 区间整体向左搬运 | d_first < first(左移压缩) | std::copy / std::move | 从左向右依次读旧值再写入,不覆盖未读位置 |
| 区间整体向右搬运 | d_first 落入 [first, last) | std::copy_backward / std::move_backward | 从尾端向头部写入,读源元素时尚未被覆盖 |
| 一元局部变换 | d_first == first(原地覆写) | std::transform | 每个输出仅依赖当前位置输入且不改变容器结构 |
| 跨元素依赖变换 | 输出覆盖后续仍需读取的输入 | std::transform 写入独立输出缓冲 | 彻底隔离旧数据读取与新数据写入 |
右移重叠区间的典型写法如下,注意 copy_backward 的第三个参数是目标区间末尾 d_last:
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
std::move 与 std::move_backward 遵循相同的方向规则;在拥有资源的类型上用错方向,不仅会覆盖未读数据,还会把 moved-from 状态传播到非预期位置。
计算相邻差值这类跨元素二元 transform 若直接写回输入区间,后续读取会踩到已被覆写的新值,应改用独立输出缓冲:
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; });
排查顺序
- 定写入形态:确认算法是覆写已有元素、经 inserter 追加、内部压缩,还是就地重排;
- 查能力要求:核对 iterator category(前向/双向/随机访问)与元素的拷贝/移动/交换语义;
- 核容量与生命周期:普通输出 iterator 须确保目标已构造且容量充足,追加或缩容归容器入口管辖;
- 判重叠与方向:左移用
copy/move,目标起点落入源区间向右移用copy_backward/move_backward,跨元素依赖改用独立输出缓冲; - 跟进返回 iterator:将
logical_end或写入末尾接入容器erase或下游区间,并按容器类型审查 iterator 失效。
最小自检任务
阅读下面代码,判断调用结束后 events.size()、events 的有效前缀、archive.size() 及被移动元素的状态,并指明各步骤由算法还是容器负责。
#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());
}
本章知识点总结
- 算法与容器职责边界
修改类算法只通过 iterator 读写元素值,容器长度与对象生命周期变化仅由 insert iterator 或容器成员函数触发。
- 输出区间与 back_inserter
普通输出 iterator 要求目标位置已有有效对象,动态追加或未知输出长度时应使用
std::back_inserter等 adapter。 - copy / move / transform 取舍
copy拷贝、move移动(源对象进入 valid-but-unspecified 状态)、transform逐元素计算写入;局部无副作用映射才可原地覆写。 - fill 与 generate 生命周期
fill重复拷贝赋值已有区间,generate每次调用外部状态可控的 generator;空容器配合fill_n/generate_n+back_inserter可直接构造新元素。 - 逻辑删除与值替换
remove/remove_if只前移压缩并返回logical_end(注意传入独立值拷贝防止区间别名),保留槽位改占位值则用replace/replace_copy系列。 - 顺序重排与 iterator 能力
reverse需双向、rotate需前向、shuffle需随机访问 iterator 与显式 RNG;节点式容器优先用成员算法,按条件分组应选partition。 - remove-erase 与重叠方向
顺序容器用
remove_if+erase或 C++20std::erase_if,有序关联容器须用成员erase循环;左移重叠用正向copy/move,右移重叠用copy_backward/move_backward。