仿函数

仿函数

STL 中的仿函数（Functors / Function Objects）

名称来源

• Functors（仿函数）：早期命名，中文翻译独特、形象。
• Function Objects（函数对象）：C++ 标准采用的正式名称，更贴切其“对象具有函数特质”的本质。

概念

• 仿函数是一个行为类似函数的对象。

• 本质上就是一个类（class），其中重载了函数调用运算符 operator()。

• 调用时可以写作：

  greater<int> ig;
  ig(4, 6);             // 调用 ig.operator()(4,6)
  greater<int>()(6, 4); // 使用临时对象调用
  

作用

• 在 STL 算法中，仿函数用于作为 “策略参数” 传入算法。

• STL 常提供两种算法版本：

  1. 默认版本：采用常见操作（如 operator+, operator<）。
  2. 泛化版本：允许用户传入仿函数，自定义行为。
  • 例：
    • accumulate() 默认执行加法，但可以传入仿函数定义其他累积操作。
    • sort() 默认使用 < 比较，但可以传入 greater<> 或用户自定义的比较仿函数。

与函数指针的区别

• 函数指针 也能传递“操作”，但存在局限：
  • 不能与 STL 其它组件（如 适配器 adapters）良好结合。
  • 可扩展性、抽象性较差。
• 仿函数对象：
  • 是类对象，可以携带状态。
  • 可与 STL 的 适配器 配合，形成更灵活的抽象。

使用语法

• 两种常见用法：

  1. 具名对象：

     greater<int> ig;
     cout << boolalpha << ig(4, 6); // false
     

  2. 临时对象（主流用法）：

     cout << greater<int>()(6, 4); // true
     

分类

• 按操作数个数：
  • 一元仿函数（Unary Functor）
  • 二元仿函数（Binary Functor）
• 按功能：
  • 算术运算（Arithmetic）
  • 关系运算（Relational）
  • 逻辑运算（Logical）

头文件

• 使用 STL 内建仿函数需包含：

  #include <functional>
  

• 在 SGI STL 中，具体定义位于 <stl_function.h>。

仿函数的可配接性 (Adaptability)

仿函数在STL中虽然简单，却能作为“策略”让算法表现出不同的行为。为了能与函数配接器组合使用，仿函数必须具备可配接性。这就要求仿函数定义一些相应型别，用来表示参数类型和返回值类型。相应型别只是通过 typedef 在编译期完成，不影响运行时效率。SGI STL 在 <stl_function.h> 中提供了 unary_function<Arg, Result> 和 binary_function<Arg1, Arg2, Result> 两个基类，它们没有数据成员或函数，只有必要的型别定义。任何自定义仿函数只要继承这两个基类之一，就能自动获得所需的相应型别，从而具备可配接性。

unary_function

unary_function 用来表示一元仿函数的参数型别和返回值型别。定义如下：

// 每一个 Adaptable Unary Function 都应该继承此类
template <class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};

一旦某个仿函数继承了 unary_function，用户就可以通过 argument_type 和 result_type 取得其参数与返回值型别。例如：

// 继承 unary_function 的一元仿函数
template <class T>
struct negate : public unary_function<T, T> {
    T operator()(const T& x) const { return -x; }
};

// 配接器：对某个仿函数取逻辑负值
template <class Predicate>
class unary_negate {
public:
    bool operator()(const typename Predicate::argument_type& x) const {
        // ...
    }
};

binary_function

binary_function 用来表示二元仿函数的第一参数型别、第二参数型别和返回值型别。定义如下：

// 每一个 Adaptable Binary Function 都应该继承此类
template <class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};

一旦某个仿函数继承了 binary_function，用户就可以通过 first_argument_type、second_argument_type 和 result_type 取得其相应型别。例如：

// 继承 binary_function 的二元仿函数
template <class T>
struct plus : public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x + y; }
};

// 配接器：将二元仿函数转化为一元仿函数
template <class Operation>
class binder1st {
protected:
    Operation op;
    typename Operation::first_argument_type value;
public:
    typename Operation::result_type
    operator()(const typename Operation::second_argument_type& x) const {
        // ...
    }
};

算术类 (Arithmetic) 仿函数

