# STL 算法、函数对象与 Lambda

> [!info] 学习导航
> 返回：[[C++ 学习指南]]
> 前置知识：[[计算机系/C++/14 STL 基础、容器与迭代器|STL 基础、容器与迭代器]]、[[计算机系/C++/15 STL 常用容器|STL 常用容器]]

C++ 标准库中的 \<algorithm> 头文件提供了一组用于操作容器（如数组、向量、列表等）的算法。这些算法包括排序、搜索、复制、比较等，它们是编写高效、可重用代码的重要工具。

\<algorithm> 头文件定义了一组模板函数，这些函数可以应用于任何类型的容器，只要容器支持迭代器。这些算法通常接受两个或更多的迭代器作为参数，表示操作的起始和结束位置。

**语法**

大多数 \<algorithm> 中的函数都遵循以下基本语法：

```cpp
algorithm_name(container.begin(), container.end(), ...);
```

这里的 container 是一个容器对象，begin() 和 end() 是容器的成员函数，返回指向容器开始和结束的迭代器。

**std::for_each**: 对区间内的每个元素执行操作。

```cpp
std::for_each(vec.begin(), vec.end(), [](int& x) { x += 1; });
```

**1. 排序算法**

函数：sort

定义：对容器中的元素进行排序。

语法：

```cpp
sort(container.begin(), container.end(), compare_function);
```

**2. 搜索算法**

函数：find

定义：在容器中查找与给定值匹配的第一个元素。

语法：

```cpp
auto it = find(container.begin(), container.end(), value);
```

**3. 复制算法**

函数：copy

定义：将一个范围内的元素复制到另一个容器或数组。

语法：

```cpp
copy(source_begin, source_end, destination_begin);
```

**4. 比较算法**

函数：equal

定义：比较两个容器或两个范围内的元素是否相等。

语法：

```cpp
bool result = equal(first1, last1, first2);
```

或

```cpp
bool result = equal(first1, last1, first2, compare_function);
```

**5. 修改算法**

**std::reverse**: 反转区间内的元素顺序。

```cpp
std::reverse(vec.begin(), vec.end());
```

**std::fill**: 将指定区间内的所有元素赋值为某个值。

```cpp
std::fill(vec.begin(), vec.end(), 0); // 所有元素设为 0
```

**std::replace**: 将区间内的某个值替换为另一个值。

```cpp
std::replace(vec.begin(), vec.end(), 1, 99); // 将所有 1 替换为 99
```

**std::copy**: 将区间内的元素复制到另一个区间。

```cpp
std::vector<int> vec2(6);
std::copy(vec.begin(), vec.end(), vec2.begin());
```

## 函数对象

当一个类重载了 **operator()**，其实例就被称为**函数对象（Function Object）** 或 **仿函数（Functor）**。

用户用自定义对象通过运算符（）来调用函数

C++规定调用运算符只能重载为类的成员函数

返回值类型 operator() (形参表)


```cpp
class MyFunctor {
public:
// 重载 operator()
  return_type operator()(parameters) {
// 实现逻辑
  }
};
class Adder {
public:
  int operator()(int a, int b) {
    return a + b;
  }
};
int main() {
  Adder add; // 创建函数对象
  int result = add(3, 4); // 调用 operator()，输出 7
  std::cout << result;
}
```

**许多 STL 算法（如 std::sort、std::transform）接受函数对象作为参数，比函数指针更灵活。
 例如，用仿函数自定义排序规则：**

```cpp
class Compare {
public:
  bool operator()(int a, int b) {
    return a > b; // 降序排序
  }
};
int main() {
  std::vector<int> v = {5, 2, 8, 1};
  std::sort(v.begin(), v.end(), Compare());
// v 变为 {8, 5, 2, 1}
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class obj
{
public:
  obj(int a_) : a(a_) {}
// 成员函数
  void show() const
  {
    cout << "Value of a: " << a << endl;
  }
// 成员函数重载
  int getA() const
  {
    return a;
  }
// 比较类应该定义为public
  class compare
  {
  public: // 必须添加public，否则sort无法访问operator()
```

​    **bool operator()(const obj &lhs, const obj &rhs) const**

```cpp
    {
      return lhs.getA() < rhs.getA();
    }
  };
private:
  int a;
};
int main()
{
  vector<obj> v;
  v.push_back(obj(3)); // 调整顺序以测试排序
  v.push_back(obj(1));
  v.push_back(obj(2));
// 使用成员比较类
  sort(v.begin(), v.end(), obj::compare()); // 创建compare的临时对象
  for (const auto &o : v)
  {
    o.show();
  }
  return 0;
}
```

**那么，有以下三种方式进行比较：**

**1、**

**Obj类中包含compare类**

