Chapter 55: Mini Algorithm
核心问题与阅读主线
STL 算法通过半开区间 [first, last) 与 iterator 解耦存储和遍历,再借助谓词、比较器与读写表达式接入用户类型。本章从零实现 find、copy、move、lower_bound、简化版 selection_sort 与 distance 的 tag dispatch,拆解泛型算法的接口契约、对象语义边界与编译期能力分发。
全章共用代码样本(下文各节持续拆解)
本章以一段 Record 区间与比较辅助函数作为贯穿材料,依次演练定位(find)、复制(copy)、状态转移(move)、二分插入点定位(lower_bound)和原地重排(selection_sort):
#include <algorithm>
#include <iterator>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
struct Record {
int id{};
std::string name;
};
inline bool less_by_id(const Record& left, const Record& right) {
return left.id < right.id;
}
inline bool id_less_value(const Record& left, int value) {
return left.id < value;
}
对照标准库完整规格可参阅 std::find、std::copy、std::move、std::lower_bound 与 std::sort。
55.1 find
find 在半开区间 [first, last) 内线性定位首个匹配元素,只要求最弱的 input iterator 能力,因此可直接复用于 vector、list 与 istream_iterator:
- 边界判停:比较
first != last;last作为尾后哨兵只参与比较,永不解引用。 - 只读访问:解引用
*first读取当前元素。 - 单步推进:执行
++first前移,不依赖区间长度或随机偏移。
namespace mini {
template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value) {
for (; first != last; ++first) {
if (*first == value) {
return first;
}
}
return last;
}
template <class InputIt, class Pred>
InputIt find_if(InputIt first, InputIt last, Pred pred) {
for (; first != last; ++first) {
if (pred(*first)) {
return first;
}
}
return last;
}
} // namespace mini
命中时返回首个满足条件的位置,未命中时返回 last;调用方必须先校验 pos != last 再解引用:
std::vector<Record> records{{3, "cache"}, {7, "tree"}, {9, "hash"}};
const auto pos = mini::find_if(records.begin(), records.end(), [](const Record& record) {
return record.id == 7;
});
if (pos != records.end()) {
pos->name = "ordered-tree";
}
长度为 N 的区间最多执行 N 次比较或谓词调用(O(N));容器布局只改变单步 ++first 的成本——vector 为指针偏移,链表为节点指针跳转,istream_iterator 则会触发流读取。
边界与误区
谓词 pred(*first) 应保持只读、无外部可变状态依赖且返回可转为 bool 的结果;若谓词修改元素,“只读查找”会变成带副作用的扫描。同时,严禁在未确认 pos != last 时解引用返回值。
55.2 copy
copy 将 [first, last) 按原序逐元素写入以 d_first 为起点的目标区间,并返回最后一个写入元素之后的位置(便于串联多次写入)。算法不分配存储也不校验容量,目标区间有效性与容量由调用方或插入适配器负责。
namespace mini {
template <class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last, OutputIt d_first) {
for (; first != last; ++first, ++d_first) {
*d_first = *first;
}
return d_first;
}
} // namespace mini
std::vector<Record> source{{1, "parse"}, {2, "copy"}};
std::vector<Record> destination(source.size());
const auto out = mini::copy(source.begin(), source.end(), destination.begin());
const bool filled = (out == destination.end());
*d_first = *first 触发拷贝赋值而非对象构造;选用区间复制算法时须先核对目标存储状态与区间重叠方向:
| 算法 | 目标存储前提 | 底层操作 | 区间重叠安全方向 |
|---|---|---|---|
mini::copy / std::copy | 目标已有有效对象 | *d_first = *first(拷贝赋值) | d_first 不在 [first, last) 内(可安全左移) |
std::copy_backward | 目标已有有效对象 | 从尾向头逐元素拷贝赋值 | 目标尾端不在 (first, last] 内(可安全右移) |
std::uninitialized_copy | 目标为未初始化原始内存 | 在未构造位置原地拷贝构造 | 目标与源区间不可重叠 |
std::vector<int> values{1, 2, 3, 4, 5};
// 左移一格:先读 values[1],再写 values[0],读写方向匹配。
mini::copy(values.begin() + 1, values.end(), values.begin());
// 右移一格应选择反向算法;正向写入会先覆盖 values[1]。
std::copy_backward(values.begin(), values.end() - 1, values.end());
长度为 N 的输入区间固定产生 N 次赋值;标准库实现通常会识别连续区间上的 trivially copyable 类型并优化为块内存操作,而泛型语义仍以逐元素拷贝赋值为基准。
55.3 move
move 算法以区间为单位执行 *d_first = std::move(*first),将源元素作为右值写入目标区间(区别于只做单表达式右值转换的工具函数 std::move(x))。
namespace mini {
template <class InputIt, class OutputIt>
OutputIt move(InputIt first, InputIt last, OutputIt d_first) {
for (; first != last; ++first, ++d_first) {
*d_first = std::move(*first);
}
return d_first;
}
} // namespace mini
std::vector<std::string> names{"vector", "deque", "list"};
std::vector<std::string> moved(names.size());
mini::move(names.begin(), names.end(), moved.begin());
// names 中的每个 string 仍是有效对象,可以析构或重新赋值。
names[0] = "array";
理解区间 move 需分清以下三条对象与成本边界:
- moved-from 状态契约:移动赋值后源元素仍留在原存储且生命周期有效,进入 moved-from 状态——仍须可析构、可重新赋值并满足类型有效状态不变量,但不保证保留原值。
- 赋值与容器扩容构造的区别:
mini::move只对已有目标对象执行移动赋值;容器扩容把元素搬到新存储时,还会涉及 allocator、placement new 上的移动/拷贝构造、异常回滚与提交点。 - 精确次数与类型相关开销:固定触发
N次移动赋值,真实成本取决于元素类型——std::string可能交换内部指针与长度或因短字符串优化(SSO)退化为字符复制,句柄类则仅转移句柄所有权。
边界与误区
move 的区间重叠约束与 copy 相同:目标起点落入源区间 [first, last) 内时,正向移动会覆盖尚未读取的源对象;向右搬移已有区间必须显式调用 std::move_backward。
55.4 lower_bound
lower_bound 在满足分区条件(partitioned range:所有使 comp(element, value) 为真的元素位于前段,其余位于后段)的半开区间内,返回第一个“未排在 value 之前”的位置(即有序区间的合法插入点)。
namespace mini {
template <class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp) {
using difference_type = typename std::iterator_traits<ForwardIt>::difference_type;
difference_type count = std::distance(first, last);
while (count > 0) {
ForwardIt middle = first;
const difference_type step = count / 2;
std::advance(middle, step);
if (comp(*middle, value)) {
first = ++middle;
count -= step + 1;
} else {
count = step;
}
}
return first;
}
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value) {
return mini::lower_bound(first, last, value, std::less<>{});
}
} // namespace mini
阅读该实现需抓住循环不变量与最弱能力约束:
- 循环不变量:
first与count描述答案仍可能出现的剩余半开区间。若comp(*middle, value)为真,说明中点元素排在目标值之前,推进first = ++middle并扣除step + 1;否则答案就是middle或在其左侧,收缩count = step。 - 最弱能力约束:只需 forward iterator。因不能写
first + step,必须先用std::distance求长,再用std::advance推进到中点。
std::vector<Record> records{{2, "array"}, {5, "vector"}, {9, "map"}};
const auto insert_pos = mini::lower_bound(
records.begin(), records.end(), 6,
[](const Record& record, int id) {
return record.id < id;
}
);
records.insert(insert_pos, Record{6, "deque"});
lower_bound 的复杂度须拆成比较与推进两层评估:
- 比较次数:固定为
O(log N)。 - 推进成本:random access iterator 单次中点定位为
O(1),forward iterator 累计std::advance可达O(N);std::map、std::set等树形容器应优先调用成员函数lower_bound沿树结构下降。
边界与误区
二分前提是区间相对查询值已按 comp 分区。若 records 按 name 排序却用 id_less_value 查询 id,中点收缩会基于错位分区作出判断,返回位置没有任何可依赖语义。
55.5 sort 简化版
sort 在随机访问区间上按比较器将元素重排为非降序。标准库 std::sort 通常采用 introsort 等混合策略,要求随机访问 iterator 及可交换、可移动构造与可移动赋值的元素;本节用结构极简的 selection_sort 暴露能力校验、比较器约束与交换通道。
namespace mini {
template <class RandomIt, class Compare>
void selection_sort(RandomIt first, RandomIt last, Compare comp) {
using category = typename std::iterator_traits<RandomIt>::iterator_category;
static_assert(
std::is_base_of_v<std::random_access_iterator_tag, category>,
"mini::selection_sort requires random access iterators"
);
for (RandomIt current = first; current != last; ++current) {
RandomIt best = current;
for (RandomIt probe = current; probe != last; ++probe) {
if (comp(*probe, *best)) {
best = probe;
}
}
if (best != current) {
using std::iter_swap;
iter_swap(current, best);
}
}
}
template <class RandomIt>
void selection_sort(RandomIt first, RandomIt last) {
mini::selection_sort(first, last, std::less<>{});
}
} // namespace mini
std::vector<Record> records{{9, "hash"}, {3, "array"}, {5, "vector"}};
mini::selection_sort(records.begin(), records.end(), [](const Record& left, const Record& right) {
return left.id < right.id;
});
| 维度 | mini::selection_sort | 标准库 std::sort |
|---|---|---|
| 核心策略 | 外层定槽位、内层找最小元素 | 混合排序(常见如 introsort) |
| 比较次数 | 约 N * (N - 1) / 2(O(N^2)) | 最坏/平均 O(N log N) |
| 交换次数 | 至多 N - 1 次 | 取决于分区、堆化与插排路径 |
| 能力与约束 | random access(static_assert 校验) | random access + 可交换/可移动 + 异常边界 |
- 严格弱序与只读:
comp(a, b)表示a应排在b之前,必须满足严格弱序且不修改元素,否则“最小元素”失去一致性。 - ADL 交换接口:
using std::iter_swap; iter_swap(current, best);使库能通过 ADL 为特殊 iterator 或元素类型匹配定制交换路径。
边界与误区
原地排序交换的是槽位上的元素值:排序前保存的数组下标或 vector 迭代器仍指向原位置,但该位置上的值可能已换为其他元素。排序前缓存元素地址、引用或下标时,必须区分“槽位位置稳定”与“对象值绑定稳定”。
55.6 tag dispatch
tag dispatch 通过 std::iterator_traits<It>::iterator_category 提取空标签类型,将 category{} 作为参数传给内部重载函数,在编译期零运行时分支地选出最佳实现。
namespace mini {
template <class InputIt>
auto distance_impl(InputIt first, InputIt last, std::input_iterator_tag)
-> typename std::iterator_traits<InputIt>::difference_type {
typename std::iterator_traits<InputIt>::difference_type n = 0;
for (; first != last; ++first) {
++n;
}
return n;
}
template <class RandomIt>
auto distance_impl(RandomIt first, RandomIt last, std::random_access_iterator_tag)
-> typename std::iterator_traits<RandomIt>::difference_type {
return last - first;
}
template <class It>
auto distance(It first, It last)
-> typename std::iterator_traits<It>::difference_type {
using category = typename std::iterator_traits<It>::iterator_category;
return mini::distance_impl(first, last, category{});
}
} // namespace mini
std::vector<int> dense{1, 2, 3, 4};
const auto dense_distance = mini::distance(dense.begin(), dense.end());
// std::list<int> linked{1, 2, 3, 4};
// const auto linked_distance = mini::distance(linked.begin(), linked.end());
阅读或编写 tag dispatch 源码的核心规律如下:
- 标签继承链兜底:
std::vector<int>::iterator匹配std::random_access_iterator_tag直接返回last - first;std::list<int>::iterator提供std::bidirectional_iterator_tag,在上述只有两份重载时会自动向上转换为基类std::input_iterator_tag走线性循环(完整标准库实现会补充更多 category 重载)。 - 源码阅读三步:① 先看对外统一模板入口(如
mini::distance);② 找iterator_traits提取的iterator_category;③ 对照各*_impl末尾的 tag 形参定位实现路径。
| 编译期分发机制 | 核心载体 | 工程定位与适用标准 |
|---|---|---|
| tag dispatch | category{} 空标签参数重载 | C++98 起通用,借助 tag 继承链自动兜底,大量 STL 源码与旧项目沿用 |
if constexpr | 编译期条件分支 | C++17 起可用,单函数内收敛多路径、减少 _impl 样板代码 |
concepts 重约束 | concept 约束函数重载 | C++20 起可用,能力要求直接写进接口签名、报错更清晰 |
55.7 iterator category 优化
iterator category 优化的本质是语义契约统一、能力路径分层:同一算法保持相同前置条件与返回语义,仅在内部按 iterator 能力替换定位或推进手段。下面将 lower_bound_fast 按 forward 与 random access 拆成两条内部路径:
namespace mini {
template <class ForwardIt, class T, class Compare>
ForwardIt lower_bound_impl(
ForwardIt first,
ForwardIt last,
const T& value,
Compare comp,
std::forward_iterator_tag
) {
using difference_type = typename std::iterator_traits<ForwardIt>::difference_type;
difference_type count = std::distance(first, last);
while (count > 0) {
ForwardIt middle = first;
const difference_type step = count / 2;
std::advance(middle, step);
if (comp(*middle, value)) {
first = ++middle;
count -= step + 1;
} else {
count = step;
}
}
return first;
}
template <class RandomIt, class T, class Compare>
RandomIt lower_bound_impl(
RandomIt first,
RandomIt last,
const T& value,
Compare comp,
std::random_access_iterator_tag
) {
auto count = last - first;
while (count > 0) {
const auto step = count / 2;
RandomIt middle = first + step;
if (comp(*middle, value)) {
first = middle + 1;
count -= step + 1;
} else {
count = step;
}
}
return first;
}
template <class ForwardIt, class T, class Compare>
ForwardIt lower_bound_fast(ForwardIt first, ForwardIt last, const T& value, Compare comp) {
using category = typename std::iterator_traits<ForwardIt>::iterator_category;
return mini::lower_bound_impl(first, last, value, comp, category{});
}
} // namespace mini
std::vector<Record> records{{1, "a"}, {4, "b"}, {8, "c"}, {10, "d"}};
const auto pos = mini::lower_bound_fast(
records.begin(), records.end(), 8,
[](const Record& record, int id) {
return record.id < id;
}
);
标准库各类优化均遵循“先保证最小语义承诺,再按高阶能力切换实现”的统一结构:
| 算法 | 基础能力路径 | 高阶优化路径 | 被优化的成本部分 |
|---|---|---|---|
lower_bound | forward_iterator_tag:distance + advance | random_access_iterator_tag:last - first 与 first + step | 中点定位降至 O(1),比较次数仍为 O(log N) |
advance | input/forward:逐步 ++it(O(N)) | random access:直接偏移加法(O(1)) | 消除逐节点推进循环 |
copy | 逐元素 *d_first = *first | 连续区间 + trivially copyable 转内存块复制 | 减少逐元素赋值循环开销 |
sort | 无降级路径,直接要求 random access | 分区、堆化与插排依赖常数偏移 | 保证 O(N log N) 随机下标访问 |
排查顺序
评估或优化泛型算法时依次确认:① 语义与前置条件(如 lower_bound 的分区/有序前提);② iterator category 匹配(确认是否命中 random_access_iterator_tag 等高阶路径);③ 元素操作表达式(比较、赋值、移动的单次真实开销);④ 复杂度受益面(iterator 优化只改善定位与推进,不会减少二分 O(log N) 比较次数,也无法消除昂贵元素比较本身的成本)。
最小自检任务
阅读下面代码,按“区间范围 -> iterator 能力 -> 元素读写与重叠 -> 前置条件与返回值”顺序,判断四处调用是否具备稳定语义。
#include <algorithm>
#include <iterator>
#include <list>
#include <string>
#include <vector>
struct Item {
int key{};
std::string payload;
};
int main() {
std::vector<Item> items{{1, "a"}, {3, "b"}, {5, "c"}};
std::vector<Item> buffer(items.size());
auto out = mini::copy(items.begin(), items.end(), buffer.begin());
auto pos = mini::lower_bound_fast(
items.begin(), items.end(), 4,
[](const Item& item, int key) {
return item.key < key;
}
);
mini::move(buffer.begin(), buffer.end(), items.begin());
std::list<Item> linked{{5, "x"}, {1, "y"}, {3, "z"}};
// mini::selection_sort(linked.begin(), linked.end(), [](const Item& a, const Item& b) {
// return a.key < b.key;
// });
(void)out;
(void)pos;
}
本章知识点总结
- 半开区间与 find 骨架
STL 算法以
[first, last)隔离容器存储,last只比较不解引用;最小find仅需 input iterator,未命中返回last,谓词须只读且无副作用。 - copy 与赋值边界
copy对已有目标对象执行*d_first = *first并返回尾后写入位置,容量由调用方保证;向未初始化存储构造应使用uninitialized_copy。 - move 与重叠安全
move算法以*d_first = std::move(*first)转移状态,源对象保留有效生命周期但进入 moved-from 状态;区间右移重叠须用copy_backward或move_backward。 - lower_bound 分区前提
以
first和count维护剩余候选区间,在保证分区依据与比较器一致的前提下用O(log N)次比较定位插入点(树形容器优先调用成员函数)。 - 简化 sort 与交换契约
selection_sort通过static_assert锁定 random access、要求严格弱序比较器并以iter_swap支持 ADL 定制交换,其O(N^2)成本决定了通用排序需采用O(N log N)混合策略。 - tag dispatch 分发
利用
std::iterator_traits提取iterator_category空对象触发编译期重载选择,并依靠 tag 继承链为弱能力 iterator 提供兜底实现。 - 能力优化审计顺序
先定语义与分区/有序前提,再核对 iterator category 优化路径与元素操作单次开销,避免误以为随机访问优化能消除昂贵比较成本。