Skip to main content

Chapter 55: Mini Algorithm

核心问题与阅读主线

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

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 dispatchcategory{} 空标签参数重载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_boundforward_iterator_tag:distance + advancerandom_access_iterator_tag:last - first 与 first + step中点定位降至 O(1),比较次数仍为 O(log N)
advanceinput/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 优化路径与元素操作单次开销,避免误以为随机访问优化能消除昂贵比较成本。