在C++編程領(lǐng)域，定時器是極為關(guān)鍵的基礎(chǔ)組件，它如同一位精準(zhǔn)的時間管家，在諸多場景里發(fā)揮著不可或缺的作用。在網(wǎng)絡(luò)編程中，它能把控連接的超時處理，保障網(wǎng)絡(luò)通信的高效與穩(wěn)定；游戲開發(fā)里，定時刷新畫面、觸發(fā)特定游戲事件等都離不開它；系統(tǒng)運(yùn)維時，可利用定時器定期執(zhí)行日志清理、數(shù)據(jù)備份等任務(wù)。

而在百度 C++ 二面這樣的高水平面試中，“手撕定時器實(shí)現(xiàn)” 這一挑戰(zhàn)，絕非只是簡單的代碼編寫，實(shí)則是對面試者 C++ 知識深度、算法設(shè)計能力、問題分析與解決能力的全面考驗(yàn)。要成功攻克它，需透徹理解定時器原理，精心挑選并設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)，巧妙構(gòu)建高效的任務(wù)調(diào)度與觸發(fā)機(jī)制。接下來，讓我們一步步深入剖析，揭開百度 C++ 二面定時器實(shí)現(xiàn)的神秘面紗，探尋如何在面試中漂亮地完成這一高難度任務(wù)。

Part1.定時器實(shí)現(xiàn)前的知識回顧

1.1C++ 基礎(chǔ)語法

在深入研究定時器實(shí)現(xiàn)之前，讓我們先來回顧一下 C++ 的基礎(chǔ)語法。C++ 作為一種強(qiáng)大的編程語言，具有豐富的特性和靈活的語法結(jié)構(gòu) 。函數(shù)定義是 C++ 編程的基礎(chǔ)，它包含返回類型、函數(shù)名、參數(shù)列表以及函數(shù)體。例如，一個簡單的加法函數(shù)可以這樣定義：

int add(int a, int b) {
    return a + b;
}

這里int是返回類型，表示函數(shù)將返回一個整數(shù)；add是函數(shù)名，方便我們在程序中調(diào)用該函數(shù)；(int a, int b)是參數(shù)列表，定義了函數(shù)接收兩個整數(shù)類型的參數(shù)；函數(shù)體{ return a + b; }則實(shí)現(xiàn)了具體的加法邏輯 。

類是 C++ 面向?qū)ο缶幊痰暮诵母拍睿且环N用戶自定義的數(shù)據(jù)類型，將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)封裝在一起。比如，我們定義一個簡單的Rectangle類來表示矩形：

class Rectangle {
public:
    int width;
    int height;
    int area() {
        return width * height;
    }
};

在這個類中，width和height是類的數(shù)據(jù)成員，用于存儲矩形的寬和高；area是類的成員函數(shù)，用于計算矩形的面積。通過類的實(shí)例化，我們可以創(chuàng)建多個矩形對象，并調(diào)用它們的成員函數(shù)進(jìn)行操作 。

指針與引用也是 C++ 中非常重要的概念。指針是一個變量，它存儲的是另一個變量的內(nèi)存地址，通過指針可以直接訪問和修改內(nèi)存中的數(shù)據(jù) 。例如：

int num = 10;
int *ptr = #

這里ptr是一個指針，它指向num的內(nèi)存地址，通過*ptr可以訪問num的值。引用則是一個變量的別名，它與被引用的變量共享同一內(nèi)存位置 。比如：

int num = 10;
int &ref = num;

ref是num的引用，對ref的操作等同于對num的操作。指針和引用在 C++ 中常用于函數(shù)參數(shù)傳遞、內(nèi)存管理等場景，熟練掌握它們對于理解和編寫高效的 C++ 代碼至關(guān)重要。

1.2時間相關(guān)知識

在 C++ 中，獲取時間有多種方式，其中<chrono>庫是 C++11 引入的一個強(qiáng)大的時間處理庫，它提供了高精度的時間測量和計算功能 。例如，使用std::chrono::high_resolution_clock可以獲取高精度的時間點(diǎn)：

#include <iostream>
#include <chrono>

int main() {
    auto start = std::chrono::high_resolution_clock::now();
    // 執(zhí)行一些操作
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "操作耗時：" << duration << " 毫秒" << std::endl;
    return 0;
}

在上述代碼中，std::chrono::high_resolution_clock::now()獲取當(dāng)前時間點(diǎn)，通過計算兩個時間點(diǎn)的差值，并使用std::chrono::duration_cast進(jìn)行類型轉(zhuǎn)換，得到操作所花費(fèi)的時間，單位為毫秒。

<ctime>庫也是常用的時間處理庫，它提供了與 C 語言兼容的時間函數(shù) 。比如，time函數(shù)可以獲取從 1970 年 1 月 1 日 00:00:00 到當(dāng)前時間的秒數(shù)：

#include <iostream>
#include <ctime>

int main() {
    time_t now = time(nullptr);
    std::cout << "當(dāng)前時間的秒數(shù)：" << now << std::endl;
    return 0;
}

在時間單位換算方面，1 秒等于 1000 毫秒，1 毫秒等于 1000 微秒，1 微秒等于 1000 納秒 。在進(jìn)行時間計算時，需要注意不同時間單位之間的轉(zhuǎn)換，以確保計算結(jié)果的準(zhǔn)確性。例如，如果要將秒數(shù)轉(zhuǎn)換為毫秒數(shù)，只需將秒數(shù)乘以 1000 即可。

1.3數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

實(shí)現(xiàn)定時器可能會用到多種數(shù)據(jù)結(jié)構(gòu)，每種數(shù)據(jù)結(jié)構(gòu)都有其獨(dú)特的特點(diǎn)和適用場景 。鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個節(jié)點(diǎn)的指針 。鏈表的優(yōu)點(diǎn)是插入和刪除操作效率高，時間復(fù)雜度為 O (1)，因?yàn)橹恍栊薷闹羔樀闹赶蚣纯?。例如，在一個簡單的單向鏈表中插入一個新節(jié)點(diǎn)：

struct ListNode {
    int data;
    ListNode *next;
    ListNode(int x) : data(x), next(nullptr) {}
};

void insertNode(ListNode *&head, int value) {
    ListNode *newNode = new ListNode(value);
    newNode->next = head;
    head = newNode;
}

上述代碼定義了一個單向鏈表節(jié)點(diǎn)結(jié)構(gòu)ListNode，并實(shí)現(xiàn)了一個插入節(jié)點(diǎn)的函數(shù)insertNode，該函數(shù)將新節(jié)點(diǎn)插入到鏈表頭部，時間復(fù)雜度為 O (1)。鏈表的缺點(diǎn)是查找操作效率較低，時間復(fù)雜度為 O (n)，因?yàn)樾枰獜念^節(jié)點(diǎn)開始逐個遍歷節(jié)點(diǎn)，直到找到目標(biāo)節(jié)點(diǎn)。

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，它分為最大堆和最小堆 。在最大堆中，每個節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值；在最小堆中，每個節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值 。堆常用于實(shí)現(xiàn)優(yōu)先隊(duì)列，在定時器實(shí)現(xiàn)中，可以利用最小堆來存儲定時器任務(wù)，按照任務(wù)的到期時間從小到大排序 。

堆的插入和刪除操作時間復(fù)雜度為 O (log n)，因?yàn)樾枰S護(hù)堆的性質(zhì)，進(jìn)行堆調(diào)整操作 。例如，使用 C++ 標(biāo)準(zhǔn)庫中的priority_queue（默認(rèn)是最大堆，通過自定義比較函數(shù)可以實(shí)現(xiàn)最小堆）來實(shí)現(xiàn)一個簡單的定時器任務(wù)隊(duì)列：

#include <iostream>
#include <queue>

struct TimerTask {
    int id;
    int expireTime;
    TimerTask(int i, int t) : id(i), expireTime(t) {}
};

struct CompareByExpireTime {
    bool operator()(const TimerTask &a, const TimerTask &b) {
        return a.expireTime > b.expireTime;
    }
};

int main() {
    std::priority_queue<TimerTask, std::vector<TimerTask>, CompareByExpireTime> timerQueue;
    timerQueue.push(TimerTask(1, 5));
    timerQueue.push(TimerTask(2, 3));
    timerQueue.push(TimerTask(3, 7));
    while (!timerQueue.empty()) {
        TimerTask task = timerQueue.top();
        timerQueue.pop();
        std::cout << "任務(wù)ID: " << task.id << ", 到期時間: " << task.expireTime << std::endl;
    }
    return 0;
}

