算法与lambda：
表达处理意图。

10.1 范围合同与操作次数

已经能写循环了，为什么还要学标准算法？因为“找到第一个4”“统计合格项”“排序”是不同的任务。名字准确的接口让读者先知道意图，再检查输入条件。进入本章前，先完成09章的范围与借用和M1中段检查；本章不会用算法替你补上无效指针或容器边界。

算法接收的[first,last)沿用09.1的半开范围：首位置包含在内，尾后不读取，首尾相等就是空范围。把两个不同vector的首尾拼起来不是一个合法范围。只读算法需要能读取每项；排序还需要能修改和交换元素。本章都使用实际存活的array/vector，不在遍历中改变拥有者的长度。

先数一个自己能完全跟踪的循环

下面仍是普通函数。const std::vector<int>&只读借用输入，wanted是要找的整数；逐项比较，相等就把found改为true并用break离开循环。comparisons只统计元素与wanted相等的比较次数，没有把循环条件、输出或调用也算进去。

#include <iostream>
#include <vector>

void trace_find(const std::vector<int>& values, int wanted) {
    int comparisons{0};
    bool found{false};
    for (auto position = values.begin(); position != values.end(); ++position) {
        ++comparisons;
        if (*position == wanted) {
            found = true;
            break;
        }
    }
    std::cout << found << ' ' << comparisons << '\n';
}

int main() {
    const std::vector<int> values{3, 1, 4, 1, 5};
    const std::vector<int> empty{};
    trace_find(values, 4);
    trace_find(values, 9);
    trace_find(empty, 4);
    return 0;
}

在[3,1,4,1,5]找4，依次比较3、1、4，第三次成功；找9必须读完五项；空输入一次也不比较。这里的顺序和精确次数来自眼前手写循环。以后调用库函数时，只能依它的公开合同判断，不把这个循环当作所有实现的源码。

大O回答规模增长，不回答多少毫秒

令n为元素数量。访问一个已知合法下标，不需要先扫过前面n项，我们记为O(1)。上面的查找最坏要比较n次，记为O(n)。O是增长上界的记法，常数和低阶项通常被省略；它不是“每次一定做n次”，找到第一项只需一次。

本章默认排序的比较次数为O(n log n)。log描述数量反复减半能分出多少层：对8和16，二进制层数分别为3和4，n log₂ n的量级参照是24和64。这两个数不是std::sort的精确比较次数，也不是本机测量结果。常数成本、输入分布和元素操作都可能影响耗时；当前先学正确使用，可信测量在后面的性能章节单独完成。

10.2 find、sort与accumulate：分别看返回什么、改变什么

本节先不传入自定义函数。<algorithm>提供find和sort，<numeric>提供accumulate。头文件名字不同，不表示需要额外安装库；仍使用本书的C++20编译方式。每个调用都先写三句话：输入是什么、返回什么、原容器有没有变化。

find返回位置，未找到时返回给定的尾后

std::find(values.begin(), values.end(), 4)查找第一个等于4的元素。它返回迭代器，不是元素值，也不是成功与否的bool。先比较position != values.end()，通过后才能用*position读取。重复的4中会找到靠前的那个；没有匹配和空范围都返回所传的end。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{3, 1, 4, 1, 5};
    const auto found = std::find(values.begin(), values.end(), 4);
    if (found != values.end()) {
        std::cout << *found << '\n';
    }
    const auto missing = std::find(values.begin(), values.end(), 9);
    std::cout << (missing == values.end()) << '\n';
    const std::vector<int> empty{};
    std::cout << (std::find(empty.begin(), empty.end(), 4) == empty.end()) << '\n';
    return 0;
}

第一次调用找到4并打印4。后两次分别查找不存在的9和空vector，打印“返回位置是否等于end”的判断结果，均为1。find只查询，原输入不变；得到end时不能先解引用再检查是否存在。

accumulate的第三个参数同时决定起点和累计类型

