定时器的实现方案：红黑树、最小堆与时间轮

①.时间轮定义：

按时间指针移动触发任务的机制。

②.时间轮特征：

适用于多线程环境，优势明显。

③.时间轮操作：

添加任务、删除任务、移动时间指针。

④.时间轮在定时器中的应用：

处理海量定时任务。

时间轮本质上是一个环形的数组，每个数组元素代表一个时间间隔，例如1秒、1分、1时等。时间轮通过指针的旋转来管理和执行定时任务，每个槽通常使用双向链表来存储该时间点需要执行的任务，以便高效地添加、删除和遍历任务。

二.基于红黑树容器set实现一个定时器集合（代码）

#include <sys/epoll.h>
#include <sys/timerfd.h>
#include <time.h> // for timespec itimerspec
#include <unistd.h> // for close#include <functional>
#include <chrono>
#include <set>
#include <memory>
#include <iostream>using namespace std;//(基类)父类
struct TimerNodeBase {time_t expire;uint64_t id; 
};//(派生类)子类
struct TimerNode : public TimerNodeBase {using Callback = std::function<void(const TimerNode &node)>;// 定义一个类型别名 Callback，表示一个接收 const TimerNode& 参数并返回 void 的函数类型Callback func;// 成员变量：一个 Callback 类型的函数对象// 构造函数：接收三个参数，并初始化 TimerNode 的成员TimerNode(int64_t id, time_t expire, Callback func) : func(func) {this->expire = expire;this->id = id;}};bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) {if (lhd.expire < rhd.expire) {return true;} else if (lhd.expire > rhd.expire) {return false;} else return lhd.id < rhd.id;
}class Timer {
public:static inline time_t GetTick() {return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now().time_since_epoch()).count();}//返回当前时间(毫秒级) TimerNodeBase AddTimer(int msec, TimerNode::Callback func) {time_t expire = GetTick() + msec;//它首先计算定时器的过期时间 expire，即当前时间加上 msec。if (timeouts.empty() || expire <= timeouts.crbegin()->expire) {//如果 timeouts 集合为空，或者新定时器的过期时间早于或等于当前最迟的定时器，它就将定时器添加到集合中。auto pairs = timeouts.emplace(GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*pairs.first);}auto ele = timeouts.emplace_hint(timeouts.crbegin().base(), GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*ele);}void DelTimer(TimerNodeBase &node) {auto iter = timeouts.find(node);if (iter != timeouts.end())timeouts.erase(iter);}//处理到期的定时器void HandleTimer(time_t now) {auto iter = timeouts.begin();while (iter != timeouts.end() && iter->expire <= now) {iter->func(*iter);iter = timeouts.erase(iter);}}public:virtual void UpdateTimerfd(const int fd) {struct timespec abstime;// 定义一个 timespec 结构体，用来保存定时器的绝对时间auto iter = timeouts.begin(); // 获取当前最早的定时器（即过期时间最小的定时器）if (iter != timeouts.end()) {    // 如果 timeouts 集合中有定时器abstime.tv_sec = iter->expire / 1000;// 过期时间的秒部分abstime.tv_nsec = (iter->expire % 1000) * 1000000;// 过期时间的毫秒部分转为纳秒} else {// 如果没有定时器，设置 abstime 为 0，表示没有定时器触发abstime.tv_sec = 0;abstime.tv_nsec = 0;}// 设置 itimerspec 结构体，指定定时器的触发时间struct itimerspec its = {.it_interval = {},// 设定定时器不重复触发，因此它的间隔时间设为 0.it_value = abstime // 设置定时器触发的绝对时间};timerfd_settime(fd, TFD_TIMER_ABSTIME, &its, nullptr);// 使用 timerfd_settime 来设置定时器文件描述符的时间// fd: 定时器文件描述符// TFD_TIMER_ABSTIME: 使用绝对时间而不是相对时间// &its: 指向 itimerspec 结构体的指针，定义定时器的触发时间和间隔时间}private:static inline uint64_t GenID() {return gid++;}static uint64_t gid; set<TimerNode, std::less<>> timeouts;
};
uint64_t Timer::gid = 0;int main() {int epfd = epoll_create(1);int timerfd = timerfd_create(CLOCK_MONOTONIC, 0);//timerfd 是 Linux 下的一种定时器机制，用于定时事件的通知。它通过文件描述符提供与定时器相关的操作。struct epoll_event ev = {.events=EPOLLIN | EPOLLET};epoll_ctl(epfd, EPOLL_CTL_ADD, timerfd, &ev);unique_ptr<Timer> timer = make_unique<Timer>();int i = 0;timer->AddTimer(1000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->AddTimer(1000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->AddTimer(3000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});auto node = timer->AddTimer(2100, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->DelTimer(node);cout << "now time:" << Timer::GetTick() << endl;struct epoll_event evs[64] = {0};while (true) {timer->UpdateTimerfd(timerfd);int n = epoll_wait(epfd, evs, 64, -1);time_t now = Timer::GetTick();for (int i = 0; i < n; i++) {// for network event handle}timer->HandleTimer(now);//执行完事件后进行清理}epoll_ctl(epfd, EPOLL_CTL_DEL, timerfd, &ev);close(timerfd);close(epfd);return 0;
}

①基类 TimerNodeBase

time_t expire :定时器的过期时间 = 当前时间+设定时间

id:定时器模块的id

②子类 TimerNode 以public的方式继承基类

在原本基类里面增加唠嗑一个回调函数Callbaakc func

③小于号运算符重载（应用于红黑树实现从小到大排序）

④定义一个Timer类管理定时器的接口

GenID:获取id编号的私有接口

set<TimerNode,std::less<>>timeouts:节点类型为TimerNode 中序遍历按从小到大排序的一颗红黑树

⑤获取当前（毫秒级）时间的成员函数

⑥增加定时器模块的成员函数

如果 timeouts 集合为空，或者新定时器的过期时间早于或等于当前最迟的定时器，它就将定时器添加到集合中。

如果新定时器的过期时间一直大于当前最迟的定时器 则一直把它添加在红黑树的最右边