在上述代碼中，定義了一個TimerTask結(jié)構(gòu)體表示定時器任務(wù)，包含任務(wù) ID 和到期時間。通過自定義比較函數(shù)CompareByExpireTime，使priority_queue按照任務(wù)的到期時間從小到大排序，模擬了一個基于最小堆的定時器任務(wù)隊(duì)列。

紅黑樹是一種自平衡的二叉搜索樹，它在插入和刪除操作后能夠自動調(diào)整樹的結(jié)構(gòu)，保持平衡，從而保證查找、插入和刪除操作的時間復(fù)雜度均為 O (log n) 。紅黑樹的每個節(jié)點(diǎn)都帶有顏色屬性，通過顏色規(guī)則來維護(hù)樹的平衡 。在定時器實(shí)現(xiàn)中，紅黑樹可以用于高效地管理定時器任務(wù)，快速查找即將到期的任務(wù) 。例如，在一些高性能的網(wǎng)絡(luò)庫中，常使用紅黑樹來實(shí)現(xiàn)定時器管理器 。雖然紅黑樹的實(shí)現(xiàn)較為復(fù)雜，但它在處理大量數(shù)據(jù)時具有出色的性能表現(xiàn)，能夠滿足定時器對高效性和穩(wěn)定性的要求。

Part2.C++定時器是什么？

2.1定時器概述

C++ 定時器，簡單來說，就是一種能夠讓程序在指定的時間間隔后執(zhí)行特定任務(wù)的機(jī)制 。它就像是一個精準(zhǔn)的時間管家，按照你設(shè)定的時間安排，準(zhǔn)時觸發(fā)相應(yīng)的操作。比如，你可以設(shè)定一個定時器，讓它每隔 1 秒鐘打印一次 “Hello, Timer!”；或者在程序啟動 5 分鐘后，自動執(zhí)行某個數(shù)據(jù)備份的函數(shù)。它為程序賦予了時間驅(qū)動的能力，使得程序能夠更加智能、高效地運(yùn)行。

2.2 C++定時器的工作原理

C++ 定時器的工作原理，其實(shí)并不復(fù)雜。我們可以把它想象成一個獨(dú)立的小助手，在后臺默默為我們服務(wù)。當(dāng)你創(chuàng)建一個定時器時，程序會為它分配一個獨(dú)立的線程。這個線程就像是定時器的專屬 “跑腿”，專門負(fù)責(zé)處理與時間相關(guān)的任務(wù)。

接下來，你需要告訴定時器你希望它等待多長時間，以及在時間到達(dá)后需要執(zhí)行的任務(wù)。定時器會把這些信息記錄下來，然后讓它的 “跑腿” 線程進(jìn)入等待狀態(tài)。在等待的過程中，線程會按照你設(shè)定的時間間隔進(jìn)行休眠，就像人在睡覺一樣，直到設(shè)定的時間到達(dá)。

當(dāng)時間一到，線程就會從休眠中蘇醒過來，然后去執(zhí)行你預(yù)先設(shè)定好的任務(wù)。這個任務(wù)可以是任何你想要的操作，比如調(diào)用一個函數(shù)、執(zhí)行一段代碼塊，甚至是啟動另一個程序。任務(wù)執(zhí)行完畢后，定時器可以根據(jù)你的需求，選擇繼續(xù)等待下一個時間間隔，再次執(zhí)行任務(wù)，或者直接結(jié)束工作。

（1）定時器分類

一般定時任務(wù)的形式表現(xiàn)為：

• 經(jīng)過固定時間后觸發(fā)
• 按照固定頻率周期性觸發(fā)
• 在某個時刻觸發(fā)。

（2）定時器的本質(zhì)

定時器究竟是什么，不妨將其視作這樣一種數(shù)據(jù)結(jié)構(gòu)：

• 存儲一系列的任務(wù)集合，并且deadline越接近的任務(wù)，擁有越高的執(zhí)行優(yōu)先權(quán)
• 一般定時器支持如下幾種操作：add：新增任務(wù)、delete：取消某個任務(wù)、run：執(zhí)行到期的任務(wù)、update：更新到期時間。

那么，該如何判斷一個任務(wù)是否到期呢？

輪詢的方式是每隔一個時間片檢查最近的任務(wù)是否到期。例如，可以創(chuàng)建一個線程每隔 100 毫秒掃描一次到期的任務(wù)。這種方式的缺點(diǎn)是：假設(shè)有 1 萬個 5 秒后到期的定時請求，而掃描周期是 100 毫秒，那么掃描線程在這 5 秒內(nèi)會不斷對這 1 萬個任務(wù)進(jìn)行掃描遍歷，額外掃描 40 多次（每 100 毫秒掃描一次，5 秒內(nèi)要掃描近 50 次），非常浪費(fèi) CPU 資源。

解決方法有：采用 epoll、sleep 之類的喚醒操作；或者使用時間輪。

另一種方式是睡眠 / 喚醒機(jī)制：不斷查找截止時間（deadline）最近的任務(wù)，若已到期就執(zhí)行；否則就睡眠到該任務(wù)到期為止。在睡眠過程中，如果有新任務(wù)被添加或刪除，可能會改變最近的截止時間，這時線程會被喚醒并重新查找最近的截止時間。

2.3定時器與線程

對于服務(wù)端而言，驅(qū)動其邏輯運(yùn)行的事件主要有兩類：一類是網(wǎng)絡(luò)事件，另一類是時間事件。

在不同的框架里，這兩種事件有著不同的實(shí)現(xiàn)方式：

第一種，網(wǎng)絡(luò)事件和時間事件在一個線程中配合使用，比如nginx、redis

// 第一種：
while(!quit){
	int now = get_now_time();  //單位：ms
	int timeout = get_nearset_timer() - now;
	if(timeout < 0){
		timeout = 0;
	}
	int nevent = epoll_wait(epfd, ev, nev, timeout);
	for(int i = 0; i < nevent; i++){
		//.... 網(wǎng)絡(luò)事件處理
	}
	update_timer(); //時間事件處理
}

第二種，網(wǎng)絡(luò)事件和時間事件在不同線程中處理，比如skynet

// 第二種 在其他線程添加定時任務(wù)
void *thread_timer(void *thread_param){
	init_timer();
	while(!quit){
		update_timer();
		sleep(t);
	}
	clear_timer();
	return NULL;
}

pthread_create(&pid, NULL, thread_timer, &thread_param);

需要注意兩點(diǎn)：

• 定時任務(wù)盡量避免執(zhí)行阻塞性操作，不然可能會導(dǎo)致后續(xù)事件無法按時處理。
• 同時，任務(wù)也不能過度占用 CPU，否則會使應(yīng)用程序的性能下降。

2.4定時器的數(shù)據(jù)結(jié)構(gòu)該如何選擇？

需要一種有序的數(shù)據(jù)結(jié)構(gòu)，要求在進(jìn)行增刪操作時能保持其有序性，并且能夠快速查找其中的最小節(jié)點(diǎn)。為滿足對任務(wù)到期判斷及相關(guān)操作的需求，有如下數(shù)據(jù)結(jié)構(gòu)可供選擇：

• 有序鏈表：在邏輯上，元素按順序排列，節(jié)點(diǎn)通過指針連接。其增刪操作相對靈活，只需調(diào)整指針，無需移動大量元素。但在查找特定元素時，需從頭節(jié)點(diǎn)開始順序遍歷，時間復(fù)雜度較高。
• 紅黑樹：一種自平衡二叉查找樹，節(jié)點(diǎn)帶有紅或黑的顏色屬性。其增刪查操作的時間復(fù)雜度均為 O (log?n) 。在紅黑樹中，最左側(cè)節(jié)點(diǎn)即為最小節(jié)點(diǎn)，查找該節(jié)點(diǎn)的時間復(fù)雜度同樣為 O (log?n) 。它能在插入和刪除節(jié)點(diǎn)時通過特定操作維持平衡，以確保良好的查找性能。
• 最小堆：是一種特殊的完全二叉樹結(jié)構(gòu)，父節(jié)點(diǎn)的值小于或等于子節(jié)點(diǎn)的值，根節(jié)點(diǎn)是堆中的最小值。插入和查找操作的時間復(fù)雜度為 O (log?n) ，刪除操作時間復(fù)雜度通常為 O (n) ，不過借助輔助數(shù)據(jù)結(jié)構(gòu)（如 map 或 hashmap）可加快刪除速度。對于最小堆，獲取根節(jié)點(diǎn)（即最小節(jié)點(diǎn)）的時間復(fù)雜度為 O (1) 。
• 跳表：本質(zhì)是有序鏈表的改進(jìn)，通過引入多層索引結(jié)構(gòu)來提升查找效率。其增刪查操作的時間復(fù)雜度平均為O (log?n) 最左側(cè)節(jié)點(diǎn)為最小節(jié)點(diǎn)，查找該節(jié)點(diǎn)的時間復(fù)雜度為O (1) 。但跳表的空間復(fù)雜度較高，為O (1.5n) 。
• 時間輪：對于像 Linux 這類對定時器依賴程度高（如網(wǎng)絡(luò)子模塊的 TCP 協(xié)議大量使用定時器）的操作系統(tǒng)，上述數(shù)據(jù)結(jié)構(gòu)無法滿足需求。Linux 采用了更為高效的定時器算法 —— 時間輪（timewheel）。時間輪在進(jìn)行增刪查操作以及查找最小節(jié)點(diǎn)時，時間復(fù)雜度均為 O (1) ，能更高效地處理大量定時任務(wù)。

