自定义排序

注意vector数据结构和优先级队列数据结构priority_queue的自定义排序的区别；

注意自定义比较函数和重载操作符的区别

自定义vector排序(基于sort)

如果你想对 vector 进行自定义排序，同样需要提供一个比较函数。可以通过以下几种方式自定义 vector 排序：

使用静态比较函数和 std::sort

定义一个静态的比较函数，并使用 std::sort 来对 vector 排序。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

using namespace std;

// 静态比较函数
static bool myCompare(const pair<int, int>& a, const pair<int, int>& b)
{
    return a.first > b.first; // 在vector中，返回true的话，就说明a的优先级高于b的优先级，a在前，这个是降序排列
}

int main()
{
    vector<pair<int, int>> vec = {{1, 10}, {3, 30}, {2, 20}};

    // 使用 std::sort 和静态比较函数排序
    sort(vec.begin(), vec.end(), myCompare);

    // 输出排序结果
    for (const auto& p : vec)
    {
        cout << p.first << " " << p.second << endl;
    }

    return 0;
}

/* 输出
3 30
2 20
1 10
*/

使用仿函数（函数对象）

你也可以定义一个仿函数（函数对象），然后用它作为排序的比较函数。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

using namespace std;

// 仿函数
struct myCompare
{
    bool operator()(const pair<int, int>& a, const pair<int, int>& b)
    {
        return a.first > b.first;
    }
};

int main()
{
    vector<pair<int, int>> vec = {{1, 10}, {3, 30}, {2, 20}};

    // 使用 std::sort 和仿函数排序
    sort(vec.begin(), vec.end(), myCompare());

    // 输出排序结果
    for (const auto& p : vec)
    {
        cout << p.first << " " << p.second << endl;
    }

    return 0;
}
/* 输出
3 30
2 20
1 10
*/

使用 lambda 表达式

对于临时的排序需求，lambda 表达式是非常方便的选择。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

using namespace std;

int main()
{
    vector<pair<int, int>> vec = {{1, 10}, {3, 30}, {2, 20}};

    // 使用 std::sort 和 lambda 表达式排序
    sort(vec.begin(), vec.end(), [](const pair<int, int>& a, const pair<int, int>& b)
    {
        return a.first > b.first;
    });

    // 输出排序结果
    for (const auto& p : vec)
    {
        cout << p.first << " " << p.second << endl;
    }

    return 0;
}
/* 输出
3 30
2 20
1 10
*/

总结：

  • 静态比较函数适用于重复使用的场景，但需要定义在类外或类内（如果是静态成员函数）。
  • **仿函数（函数对象）**更具灵活性，尤其适合多次使用同一个比较方式的情况下。
  • lambda 表达式适合临时排序需求，代码简洁且易于阅读。

自定义priority_queue的排序

标准库中的 priority_queue 期望第三个模板参数是一个可调用对象，如函数对象（仿函数）、lambda 表达式或函数指针。

使用仿函数（函数对象）

定义一个仿函数类：

1
2
3
4
5
6
7
8
9
struct myCompare
{
    bool operator()(pair<int, int> &a, pair<int, int> &b)
    {
        return a.first > b.first; // 对于priority_queue, 返回true的话表示a的优先级低于b的优先级, b应在前，这是小顶堆！！
    }
};
//然后使用它来定义 priority_queue：
priority_queue<pair<int, int>, vector<pair<int, int>>, myCompare> pq;

使用 lambda 表达式

可以直接使用 lambda 表达式来代替比较函数：

1
2
3
4
5
6
auto cmp = [](pair<int, int> &a, pair<int, int> &b)
{
    return a.first > b.first;
};
// 这样 cmp 就成为了一个可调用对象，符合 priority_queue 的lambda 表达式的要求:
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

函数指针

1
2
3
4
5
6
7
8
static bool myCompare(pair<int, int> &a, pair<int, int> &b)
{
    return a.first > b.first;
}
// 当使用函数指针时，需要通过 std::function 或者直接传递函数指针的方式来指定优先队列的第三个模板参数。
// 使用函数指针
priority_queue<pair<int, int>, vector<pair<int, int>>, bool (*)(pair<int, int>&, pair<int, int>&)> pq(myCompare);

说明

  • priority_queue 的第三个模板参数被指定为 bool (*)(pair<int, int>&, pair<int, int>&)，表示比较函数是一个返回 bool 的函数指针，该函数接受两个 pair<int, int>& 类型的参数。
  • 在构造 priority_queue 时，将静态函数 myCompare 作为参数传递给优先队列。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

static bool myCompare(pair<int, int> &a, pair<int, int> &b)
{
    return a.first > b.first;// 小顶堆
}

int main()
{
    // 使用函数指针作为比较函数
    priority_queue<pair<int, int>, vector<pair<int, int>>, bool (*)(pair<int, int>&, pair<int, int>&)> pq(myCompare);
    
    // 插入一些元素
    pq.push({1, 10});
    pq.push({3, 30});
    pq.push({2, 20});

    // 输出队列的元素
    while (!pq.empty())
    {
        cout << pq.top().first << " " << pq.top().second << endl;
        pq.pop();
    }

    return 0;

}
/* 输出：
1 10
2 20
3 30
*/

为啥vector就可以直接用静态函数，而优先级队列就必须要用结构体

