C++更改数据类型在排序中的顺序

排序在C++中很常见，例如：sort()函数从小到大排序、set容器中的元素从小到大放置、map容器中的元素按照first元素从小到大放置，priority_queue大顶堆。

那么如果自定义了一个新的数据类型（结构体），如何设定在排序中的顺序？又如何更改基本数据类型在排序中的顺序呢？

自定数据类型

在自定义数据类型（结构体）时，可以通过重载小于号运算符的方法设定两个结构体变量之间的大小关系：

// 例如定义结构体elem，设定其大小关系先遵循属性a大小关系，再遵循属性b大小关系
struct elem {
    int a, b;
    bool operator < (const elem &e) const {  // 判定自身小于e是否为true
        if (a != e.a)
            return a < e.a;
        else
            return b < e.b;
    }
};

在C++中，还有一个pair数据类型，定义在<utility>头文件中，pair<int, int>等价于如下的结构体定义，其大小关系先遵循first大小关系，再遵循second大小关系：

struct elem {
    int first, second;
    bool operator < (const elem &e) const {  // 判定自身小于e是否为true
        if (first != e.first)
            return first < e.first;
        else
            return second < e.second;
    }
};

有了pair，就可以在很多情况下免去定义结构体，重载运算符的繁琐操作。

值得一提的是，map容器中装的就是pair数据类型，从而实现了元素按照first元素从小到大放置，所以源文件包含了<map>头文件，也就包含了<utility>头文件，如果不记得pair是定义在哪个头文件中，可以直接包含<map>头文件即可。

基本数据类型

那么如何更改基本数据类型在排序中的顺序呢？具体来说，就是如何实现基本数据类型从大到小的排序？（以基本数据类型int为例）

更改在容器中的顺序

对于容器来说，需要传入模板类greater<int>，定义在头文件<functional>中：

set<int, greater<int>> st;

map<int, int, greater<int>> mp;

对于priority_queue来说，如果要定义小顶堆，除了传入模板类greater<int>，还需要传入底层容器vector<int>：

priority_queue<int, vector<int>, greater<int>> heap;  // priority_queue基于vector容器和heap处理规则实现

而set，map是基于红黑树实现的，不需要底层容器，所以比priority_queue少了一个参数。

更改在算法中的顺序

对于算法来说，需要传入模板函数greater<int>()，定义在头文件<functional>中；

// 排序范围[it_first, it_last)中的元素

sort(it_first, it_last, greater<int>());

stable_sort(it_first, it_last, greater<int>());  // 稳定排序

排序之后，还常常使用二分查找，如果sort时传入了模板函数，二分查找时同样也要传入：

// 返回范围[it_first, it_last)中首个小于等于value的元素的迭代器，若找不到则返回it_last
lower_bound(it_first, it_last, value, greater<int>());

// 返回范围[it_first, it_last)中首个小于value的元素的迭代器，若找不到则返回it_last
upper_bound(it_first, it_last, value, greater<int>());

总结

对于结构体来说，如果想要排序，则必须重载小于号运算符，此时都是默认的顺序（sort()函数从小到大排序、set容器中的元素从小到大放置、map容器中的元素按照first元素从小到大放置，priority_queue大顶堆），如果需要相反的顺序，可以在此基础上，像基本数据类型一样，再传入模板类greater<int>或模板函数greater<int>()。

---