带你手撕面试题——定时器方案：红黑树版
目录
一：前言
二：手撕面试题--set容器--timerfd驱动
1、定时任务存储的结构体
2、Timer类中的私有成员
3、获得当前系统时间
4、任务结点的添加
5、删除任务结点
6、处理超时任务
7、更新时间
8、main函数中的例子
三、set容器--使用epoll_wait的第四个参数超时
一：前言
我之前的文章有过详细的讲解为什么使用红黑树等，讲了很多的理论知识，大家可以先把理论看懂，然后再来看手撕面试题。点我跳转！
二：手撕面试题--set容器--timerfd驱动
1、定时任务存储的结构体
首先定时任务肯定需要时间，由于我们使用的是set容器，不可以插入相同的key值，那么对于同一时间的任务怎么处理呢？我们选择id来区分，我们让id自增长，这样保证id不会重复就可以。
那为什么写了两个结构体呢，因为我们存储在set容器中，其底层是红黑树，当我们插入新的结点的时候，我们需要平衡红黑树，会发生树的旋转操作，旋转操作其实就是结点的复制拷贝，当任务很多的时候，会发生大量的拷贝，降低性能占用内存。因此我们通过使用继承的操作，将子类添加到红黑树中，这样就避免了大量的内存占用。具体去看我的文章哦。
//基类
struct TimerNodeBase
{
time_t expire; //时间
uint64_t id; //id号，为了区分同一时间插入的任务
};
struct TimerNode : public TimerNodeBase
{
using CallBack = function<void(const TimerNode & timer)>; //创造一个需要传入自己的回调函数
CallBack func;
TimerNode (uint64_t id,time_t expire,CallBack func1):func(func1)
{
this->id = id;
this->expire = expire;
}
};2、Timer类中的私有成员
这里使用了set容器，其中用子类结点当作key值，使用 less<> 作为结点之间判断的条件。但是我们是使用的结点来当作key值，因此我们需要自己写判断条件。
其中 inline 关键字的作用:用于函数声明或定义中，其作用是将函数指定为内联函数。内联函数的主要目的是解决一些频繁调用的函数大量消耗栈空间（栈内存）的问题，通过在编译时将函数体的代码直接嵌入到每一个调用点处，从而避免函数调用的开销，包括参数传递、栈帧创建与销毁等成本，以提升程序的执行效率。替代宏定义。
private:
static uint64_t id; //在这里使用static是为了在类中进行共享，在类外进行初始化，且只有一次。
//这意味着无论创建了多少个类的实例，都只有一个static成员变量的副本。这对于需要跟踪类级别信息（如类的实例数量、类的静态配置等）的情况非常有用。
set<TimerNode,less<>> timeouts;
static inline uint64_t GETID() //这里加入static，只能访问静态成员
{
return 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;
}3、获得当前系统时间
static inline time_t GET_TICK() //返回系统的时间
{
return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now().time_since_epoch()).count();
}4、任务结点的添加
首先需要传入时间以及回调函数，这个时间是指多少秒后触发的意思。因此我们需要自己去计算这个任务位于整天中的第多少秒。
获得了时间，那么我们就可以通过这个时间去判断这个结点的位置，此时我们需要思考一下，我们都是添加的什么任务结点？是我们需要定时的普通任务呢还是像心跳包一样的规律性任务呢？这两种任务有什么区别？
首先举个例子，如果当前时间是4秒，我要插入第8秒的时间，到了第5秒，我要插入第7秒的时间。我们肯定会碰到这样的插入任务，这样就可以正常插入。但是如果是心跳包这种呢，一直每隔10秒插入一次，我们会发现，当只插入心跳包的时候，只插入到最后，但是红黑树每次都是从中间查找，因此会浪费时间，如果直接插入最后那么时间复杂度不久成O(1)了吗。
//将任务添加到set容器中去
TimerNodeBase TimerAdd(int msg,TimerNode::CallBack func) //要执行的时间，以及插入的函数
{
time_t time = GET_TICK() + msg;
//这里是进行了一个小优化,当一直插入的最后一个位置，那么咱们就直接找到那个位置，直接插入，不用从中间进行二分查找，直接将时间变成O(1)
if(timeouts.empty() || time <= timeouts.rbegin()->expire)
{
auto ptr = timeouts.emplace(GETID(),time,std::move(func));
return static_cast<TimerNodeBase>(*ptr.first); //在编译时进行的显示转换，这里是向上转换，是安全的。
}
auto ptrt = timeouts.emplace_hint(timeouts.crbegin().base(),GETID(),time,std::move(func));
return static_cast<TimerNodeBase>(*ptrt);
}5、删除任务结点
void DEL(TimerNodeBase & timernode)
{
auto ptr = timeouts.find(timernode);
if(ptr != timeouts.end())
{
timeouts.erase(ptr);
}
}6、处理超时任务
void Handle(time_t now)
{
auto ptr = timeouts.begin();
while(ptr != timeouts.end() && ptr->expire<=now) //传入时间之后，进行判断，小于这个时间的全部进行执行
{
ptr->func(*ptr );
ptr = timeouts.erase(ptr); //将这个删除之后会赋值一下下一个迭代器
}
}7、更新时间
单独看这个函数可能看不懂，只能看懂它将容器中第一个元素的时间给复制了一下，到了一个结构体中，而且这个结构体走了一下这个timerfd_settime函数，其中还包含了epoll的fd。看不懂没事，下面在main中的例子讲解。
virtual void UpdateTimefd(const int fd)
{
struct timespec abstime;
auto iter = timeouts.begin();
if(iter !=timeouts.end()) //如果在把timefd添加到epoll中之前去的时候，向定时器中添加了一些定时任务的话，走这里，初始化判断的时间
{
abstime.tv_sec = iter->expire /1000; //将秒和微妙进行添加
abstime.tv_nsec = (iter->expire % 1000) * 1000000;
}
else //如果还没添加定时任务
{
abstime.tv_sec = 0;
abstime.tv_nsec = 0;
}
struct itimerspec its =
{
.it_interval = {},
.it_value = abstime
};
timerfd_settime(fd,TFD_TIMER_ABSTIME,&its,nullptr); //设置定时器fd的时间，每次要执行任务之前要判断fd的时间。
}8、main函数中的例子
首先就是咱们的epollfd，然后通过timerfd_create创建一个定时器的fd，添加到epoll中，然后创建Timer定时器，并添加一些任务。到后面的while循环中去。
到这个时候，我们的timefd和Timer定时器类，并没有任何的交集，此时通过updatetimefd将timefd传入到Timer中去，并且给timefd设置了超时时间，也就是容器中首个位置的时间。这样这个timefd就可以自动超时了。
通过wait函数等待发生事件，无论是网络事件触发，还是定时器的超时触发，我们都进行检查定时器Timer类中是否有任务超时。
cout <<"1"<<endl;
int epfd = epoll_create(1);
int timefd = timerfd_create(1,0);
epoll_event ev ={.events = EPOLLIN | EPOLLET};
epoll_ctl(epfd,EPOLL_CTL_ADD,timefd,&ev);
//测试用例
unique_ptr<Timer> timer = make_unique<Timer>();
int i = 0;
timer->TimerAdd(1000, [&](const TimerNode &node) {
cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;
});
timer->TimerAdd(1000, [&](const TimerNode &node) {
cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;
});
timer->TimerAdd(3000, [&](const TimerNode &node) {
cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;
});
auto node = timer->TimerAdd(2100, [&](const TimerNode &node) {
cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;
});
timer->DEL(node);
cout << "now time:" << Timer::GET_TICK() << endl;
//将定时器添加完成之后，就进入等待环节
epoll_event evs[64]={0};
while(1)
{
timer->UpdateTimefd(timefd); //每次等待之前都要将定时器中的代码进行初始化操作，都要复制成容器中第一个的时间，
int n = epoll_wait(epfd,evs,64,-1); //设置永远不会超时，当有事件返回，则触发下面判断时间的操作。
for(int i=0;i<n;i++)
{
//这里就是正常的接收网络请求的代码
}
timer->Handle(timer->GET_TICK()); //传入当前时间，将时间之前的任务全部执行。
}
epoll_ctl(epfd, EPOLL_CTL_DEL, timefd, &ev);
close(timefd);
close(epfd);
return 0;三、set容器--使用epoll_wait的第四个参数超时
首先我们要知道第四个参数是干什么的，是用来自动超时的，我们可以思考一下怎么将咱们的超时任务连接起来。当我们插入很多任务之后，怎么样才能让他们自动超时呢？
如果我们将每个任务的超时时间添加到这个epoll_wait的参数中去，那么每次超时是不是就成了第一个任务超时的时间了呢。
time_t Timertosleep()
{
auto iter = timeouts.begin();
if(iter == timeouts.end())
{
return -1; //这里也就是说当没有定时任务的时候
}
time_t diss = iter->expire - GET_TICK();//每次等待超时的时间
return diss >0 ? diss :0;
}每次超时之后处理任务完成，都要重新设置epoll_wait的超时时间，这样就自动超时了。
epoll_event ev[64] = {0};
while (true) {
int n = epoll_wait(epfd, ev, 64, timer->Timertosleep());
time_t now = Timer::GET_TICK();
for (int i = 0; i < n; i++) {
/**/
}
/* 处理定时事件*/
timer->Handle(now);
}本片讲解完毕啦！
https://xxetb.xetslk.com/s/2D96kH