vector 和 priority_queue 排序机制的区别

在 vector 和 priority_queue 的排序机制上，根本的区别在于：

  • std::sort（用于 vector）：可以接受函数指针、仿函数或者lambda 表达式作为第三个参数，因为 std::sort 是一个模板函数，它可以在排序时直接调用这些可调用对象。静态函数可以直接作为函数指针传递给 std::sort。
  • priority_queue：第三个模板参数需要的是一个比较器类型，而这个类型必须具有一个 operator() 操作符（仿函数）来进行比较，而不是直接接受一个函数指针。

区别总结

  1. std::sort 使用函数指针：

    • std::sort 直接调用比较函数，可以是静态函数，因为 std::sort 是一个模板函数，可以直接接受函数指针作为参数。函数指针与 std::sort 的参数类型完全匹配。
    • std::sort 的用法是：sort(vec.begin(), vec.end(), 比较函数);，比较函数可以是函数指针、仿函数或 lambda 表达式。

  2. priority_queue 需要仿函数或类型比较器：

    • priority_queue 设计时需要一个类型来处理比较逻辑，而这个类型需要提供一个 operator()，因此需要一个仿函数（如结构体或类）。
    • 这种设计是因为 priority_queue 作为模板类，它在构造时不直接调用函数，而是依赖模板参数来确定比较器的类型，因此比较器需要是一个带有 operator() 的类型（如仿函数）。而函数指针本质上只是一个函数的地址，并没有这样的操作符重载，因此不能直接作为模板参数类型。

为什么 priority_queue 不能直接使用静态函数？

C++ 标准库中的 priority_queue 需要通过模板参数来定义排序规则，这个模板参数是一个类型（例如仿函数类或 lambda 表达式产生的匿名类型）。比较器类型的定义是通过构造比较器对象来调用其 operator() 操作符进行比较的，而不是直接传递一个函数指针。

因此，priority_queue 要求提供一个能作为类型参数的比较器，而静态函数并不能作为类型使用，只能作为函数指针传递。

注意vector和priority_queue的判断比较逻辑是相反的！

为什么 priority_queue 和 vector 的判断比较逻辑是相反的？

priority_queue 和 vector 使用的排序逻辑不同，是因为它们在底层处理数据的方式以及设计目的不同。它们的比较逻辑看起来是相反的，主要有以下原因：

1. std::priority_queue 的逻辑：

priority_queue 是一种 堆结构，通常默认为 大顶堆。它是基于 二叉堆 实现的，特点是总是将最大（或最小）的元素放在队首，方便快速访问和弹出。

  • 默认情况下，priority_queue 会将比较器看作是判断元素的优先级。
    • 如果使用 < 作为比较逻辑，则意味着较大的元素会被视为优先级较高，放在堆顶，因此构成 大顶堆。
    • 如果使用 > 作为比较逻辑，意味着较小的元素优先级较高，构成 小顶堆。

因此，priority_queue 实际上将较高优先级的元素放在顶部。

2. std::sort（用于 vector）的逻辑：

std::sort 是一种通用的排序算法，按照从小到大（默认行为）或从大到小的顺序对容器元素进行排序。它的比较器直接用来判断两个元素之间的大小关系。

  • 如果比较器使用 <，则 sort 会将较小的元素排在前面，完成升序排序。
  • 如果比较器使用 >，则 sort 会将较大的元素排在前面，完成降序排序。

核心区别：

  • priority_queue：比较器用于确定优先级，较高优先级的元素放在堆顶。因此，< 用于大顶堆，> 用于小顶堆。
  • std::sort：比较器用于确定排序顺序，< 实现升序，> 实现降序。

为什么看起来逻辑相反？

这是因为 priority_queue 的设计是基于优先级的，而 std::sort 是基于顺序的。priority_queue 通过反转比较器的结果来实现堆顶元素的优先级控制，因此它与 std::sort 的直接排序逻辑看起来是相反的。

总结：

  • priority_queue 是优先队列，通过比较器来定义优先级。
  • std::sort 是通用排序，通过比较器来定义排序顺序。

这导致了在实现大顶堆和降序排序时，二者的比较逻辑看起来相反。

并查集与set的用法

使用 1LL 来确保大数运算时不会溢出。

1LL 是 C++ 中用于表示 长整型（long long） 类型的常量。LL 后缀告诉编译器这个常量是 long long 类型。长整型通常用来表示更大的整数，因为 long long 在大多数平台上是 64 位的，能够存储的整数范围远大于 int（通常是 32 位）。

目的
1LL 用于确保参与运算的常量或变量被提升为 long long 类型，从而避免整数溢出问题，特别是在涉及大数运算时。例如：

1
2

long long result = 1LL * a * b;

上面的例子中，1LL 是为了保证乘法 a * b 在计算时不会溢出。若 a 和 b 都是 int 类型，而结果超出了 int 能表示的范围，使用 1LL 将使得整个表达式的计算在 long long 范围内进行，从而避免溢出。

举例

1
2
3
4
5

int a = 100000;
int b = 100000;

long long result = 1LL * a * b; // 使用 1LL 确保乘法在 long long 范围内进行

如果不使用 1LL，a * b 会先在 int 类型的范围内计算，可能导致溢出，然后再转换为 long long，这会导致错误的结果。