std::accumulate(first, last, init)从init开始，按输入顺序把元素累加进去，返回累计结果；不改变输入元素。空范围直接得到init，因此从0开始求和时空组得0。对于本节的整数和浮点标量，累计变量的类型由init决定，不能等到结果交给外面的变量时再补救。

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    const std::vector<double> values{1.5, 2.5};
    const int integer_total = std::accumulate(values.begin(), values.end(), 0);
    const double real_total = std::accumulate(values.begin(), values.end(), 0.0);
    const std::vector<int> empty{};
    std::cout << integer_total << '\n';
    std::cout << real_total << '\n';
    std::cout << std::accumulate(empty.begin(), empty.end(), 0) << '\n';
    return 0;
}

对[1.5,2.5]，初值0是int。第一步0+1.5得到1.5，保存回int累计值时成为1；第二步1+2.5得到3.5，再保存为3。初值0.0是double，两步得到1.5、4.0。即使把第一种调用的结果接到double变量里，也只能得到3.0，丢掉的小数不会回来。

本例输出的4代表默认流格式下的double数值4.0，不表示累计类型是int。这里数值有限且可表示；换成大整数或更长输入时，应先复用08.5的数值边界检查，不能认为算法会自动防止有符号溢出。

sort在原范围内排序，不创建新容器

std::sort(values.begin(), values.end())对本节的整数作升序排列。返回类型是void；结果就在传入的可写范围里。array/vector的迭代器支持它需要的随机位置访问；不能据此推断每一种容器都能交给sort。

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> values{3, 1, 2};
    std::sort(values.begin(), values.end());
    for (const int value : values) {
        std::cout << value << '\n';
    }
    const int total = std::accumulate(values.begin(), values.end(), 0);
    std::cout << "sum " << total << " size " << values.size() << '\n';
    return 0;
}

[3,1,2]排序后是[1,2,3]；接着复用刚才的accumulate，从0累加为6，最后打印sum 6 size 3。size仍为3。你可以检查输入和最终输出，但不能仅看这次程序就断言库内部先交换哪两个元素。相等元素的原先相对顺序也不由普通sort保证；本节只有整数值，不把相等值的记录身份当作已保存。

把三个接口放在一张检查表里

读整文件前再补一处简写：对这里的小整数，x *= 2先计算x乘2，再把结果写回同一个x，等价于x = x * 2的当前情形；按值循环写回的是本轮副本，按引用循环写回原元素。这里两个输入2和3及结果都能表示，不把这句话推广成复杂表达式的任意文本替换。

现在可以完整阅读副本与引用的累计示例。范围for的副本/引用已在09.2讲过，本节补齐了其中的accumulate：先改副本，原输入[2,3]仍求得5；后来按引用把原元素乘2，才求得10。因此最后打印before=5 after=10。这份文件可用于综合阅读。

10.3 命名谓词与比较器：把判断交给算法

从普通函数到函数指针

先写一个已经会的函数：bool is_even(int value)用value % 2 == 0回答“它是不是偶数”。谓词（predicate）就是这样的判断操作：输入一个元素，交回真假。我们给本章谓词规定只读输入、不修改序列，判断规则在同一次算法调用期间保持不变。

bool (*test)(int) = is_even;声明test是一个函数指针：它能指向接收一个int、返回bool的函数。圆括号里的*test不能丢；bool* test(int)读起来会变成“返回bool指针的函数”，并非同一种声明。函数名在这里转换成对应的函数地址，没有立即执行is_even；写test(4)时才真正调用它。函数指针也可为空，空指针不能调用；当前例子直接指向已定义的函数。

#include <iostream>

bool is_even(int value) {
    return value % 2 == 0;
}

int main() {
    bool (*test)(int) = is_even;
    std::cout << test(4) << '\n';
    std::cout << test(3) << '\n';
    return 0;
}