STL 内建了 6 种算术类仿函数，支持加、减、乘、除、取模和取负运算。其中只有取负是 一元运算，其余都是 二元运算：

• plus<T>：加法
• minus<T>：减法
• multiplies<T>：乘法
• divides<T>：除法
• modulus<T>：取模
• negate<T>：取负

这些仿函数都继承自 unary_function 或 binary_function，提供了参数和返回值的相应型别定义。例如：

template <class T>
struct plus : public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x + y; }
};

template <class T>
struct negate : public unary_function<T, T> {
    T operator()(const T& x) const { return -x; }
};

使用示例

仿函数对象的使用与普通函数完全一致，可以通过 具名对象 或 临时对象 调用：

#include <iostream>
#include <functional>
using namespace std;

int main() {
    plus<int> plusobj;
    minus<int> minusobj;

    cout << plusobj(3, 5) << endl;        // 8
    cout << minusobj(3, 5) << endl;       // -2

    // 临时对象调用
    cout << plus<int>()(3, 5) << endl;    // 8
    cout << minus<int>()(3, 5) << endl;   // -2
}

在实际应用中，算术仿函数主要与 STL 算法 搭配。例如：

// 用 multiplies<int>() 计算所有元素的连乘积
accumulate(iv.begin(), iv.end(), 1, multiplies<int>());

证同元素 (Identity Element)

所谓某个运算 p 的 证同元素，是指对任意数值 A，满足 A ⊕ e = A 的元素 e。

• 加法的证同元素是 0
• 乘法的证同元素是 1

SGI STL 还提供了 identity_element() 辅助函数（非标准），用于快速获取：

template <class T>
inline T identity_element(plus<T>) { return T(0); }

template <class T>
inline T identity_element(multiplies<T>) { return T(1); }

其中乘法的证同元素 1 在 <stl_numeric.h> 的 power() 算法中会被实际使用。

关系运算类 (Relational) 仿函数

STL 内建了 6 种关系运算类仿函数，支持常见的比较运算。它们都是 二元运算，返回值为 bool 类型。

• equal_to<T>：等于
• not_equal_to<T>：不等于
• greater<T>：大于
• greater_equal<T>：大于等于
• less<T>：小于
• less_equal<T>：小于等于

这些仿函数同样继承自 binary_function，提供了参数与返回值型别定义。例如：

template <class T>
struct equal_to : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x == y; }
};

template <class T>
struct greater : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x > y; }
};

使用示例

仿函数对象的用法与一般函数相同，可以使用 具名对象 或 临时对象 调用：

#include <iostream>
#include <functional>
using namespace std;

int main() {
    equal_to<int> equal_to_obj;
    greater<int> greater_obj;

    cout << equal_to_obj(3, 5) << endl;   // 0
    cout << greater_obj(3, 5) << endl;    // 0

    // 临时对象调用
    cout << equal_to<int>()(3, 5) << endl;   // 0
    cout << greater<int>()(3, 5) << endl;    // 0
}

搭配 STL 算法

在实际开发中，这些关系运算仿函数通常与 STL 算法结合使用。例如：

// 按递增顺序排序
sort(iv.begin(), iv.end(), less<int>());

// 按递减顺序排序
sort(iv.begin(), iv.end(), greater<int>());

通过传入不同的关系运算仿函数，可以轻松改变排序或查找等算法的行为。

逻辑运算类 (Logical) 仿函数

STL 内建了三种逻辑运算类仿函数，分别对应逻辑运算中的 And、Or、Not。其中 And 与 Or 为二元运算，Not 为一元运算。

• logical_and<T>：逻辑与
• logical_or<T>：逻辑或
• logical_not<T>：逻辑非

其定义大致如下：

// 逻辑与
template <class T>
struct logical_and : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x && y; }
};

// 逻辑或
template <class T>
struct logical_or : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x || y; }
};

// 逻辑非
template <class T>
struct logical_not : public unary_function<T, bool> {
    bool operator()(const T& x) const { return !x; }
};

这些仿函数对象的用法和普通函数完全相同，可以通过实体对象或临时对象来调用。例如：

#include <iostream>
#include <functional>
using namespace std;

