Chapter 55: Mini Algorithm

STL 算法的工程入口是半开区间和 iterator。容器负责存储，算法负责按 iterator 能力访问区间，比较器、谓词和赋值表达式负责把用户类型接入算法循环。本章用一组 mini algorithm 复盘这条路径：从线性扫描开始，扩展到复制、移动、二分、排序，再用 tag dispatch 把 iterator category 变成实现选择。

本章贯穿材料是一段 Record 区间。它先被 find 定位，再被 copy 写入另一个区间，被 move 转移对象状态，被 lower_bound 在有序区间中定位插入点，最后用简化排序策略重排。这个材料覆盖 STL 算法的最小充分知识集：输入区间、输出区间、元素访问、比较条件、返回 iterator、复杂度和失效边界。

标准库中的 std::find、std::copy、std::move、std::lower_bound 和 std::sort 都比本章代码更完整。本章代码只保留教学所需路径，目标是让读者能读出算法源码的骨架：循环推进 iterator，按约束解引用元素，在满足条件时返回或写入结果。

#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;
}

读完整章后，读者应能按一个稳定顺序判断算法实现：先确认输入和输出区间，再确认 iterator 能力，再确认元素读写表达式，再确认比较器或谓词约束，最后把返回值、复杂度和重叠边界纳入工程判断。这个顺序比记住每个算法的 API 更可迁移，因为 STL 算法族共享同一套接口形状。

55.1 find

find 的核心问题是：给定一个半开区间 [first, last) 和一个目标值，如何用最弱 iterator 能力完成定位。半开区间把可访问范围表达为“从 first 开始，推进到 last 前停止”。last 是哨兵位置，算法可以比较它，但不会解引用它。

最小 find 只需要 input iterator 能力：比较 first != last，解引用 *first，前进 ++first。它不需要随机访问，不需要知道区间长度，也不需要容器类型。这个形状解释了 STL 算法为何能同时作用在 vector、list、istream_iterator 这类不同来源上。

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。调用者必须把返回 iterator 和原来的 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";
}

谓词比较的工程边界在于“只读判断”。find_if 会把元素交给 pred(*first)，谓词应能接受元素引用并返回可转成 bool 的结果。谓词若修改元素，算法仍可能运行，但调用点的含义会从“查找”变成“带副作用扫描”。源码阅读时看到谓词形参，就要检查它是否只读、是否捕获外部状态、是否在多次调用下保持稳定结果。

find 的复杂度来自线性扫描。长度为 N 的区间最多做 N 次比较或谓词调用。这个结论对所有满足 input iterator 的区间成立；容器内部布局只改变每次推进的成本。例如 vector 推进通常是指针加一，链表推进需要读取节点指针，输入流推进还会触发读取动作。

55.2 copy

copy 的核心问题是：如何把一个输入区间按原顺序写入另一个输出起点。它的接口多了 d_first，这个 iterator 指向目标区间的第一个写入位置。算法不会分配目标空间，也不会检查目标容量；容量责任在调用者或目标 iterator 适配器上。

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

这段代码只表达三个动作：读源元素、写目标位置、同时推进两个 iterator。返回值是目标区间中最后一个写入元素之后的位置。这个返回值可继续接下一次写入，因此多个算法可以串联成一个输出流。

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());

copy 的对象语义是拷贝赋值。表达式 *d_first = *first 要求目标位置已经有有效对象，且该对象能接收源元素的赋值。它管理的是已有对象之间的状态覆盖；在未初始化存储上批量构造对象属于 uninitialized_copy 一类原始内存算法。本章 mini copy 不接触 allocator，也不负责对象生命周期起点。

重叠边界是 copy 的工程检查点。当目标起点落入源区间内部时，正向写入可能提前覆盖后面尚未读取的源元素。向右搬移已有区间时应使用反向路径，例如标准库的 copy_backward。向左压缩时，正向 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 次赋值。性能差异主要来自赋值表达式和 iterator 推进。对简单连续类型，真实标准库实现常见优化会识别 trivially copyable 类型并转向内存块操作；教学版 mini copy 保留逐元素循环，便于看清泛型算法的语义底座。

55.3 move

move 算法的核心问题是：如何把源区间元素作为右值写入目标区间。这里的 move 是算法名，作用于一个区间；它和 std::move(x) 这个把单个表达式转成右值引用的工具函数密切相关。算法内部的关键表达式是 *d_first = std::move(*first)。

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

