百度C++二面挑戰(zhàn)：手撕定時器實現(xiàn)全解析
在C++編程領域，定時器是極為關鍵的基礎組件，它如同一位精準的時間管家，在諸多場景里發(fā)揮著不可或缺的作用。在網絡編程中，它能把控連接的超時處理，保障網絡通信的高效與穩(wěn)定；游戲開發(fā)里，定時刷新畫面、觸發(fā)特定游戲事件等都離不開它；系統(tǒng)運維時，可利用定時器定期執(zhí)行日志清理、數據備份等任務。
而在百度 C++ 二面這樣的高水平面試中，“手撕定時器實現(xiàn)” 這一挑戰(zhàn)，絕非只是簡單的代碼編寫，實則是對面試者 C++ 知識深度、算法設計能力、問題分析與解決能力的全面考驗。要成功攻克它，需透徹理解定時器原理，精心挑選并設計合適的數據結構，巧妙構建高效的任務調度與觸發(fā)機制。接下來，讓我們一步步深入剖析，揭開百度 C++ 二面定時器實現(xiàn)的神秘面紗，探尋如何在面試中漂亮地完成這一高難度任務。
Part1.定時器實現(xiàn)前的知識回顧
1.1C++ 基礎語法
在深入研究定時器實現(xiàn)之前，讓我們先來回顧一下 C++ 的基礎語法。C++ 作為一種強大的編程語言，具有豐富的特性和靈活的語法結構 。函數定義是 C++ 編程的基礎，它包含返回類型、函數名、參數列表以及函數體。例如，一個簡單的加法函數可以這樣定義：
int add(int a, int b) {
return a + b;
}這里int是返回類型，表示函數將返回一個整數；add是函數名，方便我們在程序中調用該函數；(int a, int b)是參數列表，定義了函數接收兩個整數類型的參數；函數體{ return a + b; }則實現(xiàn)了具體的加法邏輯 。
類是 C++ 面向對象編程的核心概念，它是一種用戶自定義的數據類型，將數據和操作數據的函數封裝在一起。比如，我們定義一個簡單的Rectangle類來表示矩形：
class Rectangle {
public:
int width;
int height;
int area() {
return width * height;
}
};在這個類中，width和height是類的數據成員，用于存儲矩形的寬和高；area是類的成員函數，用于計算矩形的面積。通過類的實例化，我們可以創(chuàng)建多個矩形對象，并調用它們的成員函數進行操作 。
指針與引用也是 C++ 中非常重要的概念。指針是一個變量，它存儲的是另一個變量的內存地址，通過指針可以直接訪問和修改內存中的數據 。例如：
int num = 10;
int *ptr = #這里ptr是一個指針，它指向num的內存地址，通過*ptr可以訪問num的值。引用則是一個變量的別名，它與被引用的變量共享同一內存位置 。比如：
int num = 10;
int &ref = num;ref是num的引用，對ref的操作等同于對num的操作。指針和引用在 C++ 中常用于函數參數傳遞、內存管理等場景，熟練掌握它們對于理解和編寫高效的 C++ 代碼至關重要。
1.2時間相關知識
在 C++ 中，獲取時間有多種方式，其中<chrono>庫是 C++11 引入的一個強大的時間處理庫，它提供了高精度的時間測量和計算功能 。例如，使用std::chrono::high_resolution_clock可以獲取高精度的時間點：
#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()獲取當前時間點，通過計算兩個時間點的差值，并使用std::chrono::duration_cast進行類型轉換，得到操作所花費的時間，單位為毫秒。
<ctime>庫也是常用的時間處理庫，它提供了與 C 語言兼容的時間函數 。比如，time函數可以獲取從 1970 年 1 月 1 日 00:00:00 到當前時間的秒數：
#include <iostream>
#include <ctime>
int main() {
time_t now = time(nullptr);
std::cout << "當前時間的秒數：" << now << std::endl;
return 0;
}在時間單位換算方面，1 秒等于 1000 毫秒，1 毫秒等于 1000 微秒，1 微秒等于 1000 納秒 。在進行時間計算時，需要注意不同時間單位之間的轉換，以確保計算結果的準確性。例如，如果要將秒數轉換為毫秒數，只需將秒數乘以 1000 即可。
1.3數據結構基礎
實現(xiàn)定時器可能會用到多種數據結構，每種數據結構都有其獨特的特點和適用場景 。鏈表是一種線性數據結構，它由一系列節(jié)點組成，每個節(jié)點包含數據和指向下一個節(jié)點的指針 。鏈表的優(yōu)點是插入和刪除操作效率高，時間復雜度為 O (1)，因為只需修改指針的指向即可 。例如，在一個簡單的單向鏈表中插入一個新節(jié)點：
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é)點結構ListNode，并實現(xiàn)了一個插入節(jié)點的函數insertNode，該函數將新節(jié)點插入到鏈表頭部，時間復雜度為 O (1)。鏈表的缺點是查找操作效率較低，時間復雜度為 O (n)，因為需要從頭節(jié)點開始逐個遍歷節(jié)點，直到找到目標節(jié)點。
堆是一種特殊的樹形數據結構，它分為最大堆和最小堆 。在最大堆中，每個節(jié)點的值都大于或等于其子節(jié)點的值；在最小堆中，每個節(jié)點的值都小于或等于其子節(jié)點的值 。堆常用于實現(xiàn)優(yōu)先隊列，在定時器實現(xiàn)中，可以利用最小堆來存儲定時器任務，按照任務的到期時間從小到大排序 。
堆的插入和刪除操作時間復雜度為 O (log n)，因為需要維護堆的性質，進行堆調整操作 。例如，使用 C++ 標準庫中的priority_queue（默認是最大堆，通過自定義比較函數可以實現(xiàn)最小堆）來實現(xiàn)一個簡單的定時器任務隊列：
#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 << "任務ID: " << task.id << ", 到期時間: " << task.expireTime << std::endl;
}
return 0;
}在上述代碼中，定義了一個TimerTask結構體表示定時器任務，包含任務 ID 和到期時間。通過自定義比較函數CompareByExpireTime，使priority_queue按照任務的到期時間從小到大排序，模擬了一個基于最小堆的定時器任務隊列。
紅黑樹是一種自平衡的二叉搜索樹，它在插入和刪除操作后能夠自動調整樹的結構，保持平衡，從而保證查找、插入和刪除操作的時間復雜度均為 O (log n) 。紅黑樹的每個節(jié)點都帶有顏色屬性，通過顏色規(guī)則來維護樹的平衡 。在定時器實現(xiàn)中，紅黑樹可以用于高效地管理定時器任務，快速查找即將到期的任務 。例如，在一些高性能的網絡庫中，常使用紅黑樹來實現(xiàn)定時器管理器 。雖然紅黑樹的實現(xiàn)較為復雜，但它在處理大量數據時具有出色的性能表現(xiàn)，能夠滿足定時器對高效性和穩(wěn)定性的要求。
Part2.C++定時器是什么？
2.1定時器概述
C++ 定時器，簡單來說，就是一種能夠讓程序在指定的時間間隔后執(zhí)行特定任務的機制 。它就像是一個精準的時間管家，按照你設定的時間安排，準時觸發(fā)相應的操作。比如，你可以設定一個定時器，讓它每隔 1 秒鐘打印一次 “Hello, Timer!”；或者在程序啟動 5 分鐘后，自動執(zhí)行某個數據備份的函數。它為程序賦予了時間驅動的能力，使得程序能夠更加智能、高效地運行。
2.2 C++定時器的工作原理
C++ 定時器的工作原理，其實并不復雜。我們可以把它想象成一個獨立的小助手，在后臺默默為我們服務。當你創(chuàng)建一個定時器時，程序會為它分配一個獨立的線程。這個線程就像是定時器的專屬 “跑腿”，專門負責處理與時間相關的任務。
接下來，你需要告訴定時器你希望它等待多長時間，以及在時間到達后需要執(zhí)行的任務。定時器會把這些信息記錄下來，然后讓它的 “跑腿” 線程進入等待狀態(tài)。在等待的過程中，線程會按照你設定的時間間隔進行休眠，就像人在睡覺一樣，直到設定的時間到達。
當時間一到，線程就會從休眠中蘇醒過來，然后去執(zhí)行你預先設定好的任務。這個任務可以是任何你想要的操作，比如調用一個函數、執(zhí)行一段代碼塊，甚至是啟動另一個程序。任務執(zhí)行完畢后，定時器可以根據你的需求，選擇繼續(xù)等待下一個時間間隔，再次執(zhí)行任務，或者直接結束工作。
（1）定時器分類
一般定時任務的形式表現(xiàn)為：
- 經過固定時間后觸發(fā)
- 按照固定頻率周期性觸發(fā)
- 在某個時刻觸發(fā)。
（2）定時器的本質
定時器究竟是什么，不妨將其視作這樣一種數據結構：
- 存儲一系列的任務集合，并且deadline越接近的任務，擁有越高的執(zhí)行優(yōu)先權
- 一般定時器支持如下幾種操作：add：新增任務、delete：取消某個任務、run：執(zhí)行到期的任務、update：更新到期時間。
那么，該如何判斷一個任務是否到期呢？
輪詢的方式是每隔一個時間片檢查最近的任務是否到期。例如，可以創(chuàng)建一個線程每隔 100 毫秒掃描一次到期的任務。這種方式的缺點是：假設有 1 萬個 5 秒后到期的定時請求，而掃描周期是 100 毫秒，那么掃描線程在這 5 秒內會不斷對這 1 萬個任務進行掃描遍歷，額外掃描 40 多次（每 100 毫秒掃描一次，5 秒內要掃描近 50 次），非常浪費 CPU 資源。
解決方法有：采用 epoll、sleep 之類的喚醒操作；或者使用時間輪。
另一種方式是睡眠 / 喚醒機制：不斷查找截止時間（deadline）最近的任務，若已到期就執(zhí)行；否則就睡眠到該任務到期為止。在睡眠過程中，如果有新任務被添加或刪除，可能會改變最近的截止時間，這時線程會被喚醒并重新查找最近的截止時間。
2.3定時器與線程
對于服務端而言，驅動其邏輯運行的事件主要有兩類：一類是網絡事件，另一類是時間事件。
在不同的框架里，這兩種事件有著不同的實現(xiàn)方式：
第一種，網絡事件和時間事件在一個線程中配合使用，比如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++){
//.... 網絡事件處理
}
update_timer(); //時間事件處理
}第二種，網絡事件和時間事件在不同線程中處理，比如skynet
// 第二種 在其他線程添加定時任務
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);需要注意兩點：
- 定時任務盡量避免執(zhí)行阻塞性操作，不然可能會導致后續(xù)事件無法按時處理。
- 同時，任務也不能過度占用 CPU，否則會使應用程序的性能下降。
2.4定時器的數據結構該如何選擇？
需要一種有序的數據結構，要求在進行增刪操作時能保持其有序性，并且能夠快速查找其中的最小節(jié)點。為滿足對任務到期判斷及相關操作的需求，有如下數據結構可供選擇：
- 有序鏈表：在邏輯上，元素按順序排列，節(jié)點通過指針連接。其增刪操作相對靈活，只需調整指針，無需移動大量元素。但在查找特定元素時，需從頭節(jié)點開始順序遍歷，時間復雜度較高。
- 紅黑樹：一種自平衡二叉查找樹，節(jié)點帶有紅或黑的顏色屬性。其增刪查操作的時間復雜度均為 O (log?n) 。在紅黑樹中，最左側節(jié)點即為最小節(jié)點，查找該節(jié)點的時間復雜度同樣為 O (log?n) 。它能在插入和刪除節(jié)點時通過特定操作維持平衡，以確保良好的查找性能。
- 最小堆：是一種特殊的完全二叉樹結構，父節(jié)點的值小于或等于子節(jié)點的值，根節(jié)點是堆中的最小值。插入和查找操作的時間復雜度為 O (log?n) ，刪除操作時間復雜度通常為 O (n) ，不過借助輔助數據結構（如 map 或 hashmap）可加快刪除速度。對于最小堆，獲取根節(jié)點（即最小節(jié)點）的時間復雜度為 O (1) 。
- 跳表：本質是有序鏈表的改進，通過引入多層索引結構來提升查找效率。其增刪查操作的時間復雜度平均為O (log?n) 最左側節(jié)點為最小節(jié)點，查找該節(jié)點的時間復雜度為O (1) 。但跳表的空間復雜度較高，為O (1.5n) 。
- 時間輪：對于像 Linux 這類對定時器依賴程度高（如網絡子模塊的 TCP 協(xié)議大量使用定時器）的操作系統(tǒng)，上述數據結構無法滿足需求。Linux 采用了更為高效的定時器算法 —— 時間輪（timewheel）。時間輪在進行增刪查操作以及查找最小節(jié)點時，時間復雜度均為 O (1) ，能更高效地處理大量定時任務。
關于如何選擇定時器實現(xiàn)方式，可以根據任務量大小來決定：
- 在任務量較小的場景下，采用最小堆實現(xiàn)更為合適。它可以根據堆頂元素設置超時時間，采用數組存儲結構，內存消耗更少，能取得較好的效果。而時間輪定時器由于需要維護專門的線程來驅動指針轉動，還要開辟 bucket 數組，內存消耗較大，在此場景下使用會造成資源浪費。
- 在任務量較大的場景中，最小堆的插入操作復雜度為 O (lgN)，相比時間輪的 O (1) 會導致性能下降，因此更適合使用時間輪實現(xiàn)。
- 在業(yè)界實踐中，像服務治理中的心跳檢測等功能需要維護大量的連接心跳，這類場景下時間輪通常是首選方案。
Part3.C++定時器實現(xiàn)方式
3.1基于std::thread的定時器實現(xiàn)
基于 std::thread 實現(xiàn)定時器的原理較為直觀，通過創(chuàng)建一個新線程，讓該線程在設定的時間間隔內休眠，當休眠時間結束后，執(zhí)行預先設定的任務 。
下面通過一個簡單的代碼示例來展示其實現(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; // 確保在結束時將is_running設置為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;
// 設置一個2秒總時長，每200毫秒執(zhí)行一次任務
timer.start(std::chrono::milliseconds(2000),
std::chrono::milliseconds(200),
[]() {
std::cout << "執(zhí)行任務" << std::endl;
});
// 主線程繼續(xù)運行，可以在這里添加其他邏輯
std::this_thread::sleep_for(std::chrono::seconds(2));
timer.stop();
return 0;
}在這段代碼中，CustomTimer類封裝了定時器的功能。start函數接受總時長total_duration、時間間隔interval以及要執(zhí)行的任務task作為參數。在start函數內部，首先創(chuàng)建一個新線程timer_thread，線程的執(zhí)行體是一個 Lambda 表達式。在這個表達式中，記錄了開始時間start_time和結束時間end_time，通過一個循環(huán)不斷檢查當前時間是否超過結束時間，并且is_running標志為真。在每次循環(huán)中，線程通過std::this_thread::sleep_until休眠到下一個檢查時間next_check，當時間到達時，執(zhí)行任務task。stop函數用于停止定時器，它將is_running標志設為假，并等待線程結束。
這種實現(xiàn)方式適用于需要在指定時間內定期執(zhí)行某些操作，并且在時間結束后自動停止的場景 。它的優(yōu)點很明顯，首先是簡單易懂，使用線程是最基本的并行處理方式，對于初學者來說，易于理解和實現(xiàn)。其次，靈活性高，可以在任何時間創(chuàng)建線程，并且能夠精確控制定時器的生命周期，方便管理。
然而，它也存在一些缺點。由于每個std::thread都可能占用相當多的系統(tǒng)資源，尤其是在創(chuàng)建大量線程時，資源消耗問題會變得比較嚴重。在涉及多線程時，開發(fā)者需要處理線程的同步和并發(fā)問題，這可能會導致程序復雜度增加。相比于更高級的并發(fā)管理庫，如std::async或線程池，std::thread提供的控制能力較為基本，缺乏一些高級的特性。
3.2利用 std::async 和 std::future實現(xiàn)定時器
std::async和std::future是 C++11 引入的高級并發(fā)工具，它們?yōu)楫惒饺蝿盏墓芾硖峁┝艘环N更加簡潔和高效的方式 。std::async用于啟動一個異步任務，它會返回一個std::future對象，通過這個對象可以獲取異步任務的結果，或者查詢任務的狀態(tài)。std::future提供了諸如get（等待任務完成并獲取結果）、wait（等待任務完成）、wait_for（等待一段時間，如果任務在這段時間內完成則返回）等方法，方便對異步任務進行控制。下面是使用std::async和std::future實現(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í)行任務" << std::endl;
});
std::this_thread::sleep_for(std::chrono::seconds(2));
timer.stop();
return 0;
}在這個示例中，CustomTimer類的start函數使用std::async啟動一個異步任務，任務的執(zhí)行體同樣是一個 Lambda 表達式。在這個表達式中，實現(xiàn)了與基于std::thread實現(xiàn)類似的定時邏輯，通過休眠和檢查時間來定期執(zhí)行任務。std::future<void>對象future_task用于獲取異步任務的結果，但在這個定時器實現(xiàn)中，我們并不需要獲取具體的結果，只是利用std::async來管理異步任務的生命周期。
與std::thread相比，使用std::async和std::future實現(xiàn)的定時器，最大的優(yōu)勢在于可以自動管理線程的生命周期，開發(fā)者不需要顯式地創(chuàng)建和管理線程，這使得代碼更加簡潔且易于維護 。這種實現(xiàn)方式適用于希望簡化線程管理、減少顯式線程控制代碼的場景。例如，在一些對代碼簡潔性要求較高，且不需要對線程進行精細控制的應用中，使用std::async和std::future實現(xiàn)定時器是一個不錯的選擇。它還適用于需要處理異步任務結果的場景，因為std::future提供了方便的方法來獲取任務的執(zhí)行結果。然而，由于其內部實現(xiàn)機制相對復雜，可能在一些對性能要求極高，且資源有限的場景下，不如基于std::thread的簡單實現(xiàn)高效。
3.3基于時間輪算法的定時器實現(xiàn)
時間輪算法是一種高效的定時器實現(xiàn)方式，它的工作原理類似于鐘表的表盤 。想象一個環(huán)形的表盤，被分成了多個格子，每個格子代表一個固定的時間間隔，我們稱之為一個 “時間槽”。表盤上有一個指針，會按照固定的時間間隔移動，每移動一次，就檢查當前指針所指向的時間槽中是否有任務需要執(zhí)行。當需要添加一個定時任務時，根據任務的到期時間，計算出它應該被放置在哪個時間槽中。如果任務的到期時間超過了當前時間輪的范圍，可能會使用多層時間輪來處理，類似于鐘表中時針、分針和秒針的協(xié)作。
為了更直觀地理解，我們來看一個簡單的示意圖：
圖片
在這個圖中，時間輪被分成了 8 個時間槽，每個時間槽的時間間隔為 1 秒。假設當前指針指向時間槽 0，當有一個任務需要在 3 秒后執(zhí)行時，它會被放置在時間槽 3 中。當指針移動到時間槽 3 時，就會執(zhí)行該任務。如果有一個任務需要在 10 秒后執(zhí)行，由于超過了當前時間輪的 8 秒范圍，可能會被放置到上層時間輪的某個槽中，上層時間輪的每個槽可能代表 8 秒的時間間隔。
下面是一個簡化的時間輪定時器的代碼實現(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 << "任務執(zhí)行" << std::endl; }, 3); // 3秒后執(zhí)行任務
std::this_thread::sleep_for(std::chrono::seconds(5));
return 0;
}在這段代碼中，TimeWheel類實現(xiàn)了時間輪定時器的基本功能。構造函數接受時間槽的時間間隔tick_duration和時間輪的大小wheel_size作為參數。add_task函數用于添加任務，它根據任務的延遲時間計算出應該放置的時間槽，并將任務加入到對應的時間槽隊列中。run函數啟動一個線程，該線程會每隔tick_duration時間檢查當前時間槽中是否有任務，若有則執(zhí)行任務，然后將指針移動到下一個時間槽。
為了優(yōu)化性能，可以采用一些策略。例如，在處理大量任務時，可以使用哈希表來快速定位任務所在的時間槽，減少查找時間。對于多層時間輪的實現(xiàn)，可以合理分配各層時間輪的時間間隔和大小，以提高任務調度的效率。還可以考慮使用線程池來執(zhí)行任務，避免頻繁創(chuàng)建和銷毀線程帶來的開銷 。
Part4.C++定時器的應用場景實戰(zhàn)
4.1心跳檢測機制中的應用
在分布式系統(tǒng)或網絡通信中，心跳檢測是一種常用的機制，用于監(jiān)控遠程節(jié)點或連接的存活狀態(tài) 。其原理類似于我們日常體檢時檢查心跳，通過定期發(fā)送心跳消息來確認對方是否正常工作。如果在一定時間內沒有收到對方的心跳響應，就可以認為連接出現(xiàn)問題或者對方節(jié)點已失效。
在 C++ 中實現(xiàn)心跳檢測機制，定時器扮演著關鍵的角色。我們可以使用定時器來控制心跳消息的發(fā)送頻率，比如每隔 5 秒鐘發(fā)送一次心跳包。當接收到對方的心跳響應時，重置定時器；如果定時器超時仍未收到響應，則觸發(fā)相應的處理邏輯，如重新建立連接或提示用戶連接異常。
下面是一個使用boost::asio庫實現(xiàn)的簡單心跳檢測示例代碼，展示了定時器在其中的應用：
#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) {
// 異步解析服務器地址
resolver_.async_resolve(endpoint,
[this](const boost::system::error_code& ec,
boost::asio::ip::tcp::resolver::iterator it) {
if (!ec) {
// 異步連接到服務器
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() {
// 設置下一次心跳的時間
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類負責管理心跳檢測的邏輯。構造函數中，通過resolver_異步解析服務器地址，并異步連接到服務器。start_heartbeat函數使用timer_定時器來控制心跳消息的發(fā)送頻率，每隔next_heartbeat_秒發(fā)送一次心跳消息。send_heartbeat函數負責將心跳消息異步發(fā)送到服務器。當定時器超時時，會調用async_wait的回調函數，在回調函數中先發(fā)送心跳消息，然后再次啟動定時器，實現(xiàn)循環(huán)心跳檢測。如果在發(fā)送心跳消息或處理定時器事件時出現(xiàn)錯誤，會在控制臺輸出相應的錯誤信息。
4.2游戲開發(fā)中的技能冷卻系統(tǒng)
在游戲開發(fā)中，技能冷卻系統(tǒng)是一個非常重要的功能，它能夠增加游戲的策略性和挑戰(zhàn)性 。其主要需求是控制玩家使用技能的頻率，每個技能在使用后需要經過一定的冷卻時間才能再次使用。同時，需要在游戲界面上直觀地顯示技能的冷卻狀態(tài)，讓玩家清楚地知道技能何時可以再次釋放。
基于定時器的技能冷卻系統(tǒng)設計方案如下：為每個技能創(chuàng)建一個對應的定時器，當技能被使用時，啟動定時器并設置冷卻時間。在定時器運行期間，技能處于冷卻狀態(tài)，無法再次使用。當定時器超時，技能冷卻完成，玩家可以再次使用該技能。為了在界面上顯示技能的冷卻狀態(tài)，可以通過更新技能圖標的顏色、透明度或添加倒計時數字等方式來實現(xiàn)。
下面是一個簡單的技能冷卻系統(tǒng)的實現(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方法用于使用技能，如果技能可用，則啟動冷卻定時器，并將技能標記為不可用；如果技能正在冷卻中，則提示玩家剩余冷卻時間。update方法在每一幀被調用，用于更新技能的剩余冷卻時間。start_cooldown方法使用線程和定時器來實現(xiàn)技能的冷卻邏輯。
在main函數中，創(chuàng)建了一個Skill對象fireball，并使用SFML庫創(chuàng)建了一個簡單的圖形界面。當玩家按下空格鍵時，嘗試使用fireball技能。在游戲循環(huán)中，不斷更新技能的冷卻狀態(tài)，并在界面上顯示技能名稱和剩余冷卻時間。如果技能處于冷卻狀態(tài)，會在技能名稱下方顯示剩余冷卻時間；如果技能可用，則不顯示冷卻時間。運行這個程序，你可以直觀地看到技能冷卻系統(tǒng)的效果，體驗定時器在游戲開發(fā)中的實際應用 。
Part5.手撕定時器演練
5.1定時器的功能需求分析
在深入探討定時器的實現(xiàn)方案之前，我們先來明確一下定時器應具備的核心功能 。首先，設置定時時間是定時器最基本的功能之一，用戶需要能夠根據實際需求靈活設定任務的執(zhí)行時間 。比如，在一個網絡爬蟲程序中，可能需要每隔一段時間就去訪問特定的網站獲取最新信息，這個間隔時間就需要通過定時器的設置定時時間功能來確定。
執(zhí)行回調函數也是定時器的關鍵功能。當設定的時間到達時，定時器要能夠自動觸發(fā)并執(zhí)行預先定義好的回調函數，完成特定的任務 。例如，在一個定時備份系統(tǒng)中，回調函數可以實現(xiàn)將重要數據備份到指定存儲位置的操作。支持多個定時器同時工作也是必不可少的。在實際應用中，往往會有多個不同的任務需要在不同的時間點執(zhí)行 。以一個電商系統(tǒng)為例，可能同時存在定時更新商品庫存信息、定時發(fā)送促銷郵件、定時清理過期訂單等多個定時任務，這就要求定時器能夠管理多個定時器實例，確保每個任務都能按時執(zhí)行。
此外，能夠取消定時器也是一項重要功能。當某個定時任務不再需要執(zhí)行時，用戶應該可以隨時取消對應的定時器 。比如，在一個視頻會議系統(tǒng)中，如果用戶臨時取消了預約的會議，那么相應的定時提醒任務就需要被取消，避免不必要的通知干擾。
5.2線程安全問題
（1）問題產生原因：在多線程環(huán)境下，定時器可能會面臨線程安全問題。當多個線程同時訪問和操作定時器相關的資源時，就容易出現(xiàn)數據競爭和不一致的情況。例如，一個線程正在修改定時器的時間間隔，而另一個線程同時嘗試讀取這個時間間隔，就可能導致讀取到的數據不準確。這是因為線程的調度是由操作系統(tǒng)決定的，具有不確定性，多個線程對共享資源的并發(fā)訪問可能會破壞數據的完整性 。
（2）解決方案探討：為了解決線程安全問題，我們可以使用互斥鎖（mutex）來保護共享資源。互斥鎖就像是一把鎖，當一個線程獲取到這把鎖時，其他線程就無法訪問被鎖保護的資源，直到該線程釋放鎖。在 C++ 中，我們可以使用std::mutex來實現(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 << "當前定時器時間間隔: " << 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函數和read_timer_interval函數在訪問timer_interval這個共享資源時，都使用了std::lock_guard<std::mutex>來自動管理鎖的生命周期。std::lock_guard在構造時自動獲取鎖，在析構時自動釋放鎖，這樣可以避免因忘記釋放鎖而導致的死鎖問題。
除了互斥鎖，條件變量（condition variable）也可以用于協(xié)調線程間的協(xié)作，解決定時器相關的線程安全問題。條件變量可以讓線程在滿足特定條件時被喚醒，從而避免無效的等待和資源浪費 。例如，當定時器觸發(fā)某個事件時，可以通過條件變量通知其他等待的線程。
5.3定時器精度問題
定時器的精度會受到多種因素的影響。系統(tǒng)負載是一個重要因素，當系統(tǒng)中運行著大量的任務時，CPU 資源會被多個任務競爭，這可能導致定時器的執(zhí)行被延遲，從而影響精度。硬件性能也起著關鍵作用，例如硬件時鐘的精度會直接影響定時器的準確性。在多線程環(huán)境下，線程的調度和上下文切換也可能對定時器精度產生干擾，因為線程切換需要一定的時間開銷，這可能導致定時器不能按時觸發(fā) 。
為了提高定時器精度，我們可以選擇高精度定時器，如std::chrono::high_resolution_clock，它提供了更高的時間精度。在代碼邏輯上，要盡量減少定時器回調函數中的耗時操作，避免因回調函數執(zhí)行時間過長而影響下一次定時器的觸發(fā)精度。還可以通過優(yōu)化系統(tǒng)資源分配，合理設置線程優(yōu)先級等方式，來減少其他任務對定時器的干擾，從而提高定時器的精度 。例如，在一個實時數據采集系統(tǒng)中，將定時器線程設置為較高的優(yōu)先級，以確保它能夠及時響應并準確采集數據。
5.4常見實現(xiàn)方案比較
接下來，我們對比一下基于時間輪、最小堆、紅黑樹等數據結構的定時器實現(xiàn)方案 。時間輪是一種獨特的數據結構，它將時間劃分為一個個固定大小的時間槽，通過指針的轉動來遍歷各個時間槽，檢查是否有任務到期 。時間輪的優(yōu)點是插入和刪除操作的時間復雜度為 O (1)，效率較高，非常適合處理大量定時任務 。例如，在網絡通信中，需要頻繁處理大量的心跳檢測任務，使用時間輪就可以高效地管理這些定時任務 。時間輪的缺點是精度相對較低，對于時間跨度較大的任務，可能需要較大的時間輪尺寸，導致內存占用增加 。比如，若要設置一個一年后執(zhí)行的任務，時間輪的實現(xiàn)就會變得復雜，因為需要足夠多的時間槽來覆蓋這一年的時間范圍。
最小堆是一種完全二叉樹，其每個節(jié)點的值都小于或等于其子節(jié)點的值 。在定時器實現(xiàn)中，最小堆常用于按照任務的到期時間對任務進行排序 。最小堆的優(yōu)點是可以快速找到到期時間最短的任務，時間復雜度為 O (1)，插入和刪除操作的時間復雜度為 O (log n) 。例如，在一個實時監(jiān)控系統(tǒng)中，需要實時處理緊急事件，使用最小堆可以確保最早到期的任務（即最緊急的任務）能夠被優(yōu)先處理 。最小堆的缺點是如果要刪除堆中的任意一個非堆頂元素，時間復雜度較高，為 O (n) 。比如，在一個包含大量定時任務的最小堆中，如果要刪除一個位于中間位置的任務，就需要遍歷堆中的元素來找到該任務，然后進行刪除操作，這會耗費較多的時間。
紅黑樹是一種自平衡的二叉搜索樹，它在插入和刪除操作后能夠自動調整樹的結構，保持平衡 。紅黑樹的優(yōu)點是插入、刪除和查找操作的平均時間復雜度都為 O (log n)，性能較為穩(wěn)定 。例如，在一個數據庫系統(tǒng)中，需要對大量的定時任務進行精確管理，紅黑樹就可以提供高效的操作性能 。紅黑樹的缺點是實現(xiàn)相對復雜，代碼量較大 。比如，在實現(xiàn)紅黑樹時，需要考慮節(jié)點的顏色、旋轉操作等復雜邏輯，這對開發(fā)者的技術水平要求較高。
5.5代碼實現(xiàn)過程詳解
（1）選擇合適方案并闡述理由
在這次百度 C++ 二面的面試場景下，綜合考慮各種因素，我選擇基于最小堆的數據結構來實現(xiàn)定時器 。首先，面試場景中通常更注重算法的簡潔性和高效性，最小堆的實現(xiàn)相對較為簡單，代碼邏輯清晰，容易理解和實現(xiàn) 。比如，在有限的面試時間內，使用最小堆可以快速搭建起定時器的基本框架，展示出自己的編程能力和思路。
從實際需求來看，面試中的定時器實現(xiàn)主要是為了考察對數據結構和算法的掌握程度，以及解決實際問題的能力 。最小堆能夠快速找到即將到期的任務，這符合定時器的核心需求 。在實際應用中，比如在一個簡單的任務調度系統(tǒng)中，我們希望能夠盡快處理到期的任務，最小堆就可以很好地滿足這一需求 。而且，最小堆在插入和刪除任務時的時間復雜度也能夠滿足大多數場景的性能要求 。例如，在一個實時性要求不是特別高的應用中，即使插入和刪除操作需要一定的時間（O (log n)），也不會對系統(tǒng)的整體性能產生太大影響 。所以，基于最小堆的數據結構來實現(xiàn)定時器是一個比較合適的選擇。
（2）定義定時器類
#include <iostream>
#include <queue>
#include <functional>
#include <chrono>
class Timer {
public:
// 定義定時器任務結構體
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) {}
// 重載小于運算符，用于最小堆的比較
bool operator<(const TimerTask& other) const {
return expireTime > other.expireTime;
}
};
// 添加定時器任務
void addTask(std::chrono::milliseconds delay, std::function<void()> callback) {
auto task = std::make_shared<TimerTask>(delay, callback);
taskQueue.push(task);
}
// 檢查并執(zhí)行到期的任務
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:
// 最小堆，存儲定時器任務
std::priority_queue<std::shared_ptr<TimerTask>> taskQueue;
};在這段代碼中，我們定義了一個Timer類。首先，在類內部定義了一個TimerTask結構體，它包含了任務的延遲時間delay、到期時間expireTime以及回調函數callback 。expireTime通過當前時間加上延遲時間來計算得出。重載的小于運算符operator<用于最小堆的比較，使得堆中的任務按照到期時間從小到大排序 。
addTask成員函數用于添加定時器任務，它接收延遲時間和回調函數作為參數，創(chuàng)建一個TimerTask對象并將其加入到最小堆taskQueue中 。
checkTasks成員函數用于檢查并執(zhí)行到期的任務，它獲取當前時間now，然后在最小堆不為空且堆頂任務的到期時間小于等于當前時間時，取出堆頂任務并執(zhí)行其回調函數，之后將該任務從堆中移除 。通過這種方式，定時器能夠按照任務的到期時間順序依次執(zhí)行任務。
（3）實現(xiàn)定時器的核心功能函數
// 示例回調函數1
void task1() {
std::cout << "Task 1 executed." << std::endl;
}
// 示例回調函數2
void task2() {
std::cout << "Task 2 executed." << std::endl;
}
int main() {
Timer timer;
// 添加任務，3秒后執(zhí)行task1
timer.addTask(std::chrono::seconds(3), task1);
// 添加任務，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;
}在上述代碼中，我們定義了兩個示例回調函數task1和task2，分別用于在任務執(zhí)行時輸出相應的信息 。
在main函數中，創(chuàng)建了一個Timer對象timer。然后使用addTask函數添加了兩個任務：一個任務是延遲 3 秒后執(zhí)行task1，另一個任務是延遲 1 秒后執(zhí)行task2 。由于最小堆的特性，任務會按照到期時間從小到大排序，所以task2會先于task1執(zhí)行。
在一個無限循環(huán)中，不斷調用timer.checkTasks()來檢查并執(zhí)行到期的任務 。為了避免過度占用 CPU 資源，在每次循環(huán)中使用std::this_thread::sleep_for(std::chrono::milliseconds(100))使線程休眠 100 毫秒，模擬在執(zhí)行其他操作的同時，定期檢查定時器任務是否到期 。這樣，定時器就能夠按照設定的時間間隔準確地執(zhí)行各個任務，實現(xiàn)了定時器的核心功能。
（4）處理邊界情況和異常情況
在實現(xiàn)定時器的過程中，我們需要仔細考慮并妥善處理各種邊界情況和異常情況，以確保定時器的穩(wěn)定性和可靠性。
當定時器時間為0時，這是一種特殊的邊界情況。在我們之前實現(xiàn)的代碼中，雖然沒有對這種情況進行顯式處理，但從邏輯上來說，當添加一個延遲時間為0的任務時，按照當前的實現(xiàn)，它會立即被加入到任務隊列中，并且在checkTasks函數執(zhí)行時，只要任務隊列不為空且該任務位于堆頂（因為到期時間等于當前時間，會排在前面），就會立即執(zhí)行。然而，在實際應用中，可能需要根據具體需求對這種情況進行特殊處理。例如，如果不希望立即執(zhí)行延遲為0的任務，可以拋出一個異常，提示用戶這種設置不符合預期，或者將其視為無效輸入進行忽略 。
內存分配失敗也是一個需要關注的異常情況。在addTask函數中，我們使用std::make_shared來創(chuàng)建TimerTask對象，這涉及到內存分配操作。如果內存分配失敗，std::make_shared會拋出std::bad_alloc異常 。為了處理這個異常，我們可以在addTask函數中添加異常處理代碼，例如：
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;
// 可以根據需要進行更具體的處理，比如記錄日志、返回錯誤碼等
}
}這樣，當內存分配失敗時，程序會捕獲異常并輸出錯誤信息，避免因未處理的異常導致程序崩潰 。
并發(fā)訪問是一個較為復雜的問題。如果在多線程環(huán)境下使用定時器，多個線程同時訪問和修改任務隊列可能會導致數據不一致或競態(tài)條件 。為了解決這個問題，可以使用互斥鎖（std::mutex）來保護任務隊列的訪問。例如，修改Timer類如下：
class Timer {
public:
// 定義定時器任務結構體
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) {}
// 重載小于運算符，用于最小堆的比較
bool operator<(const TimerTask& other) const {
return expireTime > other.expireTime;
}
};
// 添加定時器任務
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í)行到期的任務
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:
// 最小堆，存儲定時器任務
std::priority_queue<std::shared_ptr<TimerTask>> taskQueue;
// 互斥鎖，用于保護任務隊列的并發(fā)訪問
std::mutex mutex_;
};在上述代碼中，我們在Timer類中添加了一個std::mutex成員變量mutex_，并在addTask和checkTasks函數中使用std::lock_guard<std::mutex>來自動管理鎖的生命周期 。std::lock_guard在構造時自動鎖定互斥鎖，在析構時自動解鎖，這樣可以確保在訪問任務隊列時，同一時間只有一個線程能夠進行操作，有效避免了并發(fā)訪問帶來的問題 。通過這些措施，我們能夠更好地處理定時器實現(xiàn)過程中的各種邊界和異常情況，提高程序的健壯性和穩(wěn)定性。
（5）代碼優(yōu)化與改進
在深入分析基于最小堆實現(xiàn)的定時器代碼性能時，我們從多個關鍵維度展開探討。從時間復雜度來看，當前代碼中添加任務的操作addTask，由于需要將任務插入到最小堆中，而最小堆的插入操作時間復雜度為 O (log n)，其中 n 是堆中元素的數量 。這意味著，隨著定時器任務數量的不斷增加，添加新任務所需的時間也會相應增長 。在一個處理大量網絡請求的服務器程序中，如果每個請求都關聯(lián)一個定時器任務，當請求量達到數千甚至數萬個時，每次添加新的定時器任務都可能需要耗費一定的時間，這對于系統(tǒng)的實時性和響應速度會產生一定的影響 。
檢查并執(zhí)行到期任務的checkTasks函數，雖然在理想情況下，當堆頂任務到期時，執(zhí)行和移除操作的時間復雜度為 O (1)，但在實際情況中，由于需要遍歷堆來查找所有到期的任務，其時間復雜度可能會達到 O (n) 。當存在大量任務且到期時間較為集中時，checkTasks函數可能需要花費較長時間來處理所有到期任務，導致系統(tǒng)在這段時間內無法及時響應其他操作 。
在空間復雜度方面，代碼使用std::priority_queue來存儲定時器任務，其空間復雜度為 O (n)，n 為任務數量 。隨著任務數量的不斷增多，內存占用也會線性增加 。如果在一個資源受限的嵌入式系統(tǒng)中使用該定時器，當任務數量過多時，可能會導致內存不足，影響系統(tǒng)的正常運行 。
內存使用方面，std::shared_ptr用于管理TimerTask對象的生命周期，雖然這種智能指針的使用方式能夠有效避免內存泄漏，但在頻繁創(chuàng)建和銷毀TimerTask對象時，會增加內存分配和釋放的開銷 。在一個高并發(fā)的場景中，大量定時器任務被頻繁創(chuàng)建和銷毀，這可能會導致內存分配器的壓力增大，進而影響系統(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; // 新增任務ID，用于快速定位和刪除任務
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來快速定位任務，加速刪除操作
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;
// 標記任務為無效，而不是直接從堆中刪除，避免堆調整的開銷
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結構體中新增了id成員，用于唯一標識每個任務 。這為后續(xù)的快速定位和刪除任務提供了基礎 。
引入了std::unordered_map<int, std::shared_ptr<TimerTask>> taskMap，它可以根據任務 ID 快速定位到對應的TimerTask對象，將刪除任務的時間復雜度從原來的 O (n) 降低到 O (1) 。在addTask函數中，不僅將任務添加到最小堆taskQueue中，還同時將任務存儲到taskMap中，以便后續(xù)快速查找和操作 。
在cancelTask函數中，通過taskMap查找并刪除任務，并且采用標記任務無效（將回調函數設置為空函數）的方式，避免了直接從最小堆中刪除任務時復雜的堆調整操作，進一步提高了刪除任務的效率 。
在checkTasks函數中，增加了對任務回調函數是否為空的檢查，確保只有有效的任務才會被執(zhí)行，避免執(zhí)行已被取消的任務 。通過這些優(yōu)化措施，優(yōu)化后的代碼在性能和效率上有了顯著提升，能夠更好地滿足實際應用中對定時器的高效管理需求 。
