泛型算法

标准库没有给每种容器都单独写一套“查找、排序、统计、复制……”成员函数，
而是提供了一组泛型算法（generic algorithms）。

之所以叫“泛型”：

  • 可以用于多种容器
  • 也可以用于内置数组
  • 只要提供合适的迭代器即可

大多数算法定义在：

1
#include <algorithm>

数值类算法主要定义在：

1
#include <numeric>

算法的核心思想

算法不直接依赖容器，而是依赖：

  • 迭代器
  • 元素支持的操作

也就是说：

  • 算法不知道它处理的是 vector、list 还是数组
  • 它只知道“这里有一段可遍历的范围”

算法通常作用于一个范围

大多数算法都处理一个迭代器范围：

1
[first, last)

含义：

  • 从 first 开始
  • 到 last 之前结束
  • last 指向尾后位置，不包含在范围内

例如：

1
find(v.begin(), v.end(), 42);

算法不会改变容器大小

这是非常重要的一点。

算法只操作元素，不直接执行容器操作。

因此：

  • 算法可以改元素值
  • 可以重排元素顺序
  • 但不能直接增加或删除容器中的元素

例如：

  • sort 可以排序
  • fill 可以改值
  • remove 只是“逻辑删除”，不真正缩小容器

算法的常见分类

复习时可分成三大类：

  1. 只读算法：只看数据，不改数据
  2. 写入算法：修改元素值或写到别处
  3. 重排算法：改变元素顺序

只读容器元素算法

特点：

  • 只读取元素
  • 不修改元素内容

可以理解为：
不改数据，只查看数据

查找类

find

在范围中查找某个值第一次出现的位置：

1
auto it = find(v.begin(), v.end(), 42);

返回：

  • 找到：指向该元素的迭代器
  • 没找到：返回 end()

find_if

按条件查找：

1
2
auto it = find_if(v.begin(), v.end(),
                  [](int x) { return x > 10; });

在一个序列中查找另一个子序列：

1
search(a.begin(), a.end(), b.begin(), b.end());

统计类

count

统计某个值出现的次数：

1
int n = count(v.begin(), v.end(), 42);

count_if

按条件统计：

1
2
int n = count_if(v.begin(), v.end(),
                 [](int x) { return x % 2 == 0; });

比较类

equal

判断两个序列对应元素是否都相等：

1
equal(v1.begin(), v1.end(), v2.begin());

注意：

  • 第三个参数是第二个序列的起始位置
  • 要保证第二个序列至少有足够多的元素

mismatch

找出两个序列第一个不匹配的位置：

1
auto p = mismatch(v1.begin(), v1.end(), v2.begin());

返回一对迭代器。

判断类

all_of

是否全部满足条件：

1
all_of(v.begin(), v.end(), [](int x){ return x > 0; });

any_of

是否存在满足条件的元素：

1
any_of(v.begin(), v.end(), [](int x){ return x > 0; });

none_of

是否没有元素满足条件：

1
none_of(v.begin(), v.end(), [](int x){ return x < 0; });

求和类

accumulate

定义在：

1
#include <numeric>

作用：对一段范围求和（或更一般地累计）

1
int sum = accumulate(v.begin(), v.end(), 0);

第三个参数：

  • 是初值
  • 也决定了返回值类型和所使用的运算类型

例如：

1
string s = accumulate(v.begin(), v.end(), string(""));

写容器元素算法

特点：

  • 给已有元素赋值
  • 或把结果写入另一段区域

可以理解为：
修改元素值 / 写入新区间

复制类

copy

把一个范围复制到目标位置：

1
copy(v.begin(), v.end(), out.begin());

要求：

  • 目标范围必须足够大

copy_if

按条件复制：

1
2
copy_if(v.begin(), v.end(), out.begin(),
        [](int x){ return x > 0; });

变换类

transform

对每个元素做变换，并把结果写到目标位置：

1
2
transform(v.begin(), v.end(), out.begin(),
          [](int x){ return x * x; });

也可用于两个序列：