```cpp
 class compare
  {
  public: // 必须添加public，否则sort无法访问operator()
```

​    **bool operator()(const obj &lhs, const obj &rhs) const**

```cpp
    {
      return lhs.getA() < rhs.getA();
    }
  };
  sort(v.begin(), v.end(), obj::compare()); // 创建compare的临时对象
```

**2**

**考虑将比较运算符重载为成员函数：如果obj类需要频繁比较，可以直接重载operator<：**

**Obj类中**

```cpp
bool operator<(const obj& rhs) const {
  return a < rhs.a;
}
```

**然后直接调用：**

```cpp
sort(v.begin(), v.end());
```

**3、**

```cpp
Bool compare(const obj &r1,const obj&r2)
{
```

**Return r1.a<r2.a**

```cpp
}
```

**然后调用**

**Sort(v.begin,v,end(),compare)**

**4lambda表达式**

```cpp
sort(v.begin(), v.end(), [](const obj& a, const obj& b) {
  return a.a < b.a;
});
```

### (1) Lambda 表达式是简化的函数对象

**C++11 的 Lambda 本质上是一个匿名函数对象：**

```cpp
auto adder = [](int a, int b) { return a + b; };
std::cout << adder(3, 4); // 输出 7
```

**编译器会将 Lambda 转换为类似下面的类：**

```cpp
class __AnonymousLambda {
public:
  int operator()(int a, int b) const {
    return a + b;
  }
};
```

### (2) 标准库中的函数对象

**\<functional> 头文件提供了许多预定义的函数对象：**

```cpp
#include <functional>
std::plus<int> add; // 仿函数，等价于 operator+
std::cout << add(3, 4); // 输出 7
```

### `std::sort` 排序

**(1) 默认排序（升序：std::less）**

```cpp
#include <algorithm>
#include <functional>
#include <vector>
int main() {
  std::vector<int> v = {5, 2, 8, 1};
// 显式使用 std::less（默认行为，可省略）
  std::sort(v.begin(), v.end(), std::less<int>());
// v 变为 {1, 2, 5, 8}
}
```

- **std::less\<int>() 是一个函数对象，内部重载了 operator()，比较两个元素是否满足 a <     b。**
- **如果省略第三个参数，std::sort 默认使用 std::less。**

**(2) 降序排序（std::greater）**

```cpp
std::sort(v.begin(), v.end(), std::greater<int>());
```

### `std::function` 模板

std::function 是一个模板类，可以存储、调用和复制任何可调用对象，比如函数、lambda 表达式或函数对象。


实例

```cpp
#include <iostream>
#include <functional>
void greet() {
  std::cout << "Hello, World!" << std::endl;
}
int main() {
  std::function<void()> f = greet; // 使用函数
  f(); // 输出: Hello, World!
  std::function<void()> lambda = []() {
    std::cout << "Hello, Lambda!" << std::endl;
  };
  lambda(); // 输出: Hello, Lambda!
  return 0;
}
```

std::bind 允许我们创建一个可调用对象，它在调用时会将给定的参数绑定到一个函数或函数对象。


实例

```cpp
#include <iostream>
#include <functional>
int add(int a, int b) {
  return a + b;
}
int main() {
  auto bound_add = std::bind(add, 5, std::placeholders::_1);
  std::cout << bound_add(10) << std::endl; // 输出: 15
  return 0;
}
```

