拾珠玑 白玉京

【LeetCode-C】仿函数

仿函数

在 C++ 中，operator() 是函数调用运算符的重载，它允许类的对象像函数一样被调用。你提供的代码片段 bool operator()(const int& a, const int& b) const 是一个典型的仿函数（Functor）实现，其核心作用是为类赋予类似函数的调用行为。

基本含义

  • 运算符重载：通过重载 operator()，可以让类的对象以 对象(参数) 的形式调用，例如 myObject(1, 2)，这等价于调用 myObject.operator()(1, 2)。
  • 仿函数（Functor）：这种重载后的对象称为“仿函数”，它结合了函数的调用灵活性和类的封装性。

代码片段解析

bool operator()(const int& a, const int& b) const {
    return a > b;
}
  • 功能：该函数接受两个 int 类型的参数，返回 a > b 的比较结果。它定义了一个降序排序规则。
  • 用途：常用于需要自定义比较逻辑的场景，例如作为 std::sort 的第三个参数。
  • const 修饰符：末尾的 const 表示该函数不会修改类的成员变量（若类有成员变量时）。

应用场景

(1) 自定义排序规则

在 STL 算法中（如 std::sort），可通过仿函数定义排序逻辑：

std::vector<int> vec = {3, 1, 4, 1, 5};
std::sort(vec.begin(), vec.end(), MyComparator());
// 若 MyComparator 中的 operator() 返回 a > b，则 vec 将被降序排序

(2) 作为谓词（Predicate）

在算法中筛选或处理数据：

std::vector<int> data = {5, 3, 8, 2};
auto it = std::find_if(data.begin(), data.end(), IsGreaterThan(4));
// 若 IsGreaterThan 的 operator() 检查元素是否大于阈值

(3) 封装复杂逻辑

仿函数可以保存状态，实现更复杂的逻辑复用：

class Counter {
    int count = 0;
public:
    int operator()() { return ++count; }
};
Counter c;
c(); // 返回 1
c(); // 返回 2（状态被保留）

优势

  • 灵活性：比普通函数更灵活，可携带状态（如计数器、配置参数）。
  • 兼容性：可直接用于 STL 算法和容器，而普通函数指针无法直接保存状态。
  • 性能：编译器通常对仿函数的内联优化更友好。

5对比普通函数

特性仿函数普通函数
状态保存✔️（通过成员变量）❌
内联优化✔️（编译器友好）可能受限
STL 兼容性✔️（可直接传递）需包装为函数指针或 Lambda

总结

你提供的 operator() 重载定义了一个仿函数，用于比较两个整数的大小并返回降序结果。这种设计在需要自定义行为或封装状态的场景中非常有用，尤其适用于 STL 算法和泛型编程。

仿函数 v.s. operator< 重载

在 C++ 中，“仿函数自定义比较函数”与“类中重载 operator<”的选择取决于具体场景需求，两者各有优劣。以下是详细对比与分析：

核心差异

特性仿函数（自定义比较函数）类中重载 operator<
灵活性支持多种比较规则（如升序、降序）仅定义类对象的默认比较逻辑
适用范围可用于任意需要比较的场景（如 STL 算法、容器）仅影响默认排序（如 std::sort 无自定义比较时）
状态保存可携带成员变量保存状态（如计数器、阈值）无法保存状态，仅依赖对象自身属性
代码复用性可复用同一比较逻辑于不同场景仅适用于该类的默认比较逻辑
STL 容器兼容性可作为模板参数传递（如 std::set 的 Compare）仅当容器默认使用 operator< 时生效

适用场景

(1) 推荐使用仿函数的情况

  • 需要多种比较规则
    例如，对同一类对象，有时需按年龄排序，有时按姓名排序。仿函数可通过定义多个不同比较类实现。
  • 需要保存比较状态
    如动态调整比较阈值或记录比较次数（通过成员变量实现）。
  • 兼容 STL 容器模板参数
    std::set、std::map 等容器的排序规则需通过模板参数指定仿函数。

示例：

// 仿函数定义升序和降序两种规则
struct Ascending {
    bool operator()(const Student& a, const Student& b) const {
        return a.score < b.score;
    }
};
struct Descending {
    bool operator()(const Student& a, const Student& b) const {
        return a.score > b.score;
    }
};
std::set<Student, Ascending> set1;  // 按分数升序
std::set<Student, Descending> set2; // 按分数降序

