Skip to main content

Chapter 27: Modifying Algorithms

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

修改类算法的核心问题是:在既定 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 + nfill_n 经 push_back 拷贝构造新元素
std::generate / std::generate_n每次调用 gen() 的返回值[first, last) 或 first + ngenerate_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::reverseBidirectional完全反转 [first, last)std::forward_list 不可用;std::list 优先用 list::reverse() 重连节点
std::rotateForward将 [middle, last) 移到 [first, middle) 之前可用于链表的通用范围,但不负责查找分界条件
std::shuffleRandomAccess使用均匀随机位生成器随机打乱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_ifiterator / reference 失效规则
std::vector / std::dequeremove_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::mapit = 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; });

排查顺序

  1. 定写入形态:确认算法是覆写已有元素、经 inserter 追加、内部压缩,还是就地重排;
  2. 查能力要求:核对 iterator category(前向/双向/随机访问)与元素的拷贝/移动/交换语义;
  3. 核容量与生命周期:普通输出 iterator 须确保目标已构造且容量充足,追加或缩容归容器入口管辖;
  4. 判重叠与方向:左移用 copy/move,目标起点落入源区间向右移用 copy_backward/move_backward,跨元素依赖改用独立输出缓冲;
  5. 跟进返回 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++20 std::erase_if,有序关联容器须用成员 erase 循环;左移重叠用正向 copy/move,右移重叠用 copy_backward/move_backward。