在这个例子中，std::placeholders::_1 是一个占位符，它在调用 bound_add 时会被实际的参数替换。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
bool compare(int a, int b) {
  return a < b;
}
int main() {
  std::vector<int> v = {5, 3, 9, 1, 4};
  std::sort(v.begin(), v.end(), compare); // 使用自定义比较函数
  for (int i : v) {
    std::cout << i << " "; // 输出: 1 3 4 5 9
  }
  std::sort(v.begin(), v.end(), std::less<int>()); // 使用标准库比较函数对象
  for (int i : v) {
    std::cout << i << " "; // 输出: 1 3 4 5 9
  }
  return 0;
}
```

### Lambda 表达式

c++在c++11标准中引入了[lambda表达式](https://zhida.zhihu.com/search?content_id=173533885&content_type=Article&match_order=1&q=lambda表达式&zhida_source=entity)，一般用于定义匿名函数，使得代码更加灵活简洁。lambda表达式与普通函数类似，也有参数列表、返回值类型和函数体，只是它的定义方式更简洁，并且可以在函数内部定义。

**什么是Lambda表达式**

最常见的lambda的表达式写法如下

```cpp
auto plus = [] (int v1, int v2) -> int { return v1 + v2; }
int sum = plus(1, 2);
[capture-list] (parameters) mutable -> return-type { body }
```

-  **[capture]**：捕捉列表。捕捉列表总是出现在     lambda 表达式的开始处。事实上，[] 是     lambda 引出符。编译器根据该引出符判断接下来的代码是否是 lambda 函数。捕捉列表能够捕捉上下文中的变量供 lambda 函数使用。
-  (parameters)：参数列表。与普通函数的参数列表一致。如果不需要参数传递，则可以连同括号 () 一起省略。
-  **mutable**：mutable 修饰符。默认情况下，lambda 函数总是一个 const 函数，mutable 可以取消其常量性。在使用该修饰符时，参数列表不可省略（即使参数为空）。
-  **->return_type**：返回类型。用追踪返回类型形式声明函数的返回类型。出于方便，不需要返回值的时候也可以连同符号 -> 一起省略。此外，在返回类型明确的情况下，也可以省略该部分，让编译器对返回类型进行推导。
-  **{statement}**：函数体。内容与普通函数一样，不过除了可以使用参数之外，还可以使用所有捕获的变量。

在 lambda 函数的定义式中，参数列表和返回类型都是可选部分，而捕捉列表和函数体都可能为空，C++ 中最简单的 lambda 函数只需要声明为：

```cpp
[]{};
```

**1. (parameters)：Lambda 的参数表**

**(parameters) 表示 Lambda 函数的参数列表，和普通函数的参数列表语法一致。**

**如果没有参数，可以写成 ()，表示无参 Lambda：**

```cpp
auto func = []() { return 42; }; // 无参 Lambda
```

**如果 Lambda 不需要参数，() 可以省略：**

```cpp
auto func = [] { return 42; }; // 等效于上一行（省略 ()）
```

**2. mutable 和 -> return-type 是可选的**

**mutable：**

**默认情况下，Lambda 的 operator() 是 const 的，即不能修改按值捕获的变量。如果加上 mutable，则可以修改：**

```cpp
int x = 0;
auto lambda = [x]() mutable { x++; }; // 允许修改 x（但修改的是副本，不影响外部的 x）
```

**如果没有 mutable，则 () 可以省略：**

```cpp
auto lambda = [] { return 42; }; // 无参数、无 mutable、无返回类型声明
```

**如果有 mutable，则 () 必须保留（即使无参数）：**

```cpp
auto lambda = []() mutable { return 42; }; // 正确
// auto lambda = [] mutable { ... };    // 错误！必须有 ()
```

**-> return-type：**

**用于显式指定 Lambda 的返回类型（通常可自动推导，但某些情况需要手动声明）：**

```cpp
auto lambda = [](int a, int b) -> int { return a + b; };
```

**如果省略 -> return-type，编译器会自动推导返回类型：**

```cpp
auto lambda = [](int a, int b) { return a + b; }; // 返回类型自动推导为 int
```

**如果 Lambda 包含多条返回语句且类型不一致，必须显式指定返回类型：**

```cpp
auto lambda = [](int x) -> double {
  if (x > 0) return 3.14; // 返回 double
  else return 0; // 返回 int，需统一类型
};
```

**Lambda 形式   是否合法    说明**

**[] { ... }**  **✅ 合法 无参数、无 mutable、无返回类型声明（() 可省略）。**

**[]() { ... }** **✅ 合法 无参数，但显式写出 ()。**

**[]() mutable { ... }** **✅ 合法 无参数，但有 mutable，必须保留 ()。**

**[] mutable { ... }**  **❌ 错误 缺少 ()，即使无参数，mutable 也必须跟在 () 后。**

`[] -> int { ... }` ❌ 错误：缺少 `()`，即使无参数、有返回值类型，也必须有 `()`。
**[](int x) -> int { ... }**   **✅ 合法 显式指定参数和返回类型。**

**[](auto x) { ... }**   **✅ 合法 C++14 起支持泛型 Lambda（参数类型自动推导）。**


**在Lambda表达式内可以访问当前作用域的变量，这是Lambda表达式的闭包（Closure）行为。**

**传递的是副本**

 **与JavaScript闭包不同，C++变量传递有传值和传引用的区别。可以通过前面的[]来指定：**

**[]   // 沒有定义任何变量。使用未定义变量会引发错误。**

**[x, &y] // x以传值方式传入（默认），y以引用方式传入。**

**[&]   // 任何被使用到的外部变量都隐式地以引用方式加以引用。**

**[=]   // 任何被使用到的外部变量都隐式地以传值方式加以引用。**

**[&, x] // x显式地以传值方式加以引用。其余变量以引用方式加以引用。**

**[=, &z] // z显式地以引用方式加以引用。其余变量以传值方式加以引用。**

**另外有一点需要注意。对于[=]或[&]的形式，lambda 表达式可以直接使用 this 指针。但是，对于[]的形式，如果要使用 this 指针，必须显式传入. [this]() { this->someFunc(); }();**

**Lambda表达式无法修改通过复制形式捕捉的变量，因为函数调用运算符的重载方法是const属性的。有时候，你想改动传值方式捕获的值，那么就要使用mutable，**


| **捕获方式**             | **语法**                   | **能否修改捕获的变量**     | **影响外部变量** |
| ------------------------ | -------------------------- | -------------------------- | ---------------- |
| **值捕获 [x]**           | **默认**                   | **❌ 不能（const）**        | **❌ 不影响**     |
| **值捕获 [x] + mutable** | **[x]()  mutable { ... }** | **✅ 能（修改副本）**       | **❌ 不影响**     |
| **引用捕获 [&x]**        | **[&x]  { ... }**          | **✅ 能（直接修改原变量）** | **✅ 影响**       |


**[this]: 通过引用捕获当前对象（对象本身） [\*this]: 通过传值捕获当前对象（对象拷贝，且只是一个地址值）**

## `std::sort` 比较器问题

是的，**std::sort** 要求比较器必须是一个 **二元谓词（Binary Predicate）**，即能接受两个参数并返回 **bool** 值的可调用对象。具体规则如下：


**1. std::sort 对比较器的要求**

- **输入**：两个参数（容器中的元素）。
- **输出**：**bool**（表示是否第一个参数应排在第二个参数之前）。
- **严格弱序**：比较器必须满足以下条件：
  - 反对称性：若 **comp(a, b) == true**，则 **comp(b,      a) == false**。
  - 传递性：若 **comp(a, b) && comp(b, c)**，则 **comp(a, c)**。
  - 不可反身性：**comp(a, a)** 必须为 **false**。


**2. 为什么必须是二元函数对象？**

**std::sort** 的排序过程需要 **任意比较两个元素** 以确定它们的相对顺序。因此比较器必须：

- 能独立接受两个参数（不能依赖对象实例状态）。
- 不修改被比较的元素（除非明确使用 **mutable** Lambda）。


**3. 四种实现方式的二元性验证**

**（1）嵌套比较类（Functor）**

```cpp
class compare {
public:
  bool operator()(const obj& a, const obj& b) const {
    return a.getA() < b.getA();
  }
};
```

- **二元性**：显式接受两个参数 **(a, b)**，符合要求。

**（2）重载 operator<**

```cpp
bool operator<(const obj& a, const obj& b) {
  return a.getA() < b.getA();
}
```

- **二元性**：虽然是成员函数，但作为自由函数或友元时，仍接受两个参数。

**（3）普通函数**

```cpp
bool compare(const obj& a, const obj& b) {
  return a.getA() < b.getA();
}
```

- **二元性**：直接满足二元谓词要求。

**（4）Lambda 表达式**

```cpp
[](const obj& a, const obj& b) { return a.getA() < b.getA(); }
```

- **二元性**：Lambda 的 **operator()** 隐式生成二元函数。


**4. 为什么成员函数形式的 operator() 不行？**

你之前提问的以下形式无法用于 **std::sort**：

```cpp
bool operator()(const obj& rhs) const { return a < rhs.getA(); }
```

- **问题**：这是一个 **一元谓词**（隐含依赖 **this** 对象），而 **std::sort** 需要能比较任意两个元素的 **二元谓词**。
- **错误示例**：

```cpp
sort(v.begin(), v.end(), obj::compare()); // 错误：compare 必须能接受两个参数
```


**5. 关键总结**

| **比较器类型**       | **是否满足 std::sort 要求** | **原因**                                                     |
| -------------------- | --------------------------- | ------------------------------------------------------------ |
| 二元函数对象         | ✅ 是                        | 显式接受两个参数（如 Functor、普通函数、Lambda）。           |
| 重载的 **operator<** | ✅ 是                        | 作为自由函数或友元时是二元的。                               |
| 一元成员函数         | ❌ 否                        | 依赖 **this** 对象，无法比较任意两个元素。                   |
| 静态成员函数         | ✅ 是                        | 可定义为二元函数（如 **static bool  compare(const obj& a, const obj& b)**）。 |


**6. 最终结论**

**std::sort** **必须使用二元函数对象**，因为它需要在排序过程中动态比较容器中的任意两个元素。四种实现方式中：

- **嵌套比较类**、**普通函数**、**Lambda** 直接满足二元性。
- **operator<** 需定义为自由函数或友元函数（二元形式）。
- 成员函数形式的 **operator()**（一元）**不满足要求**。

所以说opertaor《即可是一个参数也可是两个参数？？

## 相关内容
- [[计算机系/C++/09 运算符重载|运算符重载]]

---

## 学习导航
- 上一篇：[[计算机系/C++/15 STL 常用容器|STL 常用容器]]
- 返回目录：[[C++ 学习指南]]