4是偶数，3不是，所以输出1、0。普通数据指针用来访问对象，函数指针用来选择要调用的函数；不要对函数指针做元素加减，也不要把调用形式误读成“读取函数里的某个int”。

完整例一：计数与逐项预测

std::count_if(first,last,predicate)对范围中的每项应用谓词，返回满足条件的项数；它不删除元素。调用时传入at_least_three这个名字，算法才会用各个元素去调用它。写成at_least_three(3)则提前算出了一个bool，不再提供可反复调用的判断。

#include <algorithm>
#include <iostream>
#include <vector>

bool at_least_three(int value) {
    return value >= 3;
}

int main() {
    const std::vector<int> readings{3, 1, 4, 1, 5};
    const auto count = std::count_if(readings.begin(), readings.end(), at_least_three);
    std::cout << count << '\n';
    return 0;
}

对[3,1,4,1,5]画五格，分别写true、false、true、false、true，一共有3项满足“至少3”。count_if按合同应用谓词n次；这里记录的是每个元素对应的判定，不主张库必须采用某种内部循环实现。原来的五项和长度不变。

any_of：至少有一项，和总共有几项

std::any_of(first,last,predicate)回答是否至少有一项使谓词为true。返回的是bool；空范围没有满足项，返回false。它只查询，不移除不合格输入。不能把“没有找到负数”误写成“找到了负数”；名称和调用者如何解释结果需要分开。

#include <algorithm>
#include <iostream>
#include <vector>

bool is_negative(int value) {
    return value < 0;
}

int main() {
    const std::vector<int> rejected{-1, 2};
    const std::vector<int> accepted{1, 2};
    const std::vector<int> empty{};
    std::cout << std::any_of(rejected.begin(), rejected.end(), is_negative) << '\n';
    std::cout << std::any_of(accepted.begin(), accepted.end(), is_negative) << '\n';
    std::cout << std::any_of(empty.begin(), empty.end(), is_negative) << '\n';
    return 0;
}

is_negative对[-1,2]得到true，对[1,2]和空组得到false，输出1、0、0。如果产品规则是“不接收负数”，调用者应在第一个结果为true时拒绝；any_of自己没有替你拒绝、抛异常或修改容器。相比count_if需要完整计数，any_of的合同只需确定存在性，最多检查n项；不要依赖谓词被调用的精确次数或用它偷偷累计其它状态。

比较器回答“a应该排在b之前吗”

排序接受两个输入的判断，称为比较器（comparator）。对整数升序，a < b为true表示a在b之前；降序则用a > b。<=不合适，因为相同元素会同时宣称自己排在自己前面。

要求不止这一条。严格弱序（strict weak ordering）需要：任何a都不先于自身；a先于b且b先于c时，a也先于c；若a与b彼此都不先于对方、b与c也如此，那么a与c也应等价。这个“等价”按比较器判断，不要求对象每个成员都相等。两方向不能同时为true。不要用每次变化的计数器、随机选择或循环优先级作排序规则。

<functional>提供std::greater<int>这样的现成函数对象。std::greater<int> greater;创建一个可调用对象，greater(4,1)按大于比较。这里沿用08.1“填写库类型的模板实参”，只学习其调用合同，不要求你实现类的调用运算符。把greater作为sort的第三个参数，就得到整数降序。

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

bool before(int left, int right) {
    return left < right;
}

bool bad_before(int left, int right) {
    return left <= right;
}

int main() {
    std::cout << before(2, 2) << ' ' << before(1, 2) << ' ' << before(2, 1) << '\n';
    std::cout << bad_before(2, 2) << '\n';
    std::vector<int> values{4, 1, 3};
    const std::greater<int> descending{};
    std::sort(values.begin(), values.end(), descending);
    for (const int value : values) {
        std::cout << value << '\n';
    }
    return 0;
}

先看关系检查：严格小于对“同值、自左向右、反方向”分别给出0、1、0；错误的“小于等于”在同值比较上给出1。程序只是把错误关系当普通函数调用观察，没有把坏比较器传给sort。真正排序使用合法的greater，将[4,1,3]排成[4,3,1]。