1
2
transform(a.begin(), a.end(), b.begin(), out.begin(),
          [](int x, int y){ return x + y; });

填充类

fill

把范围内元素都改成某个值：

1
fill(v.begin(), v.end(), 0);

fill_n

从某个位置开始填充 n 个元素：

1
fill_n(v.begin(), 5, 0);

注意：

  • 目标位置开始必须至少有 n 个可写元素
  • 算法不会自动扩容

替换类

replace

把等于旧值的元素替换成新值：

1
replace(v.begin(), v.end(), 0, 42);

replace_if

按条件替换：

1
2
replace_if(v.begin(), v.end(),
           [](int x){ return x < 0; }, 0);

删除式算法

remove

删除某值的“逻辑效果”：

1
auto new_end = remove(v.begin(), v.end(), 0);

注意：

  • 不真正删除元素
  • 只是把“不该保留的元素”挪到后面去
  • 返回新的逻辑尾后迭代器

通常要配合容器的 erase：

1
v.erase(remove(v.begin(), v.end(), 0), v.end());

这叫：

erase-remove 惯用法

remove_if

按条件“逻辑删除”：

1
2
3
v.erase(remove_if(v.begin(), v.end(),
                  [](int x){ return x < 0; }),
        v.end());

unique

去掉相邻重复元素：

1
2
auto new_end = unique(v.begin(), v.end());
v.erase(new_end, v.end());

注意：

  • 只去掉连续相等的重复项
  • 若想“整个序列去重”，通常先排序再 unique
1
2
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

算法不检查写空间是否足够

这是常见错误来源。

例如：

1
2
vector<int> v;
fill_n(v.begin(), 10, 0);   // 错误：v 是空的

因为：

  • 算法不会扩容
  • v.begin() 并没有 10 个可写位置

解决方法：插入迭代器

插入迭代器会把“赋值”变成“插入”。

常见类型：

  • back_inserter(c)
  • front_inserter(c)
  • inserter(c, p)

例如：

1
2
vector<int> v;
fill_n(back_inserter(v), 10, 0);   // 正确

这样算法写一个元素，容器就新增一个元素。

重排容器元素算法

特点：

  • 改变元素顺序
  • 不改变容器大小

可以理解为：
改变顺序

排序

sort

排序：

1
sort(v.begin(), v.end());

默认按 < 升序排序。

也可自定义比较规则：

1
2
sort(v.begin(), v.end(),
     [](int a, int b){ return a > b; });

注意：

  • sort 需要随机访问迭代器
  • 所以 不能用于 list / forward_list

stable_sort

稳定排序：

1
stable_sort(v.begin(), v.end(), cmp);

特点：

  • 若两个元素“相等”，保持它们原来的先后顺序

反转

reverse

反转顺序：

1
reverse(v.begin(), v.end());

rotate

旋转序列：

1
rotate(v.begin(), v.begin() + 2, v.end());

效果：

  • 把中间位置当作新的开头

分区

partition

按条件分成两部分：

1
2
partition(v.begin(), v.end(),
          [](int x){ return x % 2 == 0; });

结果：

  • 满足条件的放前面
  • 不满足的放后面
  • 各自内部顺序不保证

stable_partition

稳定分区：

  • 保留原来的相对顺序

排列

next_permutation

生成下一个字典序排列：

1
next_permutation(v.begin(), v.end());

常用于全排列枚举。

常用算法小结

查找

  • find
  • find_if
  • search

统计

  • count
  • count_if

比较

  • equal
  • mismatch

判断

  • all_of
  • any_of
  • none_of

数值

  • accumulate

写入/复制

  • copy
  • copy_if
  • transform
  • fill
  • fill_n
  • replace
  • replace_if

删除式

  • remove
  • remove_if
  • unique

重排

  • sort
  • stable_sort
  • reverse
  • rotate
  • partition
  • next_permutation

lambda 表达式

算法经常需要一个“可调用对象”，例如比较规则、判断条件。

lambda 就是一种临时定义的小函数对象。

形式：

1
[capture list] (parameter list) -> return type { function body }

例如：

