c++ 自定义比较器

1.什么是比较器和它的作用

比较器是可以让用户自己重新定义大小比较操作的一种语法，它的主要作用如下

比较器的实质就是重载比较运算符
比较器可以很好的应用在特殊标准的排序上
比较器可以很好的应用在根据特殊标准排序的结构上

2.比较器的应用(java)

在左老师的算法课中，有介绍过比较器在java中的应用，核心思想是，用户自己去定义一个类并去实现接口 Comparator<T>

例如用户自己定义了一个类student，它包含id，姓名，年龄

    // define user's class
    public static class student{
        public String name;
        public int id;
        public int age;

        public student(String name, int id, int age){
            this.name = name;
            this.id = id;
            this.age = age;
        }
    }

接下来把他们放在一个数组里面，直接对他们排序会抛出错误

student s1 = new student("散步", 2, 16);
student s2 = new student("步行", 3, 17);
student s3 = new student("快步", 1, 19);
student s4 = new student("奔跑", 4, 12);

student[] arr = new student[] {s1,s2,s3,s4};
Arrays.sort(arr);

错误如下，提醒我们student不能转换成java可比较的类型，这也是理所当然的，因为我们没有说明到底比较哪一个属性，年龄？还是id？

Exception in thread "main" java.lang.ClassCastException: lecture03_comparator$student cannot be cast to java.lang.Comparable

这时候我们就需要自己实现Comparotor类的借口,在比较的时候把它实例化

public static class studentComp implements Comparator<student>{
    @Override
    public int compare(student s1, student s2){
        return s1.id - s2.id;
    }
}
Arrays.sort(arr, new studentComp());
System.out.println();
for (int i=0; i<arr.length; i++){
    System.out.println(arr[i].id + " , " + arr[i].name + " , " + arr[i].age);
}

输出为：按照id从小到大输出（id的升序，小的放在前面大的放在后面）
1 , 快步 , 19
2 , 散步 , 16
3 , 步行 , 17
4 , 奔跑 , 12
接下来用系统提供的数据结构实现大根堆和小根堆

public static class studentHeapComp implements Comparator<student>{
    @Override
    public int compare(student s1, student s2){
        return s2.id - s1.id;
    }
}

PriorityQueue<student> studentHeap = new PriorityQueue<>(new studentHeapComp());
studentHeap.add(s1);
studentHeap.add(s2);
studentHeap.add(s3);
studentHeap.add(s4);
System.out.println();
while(!studentHeap.isEmpty()){
    student cur = studentHeap.poll();
    System.out.println(cur.id + " , " + cur.name + " , " + cur.age);
}

输出为：大根堆，id大的在上层，小的在下层
4 , 奔跑 , 12
3 , 步行 , 17
2 , 散步 , 16
1 , 快步 , 19

3.比较器的应用（c++）

结合了上面的思想，在c++中也可以用比较器实现方便的特殊规则的比较和特殊结构的比较。比如给定你一个数组，可以通过改变比较器来轻松的实现升序和降序排序。

int numbers[]={20,40,50,10,30};
sort (numbers, numbers+5, std::less<int>());
for (int i=0; i<5; i++)
cout << numbers[i] << ' ';
cout << '\n';

输出：10 20 30 40 50

其中less表示，前面的数比后面的数小为True，也就是说两个数比较小的数放开头(低层次)，大的数放末尾（高层次）；如果想改为升序排序，把比较器改为：

sort (numbers, numbers+5, std::greater<int>());

输出：50 40 30 20 10

如果我们想比较特殊的结构，比如结构体数据，用户自定义结构体student，它有姓名和分数，如果想对它的分数进行降序排序：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

struct Student{
    std::string name;
    int score;
};

std::vector<Student> students;

bool ascendingSort (Student i, Student j){ return (i.score<j.score);}
bool descendingSort (Student i, Student j){ return (i.score>j.score);}

int main(){

    // get students form User input
    Student s1 = {"小二", 90};
    Student s2 = {"小花", 96};
    Student s3 = {"小红", 100};
    Student s4 = {"小紫", 96};

    students.push_back(s1);
    students.push_back(s2);
    students.push_back(s3);
    students.push_back(s4);

    // sort vector according to sortflag
    stable_sort(students.begin(), students.end(), descendingSort);
    for (auto cur : students){
        cout << cur.name << "," << cur.score << endl;
    }

    return 0;
}

输出：
小红,100
小花,96
小紫,96
小二,90