10.4 lambda与捕获：创建时保存，调用时使用

无捕获lambda先和命名函数做同一道题

[](int value) { return value % 2 == 0; }是一条lambda表达式。方括号说明从外面带进哪些状态，空的[]表示不捕获局部状态；圆括号列参数，花括号包住调用时执行的语句。本例的return表达式是bool，所以编译器推导返回bool。

auto even = ...;保存这个表达式创建的闭包对象（closure object），调用even(4)才执行其函数体。auto让编译器保存它的具体类型，不需要给这种编译器生成的类型取名字。它是一个可调用对象，不是布尔判断已经执行后的结果。

#include <algorithm>
#include <iostream>
#include <vector>

bool is_even(int value) {
    return value % 2 == 0;
}

int main() {
    const std::vector<int> values{1, 2, 3, 4};
    const std::vector<int> empty{};
    const auto even = [](int value) { return value % 2 == 0; };
    std::cout << std::count_if(values.begin(), values.end(), is_even) << '\n';
    std::cout << std::count_if(values.begin(), values.end(), even) << '\n';
    std::cout << std::count_if(empty.begin(), empty.end(), is_even) << '\n';
    std::cout << std::count_if(empty.begin(), empty.end(), even) << '\n';
    return 0;
}

完整例二：外部阈值从3改为5

捕获列表[threshold]在创建lambda时保存threshold的值；[&threshold]借用原threshold，调用时读它当时的值。这里方括号里的&是引用捕获记号，沿用05章的借用期限判断；它不是把threshold变成一个随便可以保存到永久的对象。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> readings{3, 1, 4, 1, 5};
    int threshold{3};
    const auto by_value = [threshold](int value) { return value >= threshold; };
    const auto by_reference = [&threshold](int value) { return value >= threshold; };
    threshold = 5;
    std::cout << std::count_if(readings.begin(), readings.end(), by_value) << '\n';
    std::cout << std::count_if(readings.begin(), readings.end(), by_reference) << '\n';
    return 0;
}

顺序必须写全：先建立threshold=3，再创建两个闭包，之后外部threshold=5，最后分别调用算法。值捕获仍按“至少3”判定[3,1,4,1,5]，结果3；引用捕获在这里按“至少5”，结果1。这两个调用发生时，外部threshold和输入仍在同一个有效作用域内。

回访10.3的any_of时，可用[](int value) { return value < 0; }替换命名is_negative，三组真假结果仍为1、0、0。改变的是表达判断的方式，存在性查询、空组和输入不变这些合同保持。

混合捕获与mutable：哪一个对象被修改

[offset, &calls]分别选择两个名字：offset保存副本，calls借用外部对象。用逗号隔开，每个名字有自己的方式，不是整个闭包只有一种统一的“值或引用模式”。本章用显式名字捕获，让数据关系能直接看出来。

通常不能在lambda体里改写按值捕获的普通成员。把mutable放在参数列表之后、函数体之前，就允许这个闭包在调用中修改自己的副本。它不会把副本改成外部原对象，也不会延长被引用对象的寿命。

#include <iostream>

int main() {
    int offset{2};
    int calls{0};
    auto adjust = [offset, &calls](int value) mutable {
        ++offset;
        ++calls;
        return value + offset;
    };
    const int first = adjust(10);
    const int second = adjust(10);
    std::cout << first << ' ' << second << '\n';
    std::cout << offset << ' ' << calls << '\n';
    return 0;
}

创建时offset的副本为2。第一次用10调用，先把闭包内offset加到3、外部calls加到1，再返回13；第二次同一个闭包继续把自己的offset加到4、calls加到2，返回14。外部offset仍是2。这里明确调用同一个具名闭包两次，没有把“某个算法可能复制可调用对象”的行为当作计数器合同。