1
[](int a, int b) { return a < b; }

基本理解

可以把 lambda 理解成：

  • 一个未命名函数
  • 通常写在调用现场
  • 特别适合传给算法

例如：

1
2
sort(v.begin(), v.end(),
     [](int a, int b) { return a > b; });

lambda 的组成

捕获列表 []

决定能否使用外部局部变量

参数列表 ()

像普通函数参数

返回类型

通常可省略，由编译器推断

函数体 {}

实际执行逻辑

lambda 的捕获

空捕获

1
[]

不能使用所在函数的局部变量。

值捕获

1
2
[=]
[x, y]

含义：

  • 把外部变量拷贝一份到 lambda 内部
  • 默认不能修改这些拷贝

引用捕获

1
2
[&]
[&x]

含义：

  • 直接使用外部变量本身
  • 在 lambda 中改它，会影响外部变量

混合捕获

1
2
[&, x]
[=, &x]

含义：

  • 一部分按引用
  • 一部分按值

规则：

  • [&, x]：默认引用，x 按值
  • [=, &x]：默认按值，x 按引用

可变 lambda

默认情况下，值捕获的变量在 lambda 体内不能修改。

若想修改值捕获的副本，要用 mutable：

1
2
int x = 10;
auto f = [x]() mutable { ++x; };

注意：

  • 改的是拷贝，不是原变量

lambda 返回类型

很多情况下返回类型可自动推断：

1
[](int x) { return x * 2; }

若函数体复杂、返回类型不明显，可显式写：

1
2
3
4
[](int x) -> bool {
    if (x > 0) return true;
    else return false;
}

复习时记住：

  • 单一 return 时通常可省略返回类型
  • 若逻辑复杂，最好显式写出

bind

bind 定义在：

1
#include <functional>

作用：

  • 把一个可调用对象重新包装成新的可调用对象
  • 可调整参数顺序、固定部分参数

形式：

1
auto newCallable = bind(callable, arg_list);

占位符

bind 中常使用占位符：

  • _1
  • _2
  • _3

表示新函数调用时传入参数的位置。

例如：

1
2
using std::placeholders::_1;
using std::placeholders::_2;

例子

1
2
3
4
5
bool check_size(const string &s, string::size_type sz) {
    return s.size() >= sz;
}

auto f = bind(check_size, _1, 6);

此时：

1
f("hello");   // 等价于 check_size("hello", 6)

交换参数顺序

1
auto g = bind(check_size, _2, _1);

调用：

1
g(6, "hello");

等价于：

1
check_size("hello", 6);

bind 的地位

现代 C++ 中，很多场景更推荐直接用 lambda，因为：

  • 更直观
  • 更易读
  • 更灵活

所以复习时：

  • 知道 bind 能做什么
  • 但实践中常优先写 lambda

标准库函数对象

标准库提供了一批函数对象类，定义在头文件：

1
#include <functional>

分为三类：

算术函数对象

类模板 含义
plus<T> 加法
minus<T> 减法
multiplies<T> 乘法
divides<T> 除法
modulus<T> 取模
negate<T> 取负

关系函数对象

类模板 含义
equal_to<T> ==
not_equal_to<T> !=
greater<T> >
greater_equal<T> >=
less<T> <
less_equal<T> <=

逻辑函数对象