關(guān)于如何選擇定時器實(shí)現(xiàn)方式，可以根據(jù)任務(wù)量大小來決定：

• 在任務(wù)量較小的場景下，采用最小堆實(shí)現(xiàn)更為合適。它可以根據(jù)堆頂元素設(shè)置超時時間，采用數(shù)組存儲結(jié)構(gòu)，內(nèi)存消耗更少，能取得較好的效果。而時間輪定時器由于需要維護(hù)專門的線程來驅(qū)動指針轉(zhuǎn)動，還要開辟 bucket 數(shù)組，內(nèi)存消耗較大，在此場景下使用會造成資源浪費(fèi)。
• 在任務(wù)量較大的場景中，最小堆的插入操作復(fù)雜度為 O (lgN)，相比時間輪的 O (1) 會導(dǎo)致性能下降，因此更適合使用時間輪實(shí)現(xiàn)。
• 在業(yè)界實(shí)踐中，像服務(wù)治理中的心跳檢測等功能需要維護(hù)大量的連接心跳，這類場景下時間輪通常是首選方案。

Part3.C++定時器實(shí)現(xiàn)方式

3.1基于std::thread的定時器實(shí)現(xiàn)

基于 std::thread 實(shí)現(xiàn)定時器的原理較為直觀，通過創(chuàng)建一個新線程，讓該線程在設(shè)定的時間間隔內(nèi)休眠，當(dāng)休眠時間結(jié)束后，執(zhí)行預(yù)先設(shè)定的任務(wù) 。

下面通過一個簡單的代碼示例來展示其實(shí)現(xiàn)方式：

#include <iostream>
#include <thread>
#include <chrono>
#include <atomic>
#include <functional>

class CustomTimer {
public:
    CustomTimer() : is_running(false) {}

    void start(std::chrono::milliseconds total_duration, 
               std::chrono::milliseconds interval, 
               std::function<void()> task) {
        stop(); // 確保之前的計時器停止
        is_running = true;
        timer_thread = std::thread([=]() {
            auto start_time = std::chrono::steady_clock::now();
            auto end_time = start_time + total_duration;
            auto next_check = start_time;
            while (is_running.load() && std::chrono::steady_clock::now() < end_time) {
                std::this_thread::sleep_until(next_check);
                next_check += interval;
                if (is_running.load()) {
                    task();
                }
            }
            is_running = false; // 確保在結(jié)束時將is_running設(shè)置為false
        });
    }

    void stop() {
        is_running = false;
        if (timer_thread.joinable()) {
            timer_thread.join();
        }
    }

    ~CustomTimer() {
        stop();
    }

private:
    std::atomic<bool> is_running;
    std::thread timer_thread;
};

int main() {
    CustomTimer timer;
    // 設(shè)置一個2秒總時長，每200毫秒執(zhí)行一次任務(wù)
    timer.start(std::chrono::milliseconds(2000), 
                std::chrono::milliseconds(200), 
                []() {
                    std::cout << "執(zhí)行任務(wù)" << std::endl;
                });
    // 主線程繼續(xù)運(yùn)行，可以在這里添加其他邏輯
    std::this_thread::sleep_for(std::chrono::seconds(2));
    timer.stop();
    return 0;
}

在這段代碼中，CustomTimer類封裝了定時器的功能。start函數(shù)接受總時長total_duration、時間間隔interval以及要執(zhí)行的任務(wù)task作為參數(shù)。在start函數(shù)內(nèi)部，首先創(chuàng)建一個新線程timer_thread，線程的執(zhí)行體是一個 Lambda 表達(dá)式。在這個表達(dá)式中，記錄了開始時間start_time和結(jié)束時間end_time，通過一個循環(huán)不斷檢查當(dāng)前時間是否超過結(jié)束時間，并且is_running標(biāo)志為真。在每次循環(huán)中，線程通過std::this_thread::sleep_until休眠到下一個檢查時間next_check，當(dāng)時間到達(dá)時，執(zhí)行任務(wù)task。stop函數(shù)用于停止定時器，它將is_running標(biāo)志設(shè)為假，并等待線程結(jié)束。

這種實(shí)現(xiàn)方式適用于需要在指定時間內(nèi)定期執(zhí)行某些操作，并且在時間結(jié)束后自動停止的場景 。它的優(yōu)點(diǎn)很明顯，首先是簡單易懂，使用線程是最基本的并行處理方式，對于初學(xué)者來說，易于理解和實(shí)現(xiàn)。其次，靈活性高，可以在任何時間創(chuàng)建線程，并且能夠精確控制定時器的生命周期，方便管理。

然而，它也存在一些缺點(diǎn)。由于每個std::thread都可能占用相當(dāng)多的系統(tǒng)資源，尤其是在創(chuàng)建大量線程時，資源消耗問題會變得比較嚴(yán)重。在涉及多線程時，開發(fā)者需要處理線程的同步和并發(fā)問題，這可能會導(dǎo)致程序復(fù)雜度增加。相比于更高級的并發(fā)管理庫，如std::async或線程池，std::thread提供的控制能力較為基本，缺乏一些高級的特性。

3.2利用 std::async 和 std::future實(shí)現(xiàn)定時器

std::async和std::future是 C++11 引入的高級并發(fā)工具，它們?yōu)楫惒饺蝿?wù)的管理提供了一種更加簡潔和高效的方式 。std::async用于啟動一個異步任務(wù)，它會返回一個std::future對象，通過這個對象可以獲取異步任務(wù)的結(jié)果，或者查詢?nèi)蝿?wù)的狀態(tài)。std::future提供了諸如get（等待任務(wù)完成并獲取結(jié)果）、wait（等待任務(wù)完成）、wait_for（等待一段時間，如果任務(wù)在這段時間內(nèi)完成則返回）等方法，方便對異步任務(wù)進(jìn)行控制。下面是使用std::async和std::future實(shí)現(xiàn)定時器的代碼示例：

#include <iostream>
#include <chrono>
#include <thread>
#include <future>
#include <atomic>
#include <functional>

class CustomTimer {
public:
    CustomTimer() : is_running(false) {}

    void start(std::chrono::milliseconds total_duration, 
               std::chrono::milliseconds interval, 
               std::function<void()> task) {
        stop();
        is_running = true;
        auto start_time = std::chrono::steady_clock::now();
        auto end_time = start_time + total_duration;
        auto next_check = start_time;

        std::future<void> future_task = std::async(std::launch::async, [this, interval, task, start_time, end_time, next_check]() mutable {
            while (is_running.load() && std::chrono::steady_clock::now() < end_time) {
                std::this_thread::sleep_until(next_check);
                next_check += interval;
                if (is_running.load()) {
                    task();
                }
            }
            is_running = false;
        });
    }

    void stop() {
        is_running = false;
    }

private:
    std::atomic<bool> is_running;
};

int main() {
    CustomTimer timer;
    timer.start(std::chrono::milliseconds(2000), 
                std::chrono::milliseconds(200), 
                []() {
                    std::cout << "執(zhí)行任務(wù)" << std::endl;
                });
    std::this_thread::sleep_for(std::chrono::seconds(2));
    timer.stop();
    return 0;
}