普通算法可以复制接收的可调用对象，因此不要在内部mutable状态上计数，然后假定算法返回后原闭包一定保存最终次数。count_if已经直接返回计数；transform应使用不依赖调用次序的变换。当前没有并发调用，mutable也不是线程同步机制。

闭包离开创建函数以后，里面还剩下什么

要演示“把判断返回给调用者”，需要一条窄读法：普通函数也可把返回类型写成auto，编译器从return表达式推导具体返回类型。下面make_at_least返回的是闭包对象，main中的auto则从这次函数调用取得它的类型；两次推导都不是运行时猜类型。当前函数只有一个返回表达式，不涉及泛型函数或模板定义。

#include <iostream>

auto make_at_least(int threshold) {
    return [threshold](int value) { return value >= threshold; };
}

int main() {
    const auto predicate = make_at_least(3);
    std::cout << predicate(4) << '\n';
    std::cout << predicate(2) << '\n';
    return 0;
}

make_at_least的int参数是自己的副本。按值捕获把这个整数保存在返回的闭包中；即使参数在函数返回后结束，之后用4和2调用这个“至少3”的判断仍安全，得到1、0。

如果只把这个函数里的[threshold]改为[&threshold]，交回的是借用局部形参的闭包。函数返回后形参已经结束，再调用闭包读取它会违反生命周期合同。不要运行这个危险变化来猜输出。调用者让闭包活得更久，并不会让形参也活得更久；问题发生在读取已结束的被借用对象，而不是“所有返回lambda都不安全”。

现在也能完整读两种捕获的对照示例：factor从2改为5后，同一输入3分别得到6与15。移动捕获和独占拥有在第14章结合回调学习，本节的按值捕获不承担资源转移合同。

10.5 组合与删除：结果位置和真实长度

transform：写入已有的位置

std::transform(first,last,result,operation)读取输入范围，把每个元素变换后的结果写到从result开始的对应位置，返回输出的尾后位置。输入有n项，目标就要有至少n个可写位置；函数不会看到一个空vector就自动push_back。

下面的std::vector<int> output(input.size());用数量构造建立与输入一样多的int元素，再交出begin。复用08.3的区别：resize创建元素，reserve只预留容量。变换是“当前整数乘2”，在本节的小数值范围内可表示，不依赖其它元素或调用次序。这里输入输出独立，不引入重叠区间的额外情况。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> input{2, 1, 3};
    std::vector<int> output(input.size());
    const auto twice = [](int value) { return value * 2; };
    std::transform(input.begin(), input.end(), output.begin(), twice);
    std::cout << "input\n";
    for (const int value : input) {
        std::cout << value << '\n';
    }
    std::cout << "output\n";
    for (const int value : output) {
        std::cout << value << '\n';
    }
    return 0;
}

[2,1,3]对应输出[4,2,6]，原组仍是[2,1,3]。输出下标和输入下标一一对应，不需要假设库一定先调用第0项再调用第1项。若输入为空，零个结果位置就足够，不能因为目标也为空而误判为必须访问第0项。

remove_if：先形成保留前缀，再交给erase缩短容器

std::remove_if(first,last,predicate)把谓词为false的项保留在范围前部，保留者的相对顺序不变，返回逻辑新末尾。谓词为true表示应从结果中排除，和count_if“统计true”的输出形式不同。

算法处理的是元素范围，不能独自改变vector的size。调用之后，[begin,new_end)是保留结果；[new_end,原end)中的元素仍在容器里，但状态不能当成确定的筛选结果。不要为这个尾部写死一组期望数字。再执行values.erase(new_end, values.end())，才让容器销毁这段尾部并更新长度；erase之后重取位置，沿用09.4的失效规则。