int main() {
    // 定义仿函数对象
    logical_and<int> and_obj;
    logical_or<int>  or_obj;
    logical_not<int> not_obj;

    cout << and_obj(true, true) << endl;   // 1
    cout << or_obj(true, false) << endl;   // 1
    cout << not_obj(true) << endl;         // 0

    // 使用临时对象调用
    cout << logical_and<int>()(true, true) << endl;   // 1
    cout << logical_or<int>()(true, false) << endl;   // 1
    cout << logical_not<int>()(true) << endl;         // 0
}

通常不会在如此简单的逻辑场景中单独使用这些仿函数，它们的主要用途是 搭配 STL 算法，例如在 transform、count_if、remove_if 等算法中作为谓词（predicate）传入，从而实现逻辑运算与条件判断的功能。

证同 (identity)、选择 (select)、投射 (project)

这一类仿函数（identity、select、project）都只是将输入参数原封不动传回，或者有选择性地返回其中一部分。虽然这些操作本身极其简单，但在泛型编程和 STL 内部实现中，为了抽象和间接性，通常会专门定义出这些仿函数。

C++ 标准并没有规定这类仿函数，但在 SGI STL 等实现中，它们常常被用作底层工具。

identity（证同函数）

• 任何数值通过此仿函数后不会有任何改变。
• 常用于 set 的底层 RB-tree，因为 set 的键值就是元素自身，所以 KeyOfValue 选择器直接用 identity。

template <class T>
struct identity : public unary_function<T, T> {
    const T& operator()(const T& x) const { return x; }
};

使用示例：set<int> 内部用 identity<int> 来告诉 RB-tree，键值就是元素本身，不需要另外取子成员。

identity<int> id;
int x = 5;
cout << id(x); // 输出 5

select1st（选择第一元素）

• 接收一个 pair，返回其 first 元素。
• 常用于 map 的底层 RB-tree，因为 map 的键值就是 pair 的第一元素。

template <class Pair>
struct select1st : public unary_function<Pair, typename Pair::first_type> {
    const typename Pair::first_type& operator()(const Pair& x) const {
        return x.first;
    }
};

select2nd（选择第二元素）

• 接收一个 pair，返回其 second 元素。
• SGI STL 并未在内部使用，但在一些场景下可能派上用场。
• 用途：map 容器内部，键是 pair.first，值是 pair.second。用 select1st/select2nd 可以让算法或容器方便地取得 key 或 value，而不用手动写 x.first / x.second。

template <class Pair>
struct select2nd : public unary_function<Pair, typename Pair::second_type> {
    const typename Pair::second_type& operator()(const Pair& x) const {
        return x.second;
    }
};

使用示例：

pair<int, string> p = {1, "hello"};
select1st<pair<int,string>> s1;
select2nd<pair<int,string>> s2;

cout << s1(p); // 输出 1
cout << s2(p); // 输出 "hello"

project1st（投射第一参数）

• 接收两个参数，返回第一个，忽略第二个。

template <class Arg1, class Arg2>
struct project1st : public binary_function<Arg1, Arg2, Arg1> {
    Arg1 operator()(const Arg1& x, const Arg2&) const { return x; }
};

project2nd（投射第二参数）

• 接收两个参数，返回第二个，忽略第一个。
• 用途：有时候算法需要一个二元函数，但我们只想用其中一个参数，比如做排序或筛选时忽略某个值。

template <class Arg1, class Arg2>
struct project2nd : public binary_function<Arg1, Arg2, Arg2> {
    Arg2 operator()(const Arg1&, const Arg2& y) const { return y; }
};

使用示例：

project1st<int,int> p1;
project2nd<int,int> p2;

cout << p1(10, 20); // 输出 10，忽略 20
cout << p2(10, 20); // 输出 20，忽略 10

这些仿函数的意义并不在于“功能强大”，而是提供统一的抽象接口，让底层容器和算法在实现时能通过参数化来选择需要的“取值方式”。这就是泛型编程中所谓的 间接性与抽象化。

这些仿函数的作用本质是 告诉算法或容器应该“取哪部分数据”或者“怎么取数据”，而不是自己去写重复的逻辑。