在這個示例中，CustomTimer類的start函數(shù)使用std::async啟動一個異步任務(wù)，任務(wù)的執(zhí)行體同樣是一個 Lambda 表達(dá)式。在這個表達(dá)式中，實(shí)現(xiàn)了與基于std::thread實(shí)現(xiàn)類似的定時邏輯，通過休眠和檢查時間來定期執(zhí)行任務(wù)。std::future<void>對象future_task用于獲取異步任務(wù)的結(jié)果，但在這個定時器實(shí)現(xiàn)中，我們并不需要獲取具體的結(jié)果，只是利用std::async來管理異步任務(wù)的生命周期。

與std::thread相比，使用std::async和std::future實(shí)現(xiàn)的定時器，最大的優(yōu)勢在于可以自動管理線程的生命周期，開發(fā)者不需要顯式地創(chuàng)建和管理線程，這使得代碼更加簡潔且易于維護(hù) 。這種實(shí)現(xiàn)方式適用于希望簡化線程管理、減少顯式線程控制代碼的場景。例如，在一些對代碼簡潔性要求較高，且不需要對線程進(jìn)行精細(xì)控制的應(yīng)用中，使用std::async和std::future實(shí)現(xiàn)定時器是一個不錯的選擇。它還適用于需要處理異步任務(wù)結(jié)果的場景，因?yàn)閟td::future提供了方便的方法來獲取任務(wù)的執(zhí)行結(jié)果。然而，由于其內(nèi)部實(shí)現(xiàn)機(jī)制相對復(fù)雜，可能在一些對性能要求極高，且資源有限的場景下，不如基于std::thread的簡單實(shí)現(xiàn)高效。

3.3基于時間輪算法的定時器實(shí)現(xiàn)

時間輪算法是一種高效的定時器實(shí)現(xiàn)方式，它的工作原理類似于鐘表的表盤 。想象一個環(huán)形的表盤，被分成了多個格子，每個格子代表一個固定的時間間隔，我們稱之為一個 “時間槽”。表盤上有一個指針，會按照固定的時間間隔移動，每移動一次，就檢查當(dāng)前指針?biāo)赶虻臅r間槽中是否有任務(wù)需要執(zhí)行。當(dāng)需要添加一個定時任務(wù)時，根據(jù)任務(wù)的到期時間，計算出它應(yīng)該被放置在哪個時間槽中。如果任務(wù)的到期時間超過了當(dāng)前時間輪的范圍，可能會使用多層時間輪來處理，類似于鐘表中時針、分針和秒針的協(xié)作。

為了更直觀地理解，我們來看一個簡單的示意圖：

圖片

在這個圖中，時間輪被分成了 8 個時間槽，每個時間槽的時間間隔為 1 秒。假設(shè)當(dāng)前指針指向時間槽 0，當(dāng)有一個任務(wù)需要在 3 秒后執(zhí)行時，它會被放置在時間槽 3 中。當(dāng)指針移動到時間槽 3 時，就會執(zhí)行該任務(wù)。如果有一個任務(wù)需要在 10 秒后執(zhí)行，由于超過了當(dāng)前時間輪的 8 秒范圍，可能會被放置到上層時間輪的某個槽中，上層時間輪的每個槽可能代表 8 秒的時間間隔。

下面是一個簡化的時間輪定時器的代碼實(shí)現(xiàn)示例：

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <chrono>
#include <thread>
#include <mutex>
#include <condition_variable>

class TimeWheel {
public:
    TimeWheel(int tick_duration, int wheel_size)
        : tick_duration_(tick_duration), wheel_size_(wheel_size), current_slot_(0) {
        slots_.resize(wheel_size_);
    }

    void add_task(std::function<void()> task, int delay) {
        int slot = (current_slot_ + (delay / tick_duration_)) % wheel_size_;
        std::unique_lock<std::mutex> lock(mutex_);
        slots_[slot].push(task);
        lock.unlock();
        cv_.notify_one();
    }

    void run() {
        std::thread([this]() {
            while (true) {
                std::this_thread::sleep_for(std::chrono::milliseconds(tick_duration_));
                std::unique_lock<std::mutex> lock(mutex_);
                cv_.wait(lock, [this]() { return!slots_[current_slot_].empty(); });
                while (!slots_[current_slot_].empty()) {
                    auto task = slots_[current_slot_].front();
                    slots_[current_slot_].pop();
                    lock.unlock();
                    task();
                    lock.lock();
                }
                current_slot_ = (current_slot_ + 1) % wheel_size_;
            }
        }).detach();
    }

private:
    int tick_duration_;
    int wheel_size_;
    int current_slot_;
    std::vector<std::queue<std::function<void()>>> slots_;
    std::mutex mutex_;
    std::condition_variable cv_;
};

int main() {
    TimeWheel wheel(1000, 10); // 每1秒一個時間槽，共10個時間槽
    wheel.run();

    wheel.add_task([]() { std::cout << "任務(wù)執(zhí)行" << std::endl; }, 3); // 3秒后執(zhí)行任務(wù)

    std::this_thread::sleep_for(std::chrono::seconds(5));
    return 0;
}

在這段代碼中，TimeWheel類實(shí)現(xiàn)了時間輪定時器的基本功能。構(gòu)造函數(shù)接受時間槽的時間間隔tick_duration和時間輪的大小wheel_size作為參數(shù)。add_task函數(shù)用于添加任務(wù)，它根據(jù)任務(wù)的延遲時間計算出應(yīng)該放置的時間槽，并將任務(wù)加入到對應(yīng)的時間槽隊(duì)列中。run函數(shù)啟動一個線程，該線程會每隔tick_duration時間檢查當(dāng)前時間槽中是否有任務(wù)，若有則執(zhí)行任務(wù)，然后將指針移動到下一個時間槽。

為了優(yōu)化性能，可以采用一些策略。例如，在處理大量任務(wù)時，可以使用哈希表來快速定位任務(wù)所在的時間槽，減少查找時間。對于多層時間輪的實(shí)現(xiàn)，可以合理分配各層時間輪的時間間隔和大小，以提高任務(wù)調(diào)度的效率。還可以考慮使用線程池來執(zhí)行任務(wù)，避免頻繁創(chuàng)建和銷毀線程帶來的開銷 。

Part4.C++定時器的應(yīng)用場景實(shí)戰(zhàn)

4.1心跳檢測機(jī)制中的應(yīng)用

在分布式系統(tǒng)或網(wǎng)絡(luò)通信中，心跳檢測是一種常用的機(jī)制，用于監(jiān)控遠(yuǎn)程節(jié)點(diǎn)或連接的存活狀態(tài) 。其原理類似于我們?nèi)粘ｓw檢時檢查心跳，通過定期發(fā)送心跳消息來確認(rèn)對方是否正常工作。如果在一定時間內(nèi)沒有收到對方的心跳響應(yīng)，就可以認(rèn)為連接出現(xiàn)問題或者對方節(jié)點(diǎn)已失效。

在 C++ 中實(shí)現(xiàn)心跳檢測機(jī)制，定時器扮演著關(guān)鍵的角色。我們可以使用定時器來控制心跳消息的發(fā)送頻率，比如每隔 5 秒鐘發(fā)送一次心跳包。當(dāng)接收到對方的心跳響應(yīng)時，重置定時器；如果定時器超時仍未收到響應(yīng)，則觸發(fā)相應(yīng)的處理邏輯，如重新建立連接或提示用戶連接異常。

下面是一個使用boost::asio庫實(shí)現(xiàn)的簡單心跳檢測示例代碼，展示了定時器在其中的應(yīng)用：

#include <boost/asio.hpp>
#include <iostream>

class HeartbeatClient {
public:
    HeartbeatClient(boost::asio::io_service& io_service,
                    boost::asio::ip::tcp::endpoint endpoint)
        : socket_(io_service), resolver_(io_service), timer_(io_service), next_heartbeat_(5) {
        // 異步解析服務(wù)器地址
        resolver_.async_resolve(endpoint,
                                [this](const boost::system::error_code& ec,
                                       boost::asio::ip::tcp::resolver::iterator it) {
                                    if (!ec) {
                                        // 異步連接到服務(wù)器
                                        boost::asio::async_connect(socket_, it,
                                                                   [this](const boost::system::error_code& ec) {
                                                                       if (!ec) {
                                                                           start_heartbeat();
                                                                       } else {
                                                                           std::cerr << "Connect failed: " << ec.message() << std::endl;
                                                                       }
                                                                   });
                                    } else {
                                        std::cerr << "Resolve failed: " << ec.message() << std::endl;
                                    }
                                });
    }

private:
    void start_heartbeat() {
        // 設(shè)置下一次心跳的時間
        auto deadline = std::chrono::high_resolution_clock::now() + std::chrono::seconds(next_heartbeat_);
        timer_.expires_at(deadline);
        // 異步等待定時器超時
        timer_.async_wait([this](const boost::system::error_code& ec) {
            if (!ec) {
                send_heartbeat();
                start_heartbeat();
            } else if (ec != boost::asio::error::operation_aborted) {
                std::cerr << "Heartbeat timer error: " << ec.message() << std::endl;
            }
        });
    }