下面的程序还要输出保留了几个元素。对同一个vector中仍然有效的两个迭代器，b - a给出从位置a到位置b的有符号元素距离，不是字节数；反向相减可以得到负数。这是vector的随机访问迭代器支持的操作，不能推广到所有迭代器，也不能跨容器或使用已经失效的位置。本例在erase之前计算kept_end - values.begin()：从开头走到保留前缀末尾要经过两个元素，所以得到2；若没有保留元素，两位置相同，结果为0。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{1, 2, 3, 4, 6};
    const auto remove_value = [](int value) { return value % 2 == 0; };
    std::cout << "before " << values.size() << '\n';
    const auto kept_end = std::remove_if(values.begin(), values.end(), remove_value);
    std::cout << "kept " << (kept_end - values.begin()) << '\n';
    for (auto position = values.begin(); position != kept_end; ++position) {
        std::cout << *position << '\n';
    }
    values.erase(kept_end, values.end());
    std::cout << "after " << values.size() << '\n';
    for (const int value : values) {
        std::cout << value << '\n';
    }
    return 0;
}

[1,2,3,4,6]中偶数使谓词为true，因此保留前缀为[1,3]。刚返回new_end时，原size还是5，前缀长度为2；erase之后size才是2，整个vector才等于[1,3]。没有任何项被排除时new_end等于end，erase空范围；所有项被排除时new_end等于begin，erase后为空。

ranges与投影：先选择比较哪一部分

C++20还提供std::ranges::sort这样的范围算法入口。对本节有名字、仍存活的vector，可直接传整个容器；这是std::ranges下的排序接口，不是把已有std::sort任意省略两个参数，也不等于引入另一份数据。仍由<algorithm>提供本例所需算法。

当元素是07章那样的简单struct时，可能想按其中一个成员排序。投影（projection）是一段从元素取得比较键的操作；比较器再比较这两个键。本例给出无捕获lambda，接收const Reading&并返回其value成员；std::less<int>{}建立现成的int小于比较对象，花括号表示构造这个对象。这里没有成员指针语法，也不要求实现比较器类。

初始化中每个内层{101,3}按成员声明顺序给一条Reading填id和value，外层花括号列出vector拥有的三条记录。仍是07章的聚合初始化与08章的元素列表组合，不是二维整数数组。

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

struct Reading {
    int id;
    int value;
};

int main() {
    std::vector<Reading> readings{{101, 3}, {202, 1}, {303, 2}};
    const auto key = [](const Reading& reading) { return reading.value; };
    std::ranges::sort(readings, std::less<int>{}, key);
    for (const auto& reading : readings) {
        std::cout << reading.id << ' ' << reading.value << '\n';
    }
    return 0;
}

输入记录的id/value分别为101/3、202/1、303/2。投影得到键3、1、2，升序后整条记录按202/1、303/2、101/3排列；不是只把value成员单独改成1、2、3。排序改变记录所在位置，id与value的配对保留。

这些键恰好互不相等，因此结果唯一。若键相等，普通sort仍不承诺保留原先顺序；要满足别的顺序需求，必须另定合同。本节只使用具名拥有者，不把临时容器销毁后的迭代器保存下来使用，也不提前引入views管道。

阶梯四：从空文件独立完成排序与求和

输入[4,1,3]，要求原地升序、输出和、输出长度，再用空组验证。自己选择本章已经教的接口，写清每一步是否修改数据；所有数值都很小、部分和可表示。不参考上面的完整程序，先把每一步预期写在纸上。

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

void sort_and_sum(std::vector<int>& values) {
    std::sort(values.begin(), values.end());
    for (const int value : values) {
        std::cout << value << '\n';
    }
    const int total = std::accumulate(values.begin(), values.end(), 0);
    std::cout << "sum " << total << " size " << values.size() << '\n';
}

int main() {
    std::vector<int> values{4, 1, 3};
    std::vector<int> empty{};
    sort_and_sum(values);
    sort_and_sum(empty);
    return 0;
}

关掉参考后，用一句完整的话说明每个接口的返回值、数据修改与存活要求，再到页末做中英复述。能换一组小输入独立写出来，比只记住算法名字更接近掌握。