(2) 推荐重载 operator< 的情况

  • 仅需默认排序逻辑
    例如，所有场景均按对象的某个固定属性（如学号）排序。
  • 简化代码
    当无需额外状态或复杂逻辑时，重载 operator< 更简洁直观。

示例：

class Student {
public:
    int id;
    bool operator<(const Student& other) const {
        return id < other.id; // 默认按学号升序
    }
};
std::set<Student> students; // 自动使用 operator<

性能与设计考量

  • 性能
    两者性能接近，仿函数可能因内联优化更高效（编译器对仿函数的内联支持优于虚函数指针）。
  • 可维护性
    仿函数通过分离比较逻辑与类定义，符合“单一职责原则”，更易维护。
  • 扩展性
    仿函数支持组合其他逻辑（如日志记录、条件分支），而 operator< 仅能实现简单比较。

总结

  • 优先选择仿函数：需要灵活比较规则、保存状态或适配 STL 模板参数时。
  • 优先重载 operator<：仅需默认排序且逻辑简单时。

典型场景对比

需求仿函数重载 operator<
同一类多种排序规则✔️❌
优先队列自定义比较逻辑✔️（必须）❌
默认按属性排序❌✔️
比较时需动态调整阈值✔️❌

若需进一步了解具体实现，可参考仿函数在 STL 中的应用 或运算符重载的设计原则。

std::less

std::less 是 C++ 标准库中定义的一个仿函数（Functor） ，用于实现通用的“小于”比较操作。