这段代码触发的是移动赋值。源元素仍留在原存储位置上，生命周期仍然有效，状态进入 moved-from 状态。moved-from 对象必须能析构、能被重新赋值，并满足类型自身声明的有效状态约束；它保留原值这件事没有通用保证。

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 与容器扩容路径的关系很直接。容器把旧存储中的元素逐个构造到新存储中时，会根据类型能力选择移动或拷贝；算法层面的 move 展示了“把源元素作为右值读出”的表达式形状。真正的容器扩容还会叠加 allocator、placement new、异常回滚和提交点，本章 mini algorithm 只关注已有目标对象上的移动赋值。

重叠边界和 copy 类似。目标起点位于源区间内部时，正向移动可能改写后面尚未读取的源对象。向右移动已有区间时应使用反向路径，例如标准库的 move_backward。向左移动时，正向路径更符合读写顺序，但工程代码仍应显式选择语义匹配的标准算法，减少对偶然实现顺序的依赖。

复杂度是精确的 N 次移动赋值。真实成本取决于元素类型。移动一个 std::string 可能只交换内部指针和长度，也可能受短字符串优化影响退化为字符复制；移动一个持有文件句柄的对象可能转移句柄所有权。算法只保证调用移动赋值，资源转移细节由元素类型实现决定。

55.4 lower_bound

lower_bound 的核心问题是：在已按比较条件分区的半开区间中，返回第一个“未排在目标值之前”的位置。通常使用场景是有序区间，因此它经常被理解为二分查找的插入点定位。严格地说，它依赖的是 partitioned range：所有满足 comp(element, value) 的元素位于前段，其余元素位于后段。

最小实现可以只要求 forward iterator。为了在 forward iterator 上运行，算法不能写 middle = first + n；它需要先计算长度，再用 std::advance 推进到中点。比较次数保持对数级，但 iterator 前进次数可能达到线性级。

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 的后一个位置，并扣除已经排除的前半段。中点元素若不满足条件，答案可能就是中点，也可能在它之前；算法保留左半段。

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 是否有定义良好的结果。区间必须相对目标值满足分区条件。若 records 按 name 排序，却用 id_less_value 查询 id，二分收缩会基于错误分区做判断，返回位置没有可依赖语义。工程检查顺序应先确认排序或分区依据，再确认查询比较器和该依据一致。

lower_bound 的复杂度要拆成两层看。比较次数是 O(log N)，因为每轮排除一半候选区间。iterator 前进成本取决于 category：随机访问 iterator 可常数时间跳到中点；forward iterator 需要逐步推进。对 std::map、std::set 这类树形容器，成员函数 lower_bound 能沿树结构下降，通常比通用算法在树 iterator 上反复 advance 更合适。

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

这段代码把排序拆成两层循环：外层确定当前位置，内层在剩余区间中找最小元素，再用 iter_swap 把它放到当前位置。比较器 comp(a, b) 表示 a 应排在 b 之前。比较器必须形成稳定的严格弱序，否则“最小元素”这个判断会失去一致性。

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;
});

iter_swap 是排序算法连接 iterator 和元素交换的接口。对普通 iterator，它通常等价于交换 *a 和 *b；对特殊 iterator，库可以通过 ADL 找到更合适的交换方式。源码阅读时看到 using std::iter_swap; iter_swap(a, b);，应把它理解为“允许 iterator 或元素类型提供定制交换路径”。

selection sort 的比较次数是平方级。长度为 N 的区间大约执行 N * (N - 1) / 2 次比较，交换次数最多 N - 1 次。这个算法适合教学和极小区间，不适合作为通用 sort 实现。真实标准库实现要同时满足随机访问要求、O(N log N) 比较复杂度、比较器约束和异常边界。

排序的对象状态边界也需要明确。比较器不应修改元素；交换会改变元素所在位置；iterator 若指向同一容器内元素，排序后 iterator 位置仍对应原位置，但该位置上的值可能已经改变。工程代码若在排序前保存元素地址、引用或索引，需要区分“位置稳定”和“值稳定”这两个问题。

55.6 tag dispatch

tag dispatch 的核心问题是：如何在编译期根据 iterator category 选择实现入口。iterator category 是 iterator 通过 iterator_traits 暴露的能力标签，例如 input、forward、bidirectional、random access。tag dispatch 把这个标签作为一个空对象传给重载函数，让重载解析选择更合适的实现。

下面用 distance 展示 tag dispatch。forward iterator 只能逐步推进，因此距离计算需要线性循环；random access iterator 支持相减，因此可以直接返回 last - first。

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>::iterator 通常提供 random access category，调用会进入相减版本；std::list<int>::iterator 提供 bidirectional category，若只提供上面两个重载，bidirectional tag 会转换到 input tag 基类路径，从而进入线性版本。真实实现会覆盖更多 category，以便表达更细能力。

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 的工程价值在于把“接口相同、成本不同”的路径集中到一组内部函数里。外部 API 仍是 mini::distance(first, last)，内部根据 iterator 能力切换实现。源码阅读时可以按三步定位：先看对外模板函数，再找 iterator_traits 抽取的 tag，再找带 tag 参数的内部重载。