类模板 含义
logical_and<T> &&
logical_or<T> `
logical_not<T> !

示例

1
2
plus<int> add;
cout << add(3, 4);   // 7

function

标准库 function 定义在：

1
#include <functional>

作用：

用统一方式保存“具有某种调用形式”的可调用对象

定义方式

1
function<int(int, int)> f;

表示 f 可以保存任何“接受两个 int，返回 int”的可调用对象。

常见操作

操作 含义
function<T> f; 空 function
function<T> f(obj); 用可调用对象初始化
f(args) 调用保存的对象
if (f) 判断是否保存了对象

示例

1
2
3
4
5
function<int(int, int)> f1 = plus<int>();
function<int(int, int)> f2 = [](int a, int b) { return a * b; };

cout << f1(2, 3);   // 5
cout << f2(2, 3);   // 6

作用总结

function 的价值在于：

可以把“不同类型但调用形式相同”的可调用对象统一存起来

可调用对象

C++ 中“可调用对象”不仅仅是函数。

包括：

  • 普通函数
  • 函数指针
  • lambda 表达式
  • bind 生成的对象
  • 重载了 operator() 的类对象

调用形式

不同可调用对象可能类型不同，但只要它们具有相同的：

  • 参数类型
  • 返回类型

就可以认为它们有相同的调用形式

例如：

1
int(int, int)

表示：

  • 接受两个 int
  • 返回一个 int

插入迭代器

插入迭代器是很重要的“算法搭档”。

定义在：

1
#include <iterator>

常见形式：

1
2
3
back_inserter(c)
front_inserter(c)
inserter(c, p)

back_inserter

1
copy(v.begin(), v.end(), back_inserter(out));

作用：

  • 每次写入时调用 push_back

适用于支持 push_back 的容器。

front_inserter

1
front_inserter(lst)

作用：

  • 每次写入时调用 push_front

适用于支持 push_front 的容器。

inserter

1
inserter(c, p)

作用：

  • 每次写入时调用 insert

适用范围更广。

迭代器进阶：迭代器类别

不同算法对迭代器能力要求不同。

输入迭代器

能读，能向前移动。
用于单遍读取。

输出迭代器

能写，能向前移动。
用于输出结果。

前向迭代器

可读写，多遍扫描，单向前进。

双向迭代器

在前向基础上，支持 --

例如：

  • list
  • set
  • map

随机访问迭代器

支持：

  • it + n
  • it - n
  • 比较大小
  • 下标

例如：

  • vector
  • deque
  • array
  • string

为什么重要

因为不是所有算法都适用于所有容器。

例如：

  • sort 需要随机访问迭代器
  • 所以不能对 list 直接用 sort

特定容器算法

有些容器提供了专有成员算法，尤其是链表类容器。

list 和 forward_list 的成员算法

由于链表不支持随机访问，所以很多操作要用成员函数版本。

常见：

  • lst.sort()
  • lst.merge(other)
  • lst.remove(val)
  • lst.reverse()
  • lst.unique()

例如：

1
2
list<int> lst = {3, 1, 2};
lst.sort();   // 正确

而：

1
sort(lst.begin(), lst.end()); // 错误

因为 list 迭代器不是随机访问迭代器。

成员 remove 与算法 remove 的区别

算法 remove

1
remove(v.begin(), v.end(), 0);
  • 不改变容器大小
  • 只是返回新的逻辑结尾

list 成员 remove

1
lst.remove(0);
  • 真正删除链表中的元素
  • 会改变容器大小

这是一个高频易混点。

易错点总结

算法操作的是迭代器范围，不是容器本身

算法通常不改变容器大小

尤其：

  • remove
  • unique

都不会真的删容器元素，要配合 erase

写入算法不会自动检查目标空间够不够

空间不够时要：

  • 先分配足够空间
  • 或使用插入迭代器

sort 不能用于 list 和 forward_list

因为它们不支持随机访问迭代器

unique 只去掉相邻重复元素

若要全局去重，通常先排序

lambda 的值捕获默认不能改，想改要 mutable

bind 中 _1、_2 是占位符

定义在：

1
std::placeholders

优先使用 lambda，bind 作为补充了解

小结

泛型算法的主线非常清晰：

  1. 算法通过迭代器操作范围
  2. 算法与容器分离
  3. 算法大致分为：只读、写入、重排
  4. 很多算法常与 lambda、插入迭代器配合
  5. 注意算法不会自动扩容，也通常不会改变容器大小

优先掌握这些高频算法：

  • find
  • count
  • equal
  • accumulate
  • copy
  • transform
  • fill
  • replace
  • remove
  • unique
  • sort
  • stable_sort
  • reverse
  • partition

以及配套知识：

  • lambda
  • bind
  • 插入迭代器
  • 迭代器类别
  • list 的成员算法