    void send_heartbeat() {
        boost::asio::post(socket_.get_executor(), [this]() {
            boost::asio::streambuf request;
            std::ostream request_stream(&request);
            request_stream << "HEARTBEAT\n";
            // 異步發(fā)送心跳消息
            boost::asio::async_write(socket_, request,
                                     [this](const boost::system::error_code& ec, size_t /*length*/) {
                                         if (ec) {
                                             std::cerr << "Send heartbeat failed: " << ec.message() << std::endl;
                                         }
                                     });
        });
    }

    boost::asio::ip::tcp::socket socket_;
    boost::asio::ip::tcp::resolver resolver_;
    boost::asio::steady_timer timer_;
    int next_heartbeat_;
};

int main() {
    try {
        boost::asio::io_service io_service;
        boost::asio::ip::tcp::endpoint endpoint(boost::asio::ip::address::from_string("127.0.0.1"), 12345);
        HeartbeatClient client(io_service, endpoint);
        io_service.run();
    } catch (std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

在這段代碼中，HeartbeatClient類負(fù)責(zé)管理心跳檢測的邏輯。構(gòu)造函數(shù)中，通過resolver_異步解析服務(wù)器地址，并異步連接到服務(wù)器。start_heartbeat函數(shù)使用timer_定時器來控制心跳消息的發(fā)送頻率，每隔next_heartbeat_秒發(fā)送一次心跳消息。send_heartbeat函數(shù)負(fù)責(zé)將心跳消息異步發(fā)送到服務(wù)器。當(dāng)定時器超時時，會調(diào)用async_wait的回調(diào)函數(shù)，在回調(diào)函數(shù)中先發(fā)送心跳消息，然后再次啟動定時器，實(shí)現(xiàn)循環(huán)心跳檢測。如果在發(fā)送心跳消息或處理定時器事件時出現(xiàn)錯誤，會在控制臺輸出相應(yīng)的錯誤信息。

4.2游戲開發(fā)中的技能冷卻系統(tǒng)

在游戲開發(fā)中，技能冷卻系統(tǒng)是一個非常重要的功能，它能夠增加游戲的策略性和挑戰(zhàn)性 。其主要需求是控制玩家使用技能的頻率，每個技能在使用后需要經(jīng)過一定的冷卻時間才能再次使用。同時，需要在游戲界面上直觀地顯示技能的冷卻狀態(tài)，讓玩家清楚地知道技能何時可以再次釋放。

基于定時器的技能冷卻系統(tǒng)設(shè)計方案如下：為每個技能創(chuàng)建一個對應(yīng)的定時器，當(dāng)技能被使用時，啟動定時器并設(shè)置冷卻時間。在定時器運(yùn)行期間，技能處于冷卻狀態(tài)，無法再次使用。當(dāng)定時器超時，技能冷卻完成，玩家可以再次使用該技能。為了在界面上顯示技能的冷卻狀態(tài)，可以通過更新技能圖標(biāo)的顏色、透明度或添加倒計時數(shù)字等方式來實(shí)現(xiàn)。

下面是一個簡單的技能冷卻系統(tǒng)的實(shí)現(xiàn)代碼，使用SFML庫來處理圖形界面：

#include <SFML/Graphics.hpp>
#include <iostream>
#include <chrono>
#include <thread>

class Skill {
public:
    Skill(const std::string& name, float cooldown)
        : name_(name), cooldown_(cooldown), remaining_cooldown_(0), is_available_(true) {}

    void use() {
        if (is_available_) {
            std::cout << "Using skill: " << name_ << std::endl;
            remaining_cooldown_ = cooldown_;
            is_available_ = false;
            start_cooldown();
        } else {
            std::cout << "Skill " << name_ << " is on cooldown. Remaining time: " << remaining_cooldown_ << "s" << std::endl;
        }
    }

    void update(float delta_time) {
        if (!is_available_) {
            remaining_cooldown_ -= delta_time;
            if (remaining_cooldown_ <= 0) {
                remaining_cooldown_ = 0;
                is_available_ = true;
            }
        }
    }

    bool is_available() const {
        return is_available_;
    }

private:
    void start_cooldown() {
        std::thread([this]() {
            auto start_time = std::chrono::high_resolution_clock::now();
            auto end_time = start_time + std::chrono::duration<float>(cooldown_);
            while (std::chrono::high_resolution_clock::now() < end_time) {
                std::this_thread::sleep_for(std::chrono::milliseconds(100));
            }
            is_available_ = true;
        }).detach();
    }

    std::string name_;
    float cooldown_;
    float remaining_cooldown_;
    bool is_available_;
};

int main() {
    sf::RenderWindow window(sf::VideoMode(800, 600), "Skill Cooldown Example");
    window.setFramerateLimit(60);

    Skill fireball("Fireball", 3.0f);

    sf::Font font;
    if (!font.loadFromFile("arial.ttf")) {
        std::cerr << "Failed to load font" << std::endl;
        return 1;
    }

    sf::Text skill_text;
    skill_text.setFont(font);
    skill_text.setString("Fireball");
    skill_text.setCharacterSize(30);
    skill_text.setFillColor(sf::Color::White);
    skill_text.setPosition(350, 250);

    sf::Text cooldown_text;
    cooldown_text.setFont(font);
    cooldown_text.setCharacterSize(30);
    cooldown_text.setFillColor(sf::Color::Red);
    cooldown_text.setPosition(350, 300);

    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed)
                window.close();
            if (event.type == sf::Event::KeyPressed && event.key.code == sf::Keyboard::Space) {
                fireball.use();
            }
        }

        float delta_time = 1.0f / 60.0f;
        fireball.update(delta_time);

        window.clear(sf::Color::Black);

        window.draw(skill_text);
        if (!fireball.is_available()) {
            cooldown_text.setString("Cooldown: " + std::to_string(fireball.remaining_cooldown_));
            window.draw(cooldown_text);
        }

        window.display();
    }

    return 0;
}

在這個示例中，Skill類表示一個游戲技能，包含技能名稱、冷卻時間、剩余冷卻時間和可用性等屬性。use方法用于使用技能，如果技能可用，則啟動冷卻定時器，并將技能標(biāo)記為不可用；如果技能正在冷卻中，則提示玩家剩余冷卻時間。update方法在每一幀被調(diào)用，用于更新技能的剩余冷卻時間。start_cooldown方法使用線程和定時器來實(shí)現(xiàn)技能的冷卻邏輯。

在main函數(shù)中，創(chuàng)建了一個Skill對象fireball，并使用SFML庫創(chuàng)建了一個簡單的圖形界面。當(dāng)玩家按下空格鍵時，嘗試使用fireball技能。在游戲循環(huán)中，不斷更新技能的冷卻狀態(tài)，并在界面上顯示技能名稱和剩余冷卻時間。如果技能處于冷卻狀態(tài)，會在技能名稱下方顯示剩余冷卻時間；如果技能可用，則不顯示冷卻時間。運(yùn)行這個程序，你可以直觀地看到技能冷卻系統(tǒng)的效果，體驗(yàn)定時器在游戲開發(fā)中的實(shí)際應(yīng)用 。

Part5.手撕定時器演練

5.1定時器的功能需求分析

在深入探討定時器的實(shí)現(xiàn)方案之前，我們先來明確一下定時器應(yīng)具備的核心功能 。首先，設(shè)置定時時間是定時器最基本的功能之一，用戶需要能夠根據(jù)實(shí)際需求靈活設(shè)定任務(wù)的執(zhí)行時間 。比如，在一個網(wǎng)絡(luò)爬蟲程序中，可能需要每隔一段時間就去訪問特定的網(wǎng)站獲取最新信息，這個間隔時間就需要通過定時器的設(shè)置定時時間功能來確定。