C++17 以后也可以用 if constexpr 写类似选择，C++20 以后还可以用 concepts 约束重载。tag dispatch 仍值得学习，因为大量 STL 源码和旧项目都使用这套形状；它还展示了泛型库如何在不增加运行时分支的情况下保留多条实现路径。

55.7 iterator category 优化

iterator category 优化的核心问题是：同一个算法语义如何在不同 iterator 能力下获得不同成本。lower_bound 是典型案例：语义上都返回第一个未排在目标值之前的位置；实现上，forward iterator 版本需要 distance 和多次 advance，random access 版本可以用整数偏移直接定位中点。

下面把 lower_bound 拆成两个内部版本。forward 版本沿用 std::advance，random access 版本使用 first + step。外部入口仍保持统一接口。

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

这组重载展示了 STL 优化的常见形状：语义层保持一个算法，能力层拆出多条路径。random access 路径触发条件是 iterator category 能匹配 std::random_access_iterator_tag。触发后，中点定位成本从逐步推进变成常数时间偏移；比较次数仍是 O(log N)。

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;
    }
);

优化判断顺序应固定下来：先确认算法语义和前置条件，再确认 iterator category，再确认元素操作表达式，再评估复杂度中哪一部分被优化。对 lower_bound 来说，排序或分区条件是语义前提；random access 只优化中点定位；比较器调用次数仍受二分结构约束；元素比较本身若很昂贵，iterator 优化也不会消除比较成本。

这个顺序也能解释源码中的很多分支。copy 可能根据 iterator 是否连续、元素是否 trivially copyable 选择块复制；advance 根据 category 选择逐步推进或直接加偏移；sort 直接要求 random access 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;
}

答案要点

mini::copy(items.begin(), items.end(), buffer.begin()) 具备稳定语义。检查顺序是：源区间有效，目标区间已有足够数量的有效对象，读表达式 *first 和写表达式 *d_first = *first 成立，目标起点没有落入源区间内部，返回值 out 指向目标区间尾后位置。

mini::lower_bound_fast 具备稳定语义，因为 items 已按 key 升序排列，比较器也用 item.key < key 表达同一分区依据。items.begin() 属于 vector iterator，通常能触发 random access 路径。这个优化只降低中点定位成本，比较次数仍是对数级。

mini::move(buffer.begin(), buffer.end(), items.begin()) 会把 buffer 中元素移动赋值到 items 中。两个区间来自不同 vector，没有源目标重叠问题。调用后 buffer 中的 payload 仍是有效 std::string 对象，但值处于 moved-from 状态；items 获得移动后的对象状态。

注释中的 mini::selection_sort(linked.begin(), linked.end(), ...) 缺少本章简化排序要求的 iterator 能力。std::list iterator 提供双向推进能力，缺少随机访问能力；selection sort 本身可以改写成只用前进 iterator 的版本，但本章这个排序接口通过 static_assert 固定为 random access 路径，工程上应使用 linked.sort 或改写算法约束。

本章知识点总结

• 半开区间：STL 算法用 [first, last) 表示输入范围，last 只作为边界比较位置。
• find 骨架：find 通过线性扫描比较元素，命中返回当前位置，未命中返回原区间的 last。
• 谓词约束：谓词应提供只读判断并返回可转成 bool 的结果，副作用会改变算法调用的工程含义。
• copy 语义：copy 对已有目标对象执行逐元素拷贝赋值，容量和对象有效性由调用者保证。
• 重叠边界：区间复制或移动时要先判断读写方向，向右搬移已有区间应选择反向算法。
• move 语义：move 算法对源元素应用 std::move 后写入目标，源对象仍有效但进入 moved-from 状态。
• 二分不变量：lower_bound 用 first 和 count 描述剩余候选区间，每次根据中点比较排除一半范围。
• 分区前提：lower_bound 的返回位置依赖区间相对查询值满足分区条件，排序依据和比较器必须一致。
• 排序边界：简化 selection sort 展示比较器和交换路径，但平方级比较成本只适合教学或极小区间。
• iter_swap 接口：排序算法通过 iter_swap 交换 iterator 指向的元素，并允许类型提供更合适的交换路径。
• tag dispatch：算法可用 iterator_traits 提取 category，再通过重载解析在编译期选择实现。
• 能力优化：iterator category 优化改变定位和推进成本，算法语义、前置条件和元素操作约束仍需单独检查。