【速記】C++ STL自定義排序

来源:https://www.cnblogs.com/somebottle/archive/2023/01/22/cpp_stl_custom_compare_tricks.html
-Advertisement-
Play Games

這篇筆記咱日後應該還會進行補充。 關於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_queuemapset這些常見容器都可以自定義比較規則,常用的有以下兩種途徑:

  1. 自定義比較類

  2. 重載運算符

自定義比較類

在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就是後一個元素:

  1. std::less中,lhs < rhs成立的時候返回true,期望程式把lhs放在rhs前面,因此是升序排序。

  2. 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)時調用的是運算符()重載方法來進行比較。

模仿greaterless模板類的定義,我們也可以自己定義比較類:

#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的元素比較規則是略顯“另類”的:

  1. 預設情況下(std::less類),優先隊列中的元素是降序排列的,即大的元素在隊頭,是一個大根堆

  2. 如果使用std::greater類,則優先隊列中的元素是升序排列的,即小的元素在隊頭,是一個小根堆

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

std::greater舉例:

template<class T> struct greater
{
    // 這裡其實是重載了()運算符,因此在使用的時候可以像函數一樣調用
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs > rhs;
    }
};
  • sort函數、mapset容器中,lhs代表序列中前一個元素rhs代表序列中後一個元素

  • 而在priority_queue中,lhs代表新插入的節點rhs代表這個節點的父節點

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

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

重載運算符

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

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

  1. 預設升序排列。

  2. 對於優先隊列來說,出隊元素呈降序排列。

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;
}

總結

  1. 把比較函數的形參(a,b)中的a看作序列中前一個元素b看作序列中後一個元素,方便理解。

  2. 無論是sort函數的比較函數cmp(a,b)還是比較類的重載方法operator()(a,b):

    • 返回true時,不會改變a和b的順序
    • 而返回false時,會改變ab的順序。

    比如在預設情況下,a在序列中的位置小於b時,滿足條件a<b,返回true,不會改變a和b的順序;而當a在序列中的位置大於b時,不滿足條件,會改變a和b的順序。藉此實現升序排列。

  3. 在預設比較函數/比較類的時候,可以活用待比較對象運算符重載方法。具體重載哪個運算符需要根據具體的實現來確定。

    比如容器預設採用比較類std::less,其內部調用待比較對象<運算符。

  4. 優先隊列容器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


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 2023-01-21 一、文件下載 1、實現文件下載步驟 (1)準備文件下載相關步驟 (2)將ResponseEntity<T>對象,作為方法返回值 (3)為ResponseEntity<T>對象,設置三個參數 2、示例代碼 @RequestMapping("/fileDownloadControl ...
  • 開心一刻 有一天,qq收到一個好友申請,驗證消息上寫的是:哥哥加我,我是妹妹 我以為是性騷擾,就沒加,直接回了一句:我喜歡少婦 過了一會兒,姑姑就給我打了個電話:你妹妹qq加你,你怎麼不同意,她想問你幾道數學題,你說你喜歡少婦 我:姑姑,你聽我狡辯一下...... 祝大家除夕快樂! 節點準備 基於  ...
  • JavaScript 中的繼承可以通過多種方式來實現,如原型鏈繼承、借用構造函數繼承、組合繼承、ES6 Class繼承等。 ...
  • 兔年到了,祝大家身體健,康萬事順利。本文內容作為兔年新春紀念頁面,將使用 Three.js 及 其他前端開發知識,創建一個以兔子為主題的 3D 簡單的趣味頁面 Rabbit craft go。本文內容包括使用純代碼創建三維浮島、小河、樹木、兔子、胡蘿蔔以及兔子的運動交互、浮島的動畫效果等。本文包含的... ...
  • JavaScript 中的記憶體管理主要由 JavaScript 引擎負責,開發人員不需要手動管理記憶體。JavaScript 引擎使用垃圾回收演算法來實現自動垃圾回收。 JavaScript 垃圾回收演算法是指在 JavaScript 程式中,用來回收不再使用的記憶體的演算法。 ...
  • 使用 CSS 的 box-sizing 屬性 MDN docs 關於box-sizing 一種解決方法是使用 CSS 的 box-sizing 屬性來控制元素的盒模型。預設情況下,盒模型是 "content-box",這意味著元素的寬度和高度只包括其內容,而不包括 padding 和 border。 ...
  • 最近寫了個 python 的 tkinter 框架入門教程,希望給大家介紹一下這個框架的上手過程,這是一個系列文章,現在是第一篇。 ...
  • 2023-01-22 一、SSM整合 1、Spring + SpringMVC (1)容器管理對象,由DispatcherServlet管理 (2)Spring容器對象,由ContextLoaderListener管理 2、解決組件掃描的衝突問題 (1)SpringMVC只掃描Controller層 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...