執(zhí)行回調(diào)函數(shù)也是定時器的關(guān)鍵功能。當(dāng)設(shè)定的時間到達(dá)時，定時器要能夠自動觸發(fā)并執(zhí)行預(yù)先定義好的回調(diào)函數(shù)，完成特定的任務(wù) 。例如，在一個定時備份系統(tǒng)中，回調(diào)函數(shù)可以實(shí)現(xiàn)將重要數(shù)據(jù)備份到指定存儲位置的操作。支持多個定時器同時工作也是必不可少的。在實(shí)際應(yīng)用中，往往會有多個不同的任務(wù)需要在不同的時間點(diǎn)執(zhí)行 。以一個電商系統(tǒng)為例，可能同時存在定時更新商品庫存信息、定時發(fā)送促銷郵件、定時清理過期訂單等多個定時任務(wù)，這就要求定時器能夠管理多個定時器實(shí)例，確保每個任務(wù)都能按時執(zhí)行。

此外，能夠取消定時器也是一項(xiàng)重要功能。當(dāng)某個定時任務(wù)不再需要執(zhí)行時，用戶應(yīng)該可以隨時取消對應(yīng)的定時器 。比如，在一個視頻會議系統(tǒng)中，如果用戶臨時取消了預(yù)約的會議，那么相應(yīng)的定時提醒任務(wù)就需要被取消，避免不必要的通知干擾。

5.2線程安全問題

（1）問題產(chǎn)生原因：在多線程環(huán)境下，定時器可能會面臨線程安全問題。當(dāng)多個線程同時訪問和操作定時器相關(guān)的資源時，就容易出現(xiàn)數(shù)據(jù)競爭和不一致的情況。例如，一個線程正在修改定時器的時間間隔，而另一個線程同時嘗試讀取這個時間間隔，就可能導(dǎo)致讀取到的數(shù)據(jù)不準(zhǔn)確。這是因?yàn)榫€程的調(diào)度是由操作系統(tǒng)決定的，具有不確定性，多個線程對共享資源的并發(fā)訪問可能會破壞數(shù)據(jù)的完整性 。

（2）解決方案探討：為了解決線程安全問題，我們可以使用互斥鎖（mutex）來保護(hù)共享資源。互斥鎖就像是一把鎖，當(dāng)一個線程獲取到這把鎖時，其他線程就無法訪問被鎖保護(hù)的資源，直到該線程釋放鎖。在 C++ 中，我們可以使用std::mutex來實(shí)現(xiàn)互斥鎖。比如：

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

std::mutex timer_mutex;
int timer_interval = 1000; // 定時器時間間隔，單位毫秒

void update_timer_interval(int new_interval) {
    std::lock_guard<std::mutex> lock(timer_mutex);
    timer_interval = new_interval;
}

void read_timer_interval() {
    std::lock_guard<std::mutex> lock(timer_mutex);
    std::cout << "當(dāng)前定時器時間間隔: " << timer_interval << " 毫秒" << std::endl;
}

int main() {
    std::thread update_thread(update_timer_interval, 2000);
    std::thread read_thread(read_timer_interval);

    update_thread.join();
    read_thread.join();

    return 0;
}

在這段代碼中，update_timer_interval函數(shù)和read_timer_interval函數(shù)在訪問timer_interval這個共享資源時，都使用了std::lock_guard<std::mutex>來自動管理鎖的生命周期。std::lock_guard在構(gòu)造時自動獲取鎖，在析構(gòu)時自動釋放鎖，這樣可以避免因忘記釋放鎖而導(dǎo)致的死鎖問題。

除了互斥鎖，條件變量（condition variable）也可以用于協(xié)調(diào)線程間的協(xié)作，解決定時器相關(guān)的線程安全問題。條件變量可以讓線程在滿足特定條件時被喚醒，從而避免無效的等待和資源浪費(fèi) 。例如，當(dāng)定時器觸發(fā)某個事件時，可以通過條件變量通知其他等待的線程。

5.3定時器精度問題

定時器的精度會受到多種因素的影響。系統(tǒng)負(fù)載是一個重要因素，當(dāng)系統(tǒng)中運(yùn)行著大量的任務(wù)時，CPU 資源會被多個任務(wù)競爭，這可能導(dǎo)致定時器的執(zhí)行被延遲，從而影響精度。硬件性能也起著關(guān)鍵作用，例如硬件時鐘的精度會直接影響定時器的準(zhǔn)確性。在多線程環(huán)境下，線程的調(diào)度和上下文切換也可能對定時器精度產(chǎn)生干擾，因?yàn)榫€程切換需要一定的時間開銷，這可能導(dǎo)致定時器不能按時觸發(fā) 。

為了提高定時器精度，我們可以選擇高精度定時器，如std::chrono::high_resolution_clock，它提供了更高的時間精度。在代碼邏輯上，要盡量減少定時器回調(diào)函數(shù)中的耗時操作，避免因回調(diào)函數(shù)執(zhí)行時間過長而影響下一次定時器的觸發(fā)精度。還可以通過優(yōu)化系統(tǒng)資源分配，合理設(shè)置線程優(yōu)先級等方式，來減少其他任務(wù)對定時器的干擾，從而提高定時器的精度 。例如，在一個實(shí)時數(shù)據(jù)采集系統(tǒng)中，將定時器線程設(shè)置為較高的優(yōu)先級，以確保它能夠及時響應(yīng)并準(zhǔn)確采集數(shù)據(jù)。

5.4常見實(shí)現(xiàn)方案比較

接下來，我們對比一下基于時間輪、最小堆、紅黑樹等數(shù)據(jù)結(jié)構(gòu)的定時器實(shí)現(xiàn)方案 。時間輪是一種獨(dú)特的數(shù)據(jù)結(jié)構(gòu)，它將時間劃分為一個個固定大小的時間槽，通過指針的轉(zhuǎn)動來遍歷各個時間槽，檢查是否有任務(wù)到期 。時間輪的優(yōu)點(diǎn)是插入和刪除操作的時間復(fù)雜度為 O (1)，效率較高，非常適合處理大量定時任務(wù) 。例如，在網(wǎng)絡(luò)通信中，需要頻繁處理大量的心跳檢測任務(wù)，使用時間輪就可以高效地管理這些定時任務(wù) 。時間輪的缺點(diǎn)是精度相對較低，對于時間跨度較大的任務(wù)，可能需要較大的時間輪尺寸，導(dǎo)致內(nèi)存占用增加 。比如，若要設(shè)置一個一年后執(zhí)行的任務(wù)，時間輪的實(shí)現(xiàn)就會變得復(fù)雜，因?yàn)樾枰銐蚨嗟臅r間槽來覆蓋這一年的時間范圍。

最小堆是一種完全二叉樹，其每個節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值 。在定時器實(shí)現(xiàn)中，最小堆常用于按照任務(wù)的到期時間對任務(wù)進(jìn)行排序 。最小堆的優(yōu)點(diǎn)是可以快速找到到期時間最短的任務(wù)，時間復(fù)雜度為 O (1)，插入和刪除操作的時間復(fù)雜度為 O (log n) 。例如，在一個實(shí)時監(jiān)控系統(tǒng)中，需要實(shí)時處理緊急事件，使用最小堆可以確保最早到期的任務(wù)（即最緊急的任務(wù)）能夠被優(yōu)先處理 。最小堆的缺點(diǎn)是如果要刪除堆中的任意一個非堆頂元素，時間復(fù)雜度較高，為 O (n) 。比如，在一個包含大量定時任務(wù)的最小堆中，如果要刪除一個位于中間位置的任務(wù)，就需要遍歷堆中的元素來找到該任務(wù)，然后進(jìn)行刪除操作，這會耗費(fèi)較多的時間。

紅黑樹是一種自平衡的二叉搜索樹，它在插入和刪除操作后能夠自動調(diào)整樹的結(jié)構(gòu)，保持平衡 。紅黑樹的優(yōu)點(diǎn)是插入、刪除和查找操作的平均時間復(fù)雜度都為 O (log n)，性能較為穩(wěn)定 。例如，在一個數(shù)據(jù)庫系統(tǒng)中，需要對大量的定時任務(wù)進(jìn)行精確管理，紅黑樹就可以提供高效的操作性能 。紅黑樹的缺點(diǎn)是實(shí)現(xiàn)相對復(fù)雜，代碼量較大 。比如，在實(shí)現(xiàn)紅黑樹時，需要考慮節(jié)點(diǎn)的顏色、旋轉(zhuǎn)操作等復(fù)雜邏輯，這對開發(fā)者的技術(shù)水平要求較高。

5.5代碼實(shí)現(xiàn)過程詳解

（1）選擇合適方案并闡述理由

在這次百度 C++ 二面的面試場景下，綜合考慮各種因素，我選擇基于最小堆的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)定時器 。首先，面試場景中通常更注重算法的簡潔性和高效性，最小堆的實(shí)現(xiàn)相對較為簡單，代碼邏輯清晰，容易理解和實(shí)現(xiàn) 。比如，在有限的面試時間內(nèi)，使用最小堆可以快速搭建起定時器的基本框架，展示出自己的編程能力和思路。

從實(shí)際需求來看，面試中的定時器實(shí)現(xiàn)主要是為了考察對數(shù)據(jù)結(jié)構(gòu)和算法的掌握程度，以及解決實(shí)際問題的能力 。最小堆能夠快速找到即將到期的任務(wù)，這符合定時器的核心需求 。在實(shí)際應(yīng)用中，比如在一個簡單的任務(wù)調(diào)度系統(tǒng)中，我們希望能夠盡快處理到期的任務(wù)，最小堆就可以很好地滿足這一需求 。而且，最小堆在插入和刪除任務(wù)時的時間復(fù)雜度也能夠滿足大多數(shù)場景的性能要求 。例如，在一個實(shí)時性要求不是特別高的應(yīng)用中，即使插入和刪除操作需要一定的時間（O (log n)），也不會對系統(tǒng)的整體性能產(chǎn)生太大影響 。所以，基于最小堆的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)定時器是一個比較合適的選擇。

（2）定義定時器類

#include <iostream>
#include <queue>
#include <functional>
#include <chrono>

class Timer {
public:
    // 定義定時器任務(wù)結(jié)構(gòu)體
    struct TimerTask {
        std::chrono::milliseconds delay;
        std::chrono::steady_clock::time_point expireTime;
        std::function<void()> callback;

        TimerTask(std::chrono::milliseconds d, std::function<void()> cb)
            : delay(d), expireTime(std::chrono::steady_clock::now() + d), callback(cb) {}

        // 重載小于運(yùn)算符，用于最小堆的比較
        bool operator<(const TimerTask& other) const {
            return expireTime > other.expireTime;
        }
    };

    // 添加定時器任務(wù)
    void addTask(std::chrono::milliseconds delay, std::function<void()> callback) {
        auto task = std::make_shared<TimerTask>(delay, callback);
        taskQueue.push(task);
    }

    // 檢查并執(zhí)行到期的任務(wù)
    void checkTasks() {
        auto now = std::chrono::steady_clock::now();
        while (!taskQueue.empty() && taskQueue.top()->expireTime <= now) {
            auto task = taskQueue.top();
            taskQueue.pop();
            task->callback();
        }
    }

private:
    // 最小堆，存儲定時器任務(wù)
    std::priority_queue<std::shared_ptr<TimerTask>> taskQueue;
};

在這段代碼中，我們定義了一個Timer類。首先，在類內(nèi)部定義了一個TimerTask結(jié)構(gòu)體，它包含了任務(wù)的延遲時間delay、到期時間expireTime以及回調(diào)函數(shù)callback 。expireTime通過當(dāng)前時間加上延遲時間來計算得出。重載的小于運(yùn)算符operator<用于最小堆的比較，使得堆中的任務(wù)按照到期時間從小到大排序 。

addTask成員函數(shù)用于添加定時器任務(wù)，它接收延遲時間和回調(diào)函數(shù)作為參數(shù)，創(chuàng)建一個TimerTask對象并將其加入到最小堆taskQueue中 。

checkTasks成員函數(shù)用于檢查并執(zhí)行到期的任務(wù)，它獲取當(dāng)前時間now，然后在最小堆不為空且堆頂任務(wù)的到期時間小于等于當(dāng)前時間時，取出堆頂任務(wù)并執(zhí)行其回調(diào)函數(shù)，之后將該任務(wù)從堆中移除 。通過這種方式，定時器能夠按照任務(wù)的到期時間順序依次執(zhí)行任務(wù)。

（3）實(shí)現(xiàn)定時器的核心功能函數(shù)

// 示例回調(diào)函數(shù)1
void task1() {
    std::cout << "Task 1 executed." << std::endl;
}

// 示例回調(diào)函數(shù)2
void task2() {
    std::cout << "Task 2 executed." << std::endl;
}

int main() {
    Timer timer;

    // 添加任務(wù)，3秒后執(zhí)行task1
    timer.addTask(std::chrono::seconds(3), task1);
    // 添加任務(wù)，1秒后執(zhí)行task2
    timer.addTask(std::chrono::seconds(1), task2);

    while (true) {
        timer.checkTasks();
        // 模擬其他操作
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }

    return 0;
}

在上述代碼中，我們定義了兩個示例回調(diào)函數(shù)task1和task2，分別用于在任務(wù)執(zhí)行時輸出相應(yīng)的信息 。

在main函數(shù)中，創(chuàng)建了一個Timer對象timer。然后使用addTask函數(shù)添加了兩個任務(wù)：一個任務(wù)是延遲 3 秒后執(zhí)行task1，另一個任務(wù)是延遲 1 秒后執(zhí)行task2 。由于最小堆的特性，任務(wù)會按照到期時間從小到大排序，所以task2會先于task1執(zhí)行。

在一個無限循環(huán)中，不斷調(diào)用timer.checkTasks()來檢查并執(zhí)行到期的任務(wù) 。為了避免過度占用 CPU 資源，在每次循環(huán)中使用std::this_thread::sleep_for(std::chrono::milliseconds(100))使線程休眠 100 毫秒，模擬在執(zhí)行其他操作的同時，定期檢查定時器任務(wù)是否到期 。這樣，定時器就能夠按照設(shè)定的時間間隔準(zhǔn)確地執(zhí)行各個任務(wù)，實(shí)現(xiàn)了定時器的核心功能。

（4）處理邊界情況和異常情況

在實(shí)現(xiàn)定時器的過程中，我們需要仔細(xì)考慮并妥善處理各種邊界情況和異常情況，以確保定時器的穩(wěn)定性和可靠性。

當(dāng)定時器時間為0時，這是一種特殊的邊界情況。在我們之前實(shí)現(xiàn)的代碼中，雖然沒有對這種情況進(jìn)行顯式處理，但從邏輯上來說，當(dāng)添加一個延遲時間為0的任務(wù)時，按照當(dāng)前的實(shí)現(xiàn)，它會立即被加入到任務(wù)隊(duì)列中，并且在checkTasks函數(shù)執(zhí)行時，只要任務(wù)隊(duì)列不為空且該任務(wù)位于堆頂（因?yàn)榈狡跁r間等于當(dāng)前時間，會排在前面），就會立即執(zhí)行。然而，在實(shí)際應(yīng)用中，可能需要根據(jù)具體需求對這種情況進(jìn)行特殊處理。例如，如果不希望立即執(zhí)行延遲為0的任務(wù)，可以拋出一個異常，提示用戶這種設(shè)置不符合預(yù)期，或者將其視為無效輸入進(jìn)行忽略 。

內(nèi)存分配失敗也是一個需要關(guān)注的異常情況。在addTask函數(shù)中，我們使用std::make_shared來創(chuàng)建TimerTask對象，這涉及到內(nèi)存分配操作。如果內(nèi)存分配失敗，std::make_shared會拋出std::bad_alloc異常 。為了處理這個異常，我們可以在addTask函數(shù)中添加異常處理代碼，例如：

void addTask(std::chrono::milliseconds delay, std::function<void()> callback) {
    try {
        auto task = std::make_shared<TimerTask>(delay, callback);
        taskQueue.push(task);
    } catch (const std::bad_alloc& e) {
        std::cerr << "Memory allocation failed: " << e.what() << std::endl;
        // 可以根據(jù)需要進(jìn)行更具體的處理，比如記錄日志、返回錯誤碼等
    }
}

這樣，當(dāng)內(nèi)存分配失敗時，程序會捕獲異常并輸出錯誤信息，避免因未處理的異常導(dǎo)致程序崩潰 。

并發(fā)訪問是一個較為復(fù)雜的問題。如果在多線程環(huán)境下使用定時器，多個線程同時訪問和修改任務(wù)隊(duì)列可能會導(dǎo)致數(shù)據(jù)不一致或競態(tài)條件 。為了解決這個問題，可以使用互斥鎖（std::mutex）來保護(hù)任務(wù)隊(duì)列的訪問。例如，修改Timer類如下：