### **`std::less` 的仿函数特性**
`std::less` 是标准库提供的模板类，定义在 `<functional>` 头文件中：
```cpp
template<typename T>
struct less {
    constexpr bool operator()(const T& lhs, const T& rhs) const {
    return lhs < rhs; // assumes that the implementation handles pointer total order
	}
};
  • 重载了 operator()：允许通过 std::less<T>()(a, b) 调用比较逻辑。
  • 泛型设计：适用于所有支持 < 操作的类型（如 int、std::string、自定义类等）。

std::less 的典型用途

(1) 作为容器的默认比较器

  • std::set、std::map 等有序容器默认使用 std::less<T> 排序：
std::set<int, std::less<int>> s; // 默认升序排序（可省略显式指定）

(2) 泛型算法中的比较逻辑

  • 在 std::sort、std::lower_bound 等算法中提供比较规则：
std::vector<int> vec = {5, 3, 1, 4};
std::sort(vec.begin(), vec.end(), std::less<int>());
// 结果：1, 3, 4, 5（升序）

(3) 支持自定义类型的比较

若自定义类型重载了 < 运算符，可直接用 std::less：

class Student {
public:
    int id;
    bool operator<(const Student& other) const {
        return id < other.id;
    }
};

std::set<Student> students; // 默认使用 std::less<Student>，依赖 operator<

为什么需要 std::less？

  • 统一接口：将比较逻辑封装为对象，便于传递给模板或函数。
  • 灵活扩展：可通过特化 std::less 修改默认行为。例如，对 const char* 按字符串内容比较：
template<>
struct std::less<const char*> {
    bool operator()(const char* a, const char* b) const {
        return strcmp(a, b) < 0;
    }
};

总结

  • std::less 是仿函数：因为它通过 operator() 提供函数调用语义。
  • 核心作用：标准化“小于”比较逻辑，为泛型编程提供统一接口。
  • 扩展性：可通过特化或自定义仿函数实现灵活的比较规则。 好的，我需要帮用户生成关于std::less在priority_queue中生成大根堆的典型用途。用户之前已经讨论过std::less作为仿函数以及它在set和sort中的应用，现在他们可能想了解如何利用它来调整优先队列的行为。

首先，我需要确认priority_queue的默认行为。默认情况下，priority_queue使用std::less作为比较函数，但实际上会生成大根堆还是小根堆呢？这里可能存在误解。根据C++标准，priority_queue默认是最大堆，即顶部元素最大，而比较函数默认是std::less，这看起来有点矛盾。需要解释清楚，因为std::less对应的是元素按升序排列，但在堆结构中，比较函数的逻辑是反的。例如，堆的调整是通过比较父节点和子节点，使用std::less时，父节点需要比子节点大，从而形成大根堆。

接下来，我需要详细说明如何通过std::less来实现大根堆。可能需要指出，虽然std::less在排序算法中是升序，但在priority_queue中的比较逻辑是反向的，因为它是一个最大堆实现。因此，用户可能想确认使用std::less是否真的生成大根堆，或者是否需要使用其他比较函数。例如，使用std::greater会生成小根堆，而默认的std::less生成大根堆。

然后，我需要给出一个代码示例，展示如何用std::less来声明一个最大堆的priority_queue。同时，对比使用std::greater生成最小堆的情况，帮助用户理解两者之间的区别。此外，可能还需要解释为什么默认情况下使用std::less会产生大根堆，这涉及到堆的内部结构和比较函数的关系。

用户可能存在的疑问点在于，为什么比较函数和堆的类型看起来相反。例如，使用std::less作为比较器，但得到的是最大堆。需要解释清楚比较函数在堆中的实际应用方式，即每次插入元素时，比较函数决定元素的排列顺序，而堆的结构维护依赖于这个比较结果。

最后，总结std::less在priority_queue中的作用，并提醒用户注意默认情况下生成的是大根堆，而如果需要小根堆，则需要显式使用std::greater。这可能帮助用户避免常见的误解和错误。

需要确保内容准确，避免误导，同时语言要简洁明了，符合用户之前讨论的详细技术风格。可能需要参考C++标准库文档来确认priority_queue的默认行为，确保给出的信息正确无误。

std::less 的典型用途：priority_queue 大根堆

堆

逻辑结构 堆是一棵完全二叉树，满足以下性质

  • 最大堆：父节点的值 ≥ 子节点的值（根节点为最大值）。
  • 最小堆：父节点的值 ≤ 子节点的值（根节点为最小值）。示例：数组 [90, 45, 60, 20, 10] 可表示为最大堆（根节点90最大）。 物理存储 堆通常用数组实现，通过下标关系维护父子节点
  • 父节点下标：parent(i) = (i-1)/2（向下取整）。
  • 左子节点下标：left_child(i) = 2i + 1。
  • 右子节点下标：right_child(i) = 2i + 2

priority_queue

在 C++ 中，std::priority_queue 默认使用 std::less<T> 作为比较函数，但生成的却是大根堆（最大堆）。这是由于其底层实现逻辑决定的：堆的构建过程中，父节点始终“大于”子节点（通过比较函数判定），而 std::less 的返回值决定了这种父子关系。

(1) 默认行为解析

  • std::priority_queue 声明：

    template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

    默认比较器为 std::less<T>，但会按从大到小顺序排列（堆顶为最大值）。

  • 底层逻辑：
    std::priority_queue 内部维护一个堆，通过 Compare 函数判断是否要交换父子节点。
    当 Compare(a, b) 返回 true 时，表示 a 应该排在 b 之后（即 a < b 时，b 优先）。
    因此，使用 std::less<T> 会确保较大的元素上升到堆顶。

(2) 代码示例

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 默认使用 std::less<int>，生成大根堆
    std::priority_queue<int> pq; // 等价于 std::priority_queue<int, std::vector<int>, std::less<int>>

    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);

    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 输出顺序：4 3 2 1
        pq.pop();
    }
    return 0;
}

(3) 对比小根堆

若要生成小根堆（堆顶为最小值），需显式指定比较器为 std::greater<T>：

#include <functional> // 需要包含此头文件

std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
min_pq.push(4);
min_pq.push(2);

// 输出顺序：1 2 3 4

(4) 设计原理

  • Compare 函数的语义：
    Compare(a, b) 返回 true 表示 a 的优先级低于 b（即 a 应排在 b 后面）。

    • 对于 std::less<T>，当 a < b 时返回 true，说明 b 优先级更高，最终形成大根堆。
    • 对于 std::greater<T>，当 a > b 时返回 true，说明 a 优先级更低，形成小根堆。

  • 内存与性能：
    std::priority_queue 的插入和删除操作时间复杂度为 O(log n)，与比较函数的选择无关。

总结

比较器堆类型堆顶元素适用场景
std::less<T>大根堆最大值默认场景（如求 Top-K 大）
std::greater<T>小根堆最小值需要快速获取最小值时

通过 std::less 和 std::priority_queue 的配合，可以高效实现最大值优先的队列逻辑。

LeetCode-C
Licensed under CC BY-NC-SA 4.0
Last updated on Feb 28, 2025 00:00 UTC
comments powered by Disqus
© 2020 - 2025 飞鸿踏雪泥
Built with Hugo
Theme Stack designed by Jimmy