【速記】C++ STL自定義排序_ZenDei技術網路在線

這篇筆記咱日後應該還會進行補充。關於sort的比較函數 STL的algorithm庫中的sort函數，可以接受一個cmp函數作為第三個參數，用來指定排序的規則。自定義sort比較函數 cmp(a,b)函數的返回值是一個bool值，當返回值為true時不改變元素順序。可以把其中的a看作序列中前一 ...

這篇筆記咱日後應該還會進行補充。

關於sort的比較函數

STL的algorithm庫中的sort函數，可以接受一個cmp函數作為第三個參數，用來指定排序的規則。

自定義sort比較函數

cmp(a,b)函數的返回值是一個bool值，當返回值為true時不改變元素順序。

可以把其中的a看作序列中前一個元素，b看作後一個元素:

如果a < b的時候cmp(a,b)=true，那麼a就會被放在b前面，排序呈升序。
如果a < b的時候cmp(a,b)=false，那麼b就會被放在a前面，排序呈降序。

也就是說cmp(a,b)=true的時候，有a < b成立，期望程式把a放在b前面。

#include <iostream>
#include <algorithm>

using namespace std;

bool ascending(int a, int b) // 升序排序，讓a先於b
{
    // 把a看作序列中前一個元素，b看作後一個元素
    return a < b; // 如果返回true就說明a<b成立，期望程式把a放在b前面
};

bool descending(int a, int b) // 降序排序，讓b先於a
{
    // 把a看作序列中前一個元素，b看作後一個元素
    return b < a; // 如果返回true就說明b<a成立，期望程式把b放在a前面
};

int main()
{
    int test[10] = {9, 4, 2, 5, 1, 7, 3, 6, 8, 10};
    sort(test, test + 10, ascending);
    for (int i = 0; i < 10; i++)
        cout << test[i] << " ";
    // Ouput: 1 2 3 4 5 6 7 8 9 10
    cout << "\n";
    sort(test, test + 10, descending);
    for (int i = 0; i < 10; i++)
        cout << test[i] << " ";
    // Ouput: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

預設sort比較函數

預設情況下，sort函數會使用<運算符作比較。(也就是預設升序排序)

這個時候如果要自定義排序規則，可以重載<運算符。

#include <iostream>
#include <algorithm>

using namespace std;

struct Node
{
    int data;
    bool operator<(const Node &obj)
    {
        return data > obj.data; // a>b的時候返回true, 相當於cmp(b,a)=true, 期望b排在a前面
    }
};

int main()
{
    Node test[10] = {{1}, {4}, {2}, {5}, {9}, {7}, {3}, {6}, {8}, {10}};
    sort(test, test + 10);
    for (int i = 0; i < 10; i++)
        cout << test[i].data << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

自定義容器內元素排序

priority_queue、map、set這些常見容器都可以自定義比較規則，常用的有以下兩種途徑:

自定義比較類
重載運算符

自定義比較類

在cppreference頁面可以看到，這類元素有序的容器都有個預設的Compare比較類。比如priority_queue的聲明:

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

多觀察幾個容器的聲明，能發現預設的Compare比較類都是std::less，定義大概是這樣:

template<class T> struct less
{
    // 這裡其實是重載了()運算符，因此在使用的時候可以像函數一樣調用
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs < rhs;
    }
};

標準庫中還有另一個比較類std::greater，定義如下:

template<class T> struct greater
{
    // 這裡其實是重載了()運算符，因此在使用的時候可以像函數一樣調用
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs > rhs;
    }
};

從數組排序的角度看，lhs就是前一個元素，rhs就是後一個元素:

std::less中，lhs < rhs成立的時候返回true，期望程式把lhs放在rhs前面，因此是升序排序。
std::greater中，lhs > rhs成立的時候才返回true，期望程式把rhs放在lhs前面，因此是降序排序。

很顯然，這裡和sort函數的預設比較函數一樣都是預設升序排序的。

因為重載了運算符()，我實際上可以把【比較類】的對象作為比較函數傳入sort方法:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int test[10] = {4, 1, 3, 7, 5, 8, 2, 9, 6, 10};
    sort(test, test + 10, greater<int>()); // 註意這裡調用的是greater對象的()運算符重載方法
    for (int i = 0; i < 10; i++)
        cout << test[i] << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

值得註意的是，這裡首先調用的是greater類的預設構造方法，返回一個對象並傳遞給sort函數。sort函數內部調用對象(a,b)時調用的是運算符()重載方法來進行比較。

模仿greater和less模板類的定義，我們也可以自己定義比較類:

#include <iostream>
#include <algorithm>

using namespace std;

struct Node
{
    int data;
};

struct MyGreater
{
    // a是序列中前一個元素，b則是後一個元素
    bool operator()(const Node &a, const Node &b) const
    {
        return b.data < a.data; // a<b時返回false，期待程式把b排在a前面
    }
};

int main()
{
    Node test[10] = {{4}, {1}, {3}, {7}, {5}, {8}, {2}, {9}, {6}, {10}};
    sort(test, test + 10, MyGreater());
    for (int i = 0; i < 10; i++)
        cout << test[i].data << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

優先隊列的比較類

在這幾種STL容器中，優先隊列priority_queue的元素比較規則是略顯“另類”的:

預設情況下(std::less類)，優先隊列中的元素是降序排列的，即大的元素在隊頭，是一個大根堆。
如果使用std::greater類，則優先隊列中的元素是升序排列的，即小的元素在隊頭，是一個小根堆。

這裡和之前的排序不同的地方就在於：比較方法形參的意義不同。

拿std::greater舉例:

template<class T> struct greater
{
    // 這裡其實是重載了()運算符，因此在使用的時候可以像函數一樣調用
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs > rhs;
    }
};

在sort函數、map、set容器中，lhs代表序列中前一個元素，rhs代表序列中後一個元素。
而在priority_queue中，lhs代表新插入的節點，rhs代表這個節點的父節點。

lhs>rhs時就是期望父節點小於子節點，即構成小根堆，因此堆頂元素總是堆中最小的，所以從優先隊列中取出的元素也是從小到大的，即升序排列。

往堆中插入新節點時是插入在最後一個葉子節點的位置的。

重載運算符

sort函數中可以預設排序函數。在創建容器對象時，我們也可以預設比較函數。

在預設比較函數的情況下，STL容器預設採用std::less模板類來進行比較：

預設升序排列。
對於優先隊列來說，出隊元素呈降序排列。

std::less類的重載方法中一樣也是調用了對象的<運算符進行比較，因此我們也可以重載<運算符來實現自定義的比較規則。

#include <iostream>
#include <algorithm>

using namespace std;

struct Node
{
    int data;
    // std::less中調用了這裡的<運算符重載方法
    bool operator<(const Node &b) const
    {
        return data > b.data; // a>b時返回true，期待b放在a前面
    }
};

int main()
{
    Node test[10] = {{4}, {1}, {3}, {7}, {5}, {8}, {2}, {9}, {6}, {10}};
    sort(test, test + 10);
    for (int i = 0; i < 10; i++)
        cout << test[i].data << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

總結

把比較函數的形參(a,b)中的a看作序列中前一個元素，b看作序列中後一個元素，方便理解。
無論是sort函數的比較函數cmp(a,b)還是比較類的重載方法operator()(a,b):
- 返回true時，不會改變a和b的順序；
- 而返回false時，會改變a和b的順序。
比如在預設情況下，a在序列中的位置小於b時，滿足條件a<b，返回true，不會改變a和b的順序；而當a在序列中的位置大於b時，不滿足條件，會改變a和b的順序。藉此實現升序排列。
在預設比較函數/比較類的時候，可以活用待比較對象的運算符重載方法。具體重載哪個運算符需要根據具體的實現來確定。

比如容器預設採用比較類std::less，其內部調用待比較對象的<運算符。
優先隊列容器priority_queue的比較元素的含義是不同的，重載方法operator()(a,b)中前一個元素a指的是新插入的元素，而後一個元素b指的是這個元素的父節點。
- 這裡仍然是比較方法返回true時不會改變元素順序。
比如在預設情況下，新插入的元素a的值小於父節點b的值，滿足條件a<b，返回true，不會改變a和b的位置；而當新插入的元素a的值大於父節點b的值，不滿足條件，會改變a和b的位置。藉此維持大根堆的堆序性。

參考文章

https://blog.csdn.net/sandalphon4869/article/details/105419706