class Timer {
public:
    // 定義定時器任務(wù)結(jié)構(gòu)體
    struct TimerTask {
        std::chrono::milliseconds delay;
        std::chrono::steady_clock::time_point expireTime;
        std::function<void()> callback;

        TimerTask(std::chrono::milliseconds d, std::function<void()> cb)
            : delay(d), expireTime(std::chrono::steady_clock::now() + d), callback(cb) {}

        // 重載小于運(yùn)算符，用于最小堆的比較
        bool operator<(const TimerTask& other) const {
            return expireTime > other.expireTime;
        }
    };

    // 添加定時器任務(wù)
    void addTask(std::chrono::milliseconds delay, std::function<void()> callback) {
        std::lock_guard<std::mutex> lock(mutex_);
        try {
            auto task = std::make_shared<TimerTask>(delay, callback);
            taskQueue.push(task);
        } catch (const std::bad_alloc& e) {
            std::cerr << "Memory allocation failed: " << e.what() << std::endl;
        }
    }

    // 檢查并執(zhí)行到期的任務(wù)
    void checkTasks() {
        std::lock_guard<std::mutex> lock(mutex_);
        auto now = std::chrono::steady_clock::now();
        while (!taskQueue.empty() && taskQueue.top()->expireTime <= now) {
            auto task = taskQueue.top();
            taskQueue.pop();
            task->callback();
        }
    }

private:
    // 最小堆，存儲定時器任務(wù)
    std::priority_queue<std::shared_ptr<TimerTask>> taskQueue;
    // 互斥鎖，用于保護(hù)任務(wù)隊(duì)列的并發(fā)訪問
    std::mutex mutex_;
};

在上述代碼中，我們在Timer類中添加了一個std::mutex成員變量mutex_，并在addTask和checkTasks函數(shù)中使用std::lock_guard<std::mutex>來自動管理鎖的生命周期 。std::lock_guard在構(gòu)造時自動鎖定互斥鎖，在析構(gòu)時自動解鎖，這樣可以確保在訪問任務(wù)隊(duì)列時，同一時間只有一個線程能夠進(jìn)行操作，有效避免了并發(fā)訪問帶來的問題 。通過這些措施，我們能夠更好地處理定時器實(shí)現(xiàn)過程中的各種邊界和異常情況，提高程序的健壯性和穩(wěn)定性。

（5）代碼優(yōu)化與改進(jìn)

在深入分析基于最小堆實(shí)現(xiàn)的定時器代碼性能時，我們從多個關(guān)鍵維度展開探討。從時間復(fù)雜度來看，當(dāng)前代碼中添加任務(wù)的操作addTask，由于需要將任務(wù)插入到最小堆中，而最小堆的插入操作時間復(fù)雜度為 O (log n)，其中 n 是堆中元素的數(shù)量 。這意味著，隨著定時器任務(wù)數(shù)量的不斷增加，添加新任務(wù)所需的時間也會相應(yīng)增長 。在一個處理大量網(wǎng)絡(luò)請求的服務(wù)器程序中，如果每個請求都關(guān)聯(lián)一個定時器任務(wù)，當(dāng)請求量達(dá)到數(shù)千甚至數(shù)萬個時，每次添加新的定時器任務(wù)都可能需要耗費(fèi)一定的時間，這對于系統(tǒng)的實(shí)時性和響應(yīng)速度會產(chǎn)生一定的影響 。

檢查并執(zhí)行到期任務(wù)的checkTasks函數(shù)，雖然在理想情況下，當(dāng)堆頂任務(wù)到期時，執(zhí)行和移除操作的時間復(fù)雜度為 O (1)，但在實(shí)際情況中，由于需要遍歷堆來查找所有到期的任務(wù)，其時間復(fù)雜度可能會達(dá)到 O (n) 。當(dāng)存在大量任務(wù)且到期時間較為集中時，checkTasks函數(shù)可能需要花費(fèi)較長時間來處理所有到期任務(wù)，導(dǎo)致系統(tǒng)在這段時間內(nèi)無法及時響應(yīng)其他操作 。

在空間復(fù)雜度方面，代碼使用std::priority_queue來存儲定時器任務(wù)，其空間復(fù)雜度為 O (n)，n 為任務(wù)數(shù)量 。隨著任務(wù)數(shù)量的不斷增多，內(nèi)存占用也會線性增加 。如果在一個資源受限的嵌入式系統(tǒng)中使用該定時器，當(dāng)任務(wù)數(shù)量過多時，可能會導(dǎo)致內(nèi)存不足，影響系統(tǒng)的正常運(yùn)行 。

內(nèi)存使用方面，std::shared_ptr用于管理TimerTask對象的生命周期，雖然這種智能指針的使用方式能夠有效避免內(nèi)存泄漏，但在頻繁創(chuàng)建和銷毀TimerTask對象時，會增加內(nèi)存分配和釋放的開銷 。在一個高并發(fā)的場景中，大量定時器任務(wù)被頻繁創(chuàng)建和銷毀，這可能會導(dǎo)致內(nèi)存分配器的壓力增大，進(jìn)而影響系統(tǒng)的整體性能 。

優(yōu)化后的代碼展示與說明：

#include <iostream>
#include <queue>
#include <functional>
#include <chrono>
#include <unordered_map>

class Timer {
public:
    struct TimerTask {
        std::chrono::milliseconds delay;
        std::chrono::steady_clock::time_point expireTime;
        std::function<void()> callback;
        int id; // 新增任務(wù)ID，用于快速定位和刪除任務(wù)

        TimerTask(std::chrono::milliseconds d, std::function<void()> cb, int i)
            : delay(d), expireTime(std::chrono::steady_clock::now() + d), callback(cb), id(i) {}

        bool operator<(const TimerTask& other) const {
            return expireTime > other.expireTime;
        }
    };

    // 使用unordered_map來快速定位任務(wù)，加速刪除操作
    std::unordered_map<int, std::shared_ptr<TimerTask>> taskMap; 

    void addTask(std::chrono::milliseconds delay, std::function<void()> callback, int id) {
        auto task = std::make_shared<TimerTask>(delay, callback, id);
        taskQueue.push(task);
        taskMap[id] = task;
    }

    void cancelTask(int id) {
        auto it = taskMap.find(id);
        if (it != taskMap.end()) {
            auto task = it->second;
            // 標(biāo)記任務(wù)為無效，而不是直接從堆中刪除，避免堆調(diào)整的開銷
            task->callback = []() {}; 
            taskMap.erase(it);
        }
    }

    void checkTasks() {
        auto now = std::chrono::steady_clock::now();
        while (!taskQueue.empty() && taskQueue.top()->expireTime <= now) {
            auto task = taskQueue.top();
            taskQueue.pop();
            if (task->callback != nullptr) {
                task->callback();
            }
        }
    }

private:
    std::priority_queue<std::shared_ptr<TimerTask>> taskQueue;
};

對比優(yōu)化前后的代碼，主要有以下幾個顯著的差異和優(yōu)化措施 。首先，在TimerTask結(jié)構(gòu)體中新增了id成員，用于唯一標(biāo)識每個任務(wù) 。這為后續(xù)的快速定位和刪除任務(wù)提供了基礎(chǔ) 。

引入了std::unordered_map<int, std::shared_ptr<TimerTask>> taskMap，它可以根據(jù)任務(wù) ID 快速定位到對應(yīng)的TimerTask對象，將刪除任務(wù)的時間復(fù)雜度從原來的 O (n) 降低到 O (1) 。在addTask函數(shù)中，不僅將任務(wù)添加到最小堆taskQueue中，還同時將任務(wù)存儲到taskMap中，以便后續(xù)快速查找和操作 。

在cancelTask函數(shù)中，通過taskMap查找并刪除任務(wù)，并且采用標(biāo)記任務(wù)無效（將回調(diào)函數(shù)設(shè)置為空函數(shù)）的方式，避免了直接從最小堆中刪除任務(wù)時復(fù)雜的堆調(diào)整操作，進(jìn)一步提高了刪除任務(wù)的效率 。

在checkTasks函數(shù)中，增加了對任務(wù)回調(diào)函數(shù)是否為空的檢查，確保只有有效的任務(wù)才會被執(zhí)行，避免執(zhí)行已被取消的任務(wù) 。通過這些優(yōu)化措施，優(yōu)化后的代碼在性能和效率上有了顯著提升，能夠更好地滿足實(shí)際應(yīng)用中對定時器的高效管理需求 。