来自：腾讯百度C++二面：手撕定时器_哔哩哔哩_bilibili
腾讯、网易、百度C++：
手撕定时器
相关概念参考：
1. 什么是定时器
定时器（Timer）是用来管理大量延时任务（异步执行，一般用回调函数）的模块，它会触发执行最近将要超时的任务。
2. 需要考虑的问题吧
如何选择数据结构
需要满足以下要求：
- 触发时刻作为
key，任务作为val - 能快速找到最近要超时的任务
- 触发后要删除该任务且支持随时删除任务
- 允许相同时刻触发任务
一些框架中使用的数据结构是最小堆、红黑树和时间轮。
这里我们可以使用STL中的
multimap（基于红黑树）- 触发时刻作为
设计“任务”
使用函数对象
如何触发
- 使用
epoll_wait中的第四个参数 —— 超时参数 timerfd有三个接口，记忆难度较大，可以不考虑
- 使用
3. 接口设计
- 添加一个延时任务
- 删除一个延时任务
- 检测触发延时任务
4. 完整代码
timer.h
#include <sys/epoll.h>
#include <functional>
#include <chrono>
#include <map>
#include <memory>
#include <iostream>
class Timer;
class TimerTask {
friend class Timer;
public:
using Callback = std::function<void(TimerTask* task)>;
TimerTask(uint64_t addtime, uint64_t exectime, Callback func) {
m_addtime = addtime;
m_exectime = exectime;
m_func = std::move(func);
}
uint64_t AddTime() const {
return m_addtime;
}
uint64_t ExecTime() const {
return m_exectime;
}
private:
void run() {
m_func(this);
}
uint64_t m_addtime;
uint64_t m_exectime;
Callback m_func;
};
class Timer {
using Millisecond = std::chrono::milliseconds;
public:
static uint64_t GetTick() {
// 获取系统启动到现在时刻经过的时间
auto sc = std::chrono::time_point_cast<Millisecond>(std::chrono::steady_clock::now());
auto temp = std::chrono::duration_cast<Millisecond>(sc.time_since_epoch());
return temp.count();
}
// 添加定时器,
std::shared_ptr<TimerTask> AddTimeout(uint64_t offset, TimerTask::Callback func) {
uint64_t now = GetTick();
uint64_t exectime = now + offset;
auto task = std::make_shared<TimerTask>(now, exectime, std::move(func));
if (m_timeouts.empty() || exectime >= m_timeouts.crbegin()->first) {
auto ele = m_timeouts.emplace_hint(m_timeouts.end(), exectime, task);
return ele->second;
}
auto ele = m_timeouts.emplace(exectime, task);
return ele->second;
}
// 删除定时器，由于存在多个同时触发的定时器，所以需要在满足触发时间的任务重寻找需要删除的定时器
void DelTimeout(std::shared_ptr<TimerTask> task) {
auto range = m_timeouts.equal_range(task->ExecTime());
for (auto it = range.first; it != range.second;) {
if (it->second == task) {
it = m_timeouts.erase(it);
} else {
++it;
}
}
}
// 更新定时器
void Update(uint64_t now) {
auto it = m_timeouts.begin();
while (it != m_timeouts.end() && it->first <= now) {
it->second->run();
// delete it->second;
it = m_timeouts.erase(it);
}
}
// 获取最近的超时时间
int WaitTime() {
auto it = m_timeouts.begin();
if (it == m_timeouts.end()) {
return -1;
}
int diss = it->first - GetTick();
return diss > 0 ? diss : 0;
}
private:
std::multimap<uint64_t, std::shared_ptr<TimerTask>> m_timeouts;
};
example.cpp
#include "timer.h"
using namespace std;
int main() {
int epfd = epoll_create(1);
unique_ptr<Timer> timer = make_unique<Timer>();
int i = 0;
timer->AddTimeout(1000, [&](TimerTask* task) {
cout << Timer::GetTick() << " addtime:" << task->AddTime() << " revoked times:" << ++i << endl;
});
timer->AddTimeout(2000, [&](TimerTask* task) {
cout << Timer::GetTick() << " addtime:" << task->AddTime() << " revoked times:" << ++i << endl;
});
timer->AddTimeout(3000, [&](TimerTask* task) {
cout << Timer::GetTick() << " addtime:" << task->AddTime() << " revoked times:" << ++i << endl;
});
auto task = timer->AddTimeout(2100, [&](TimerTask* task) {
cout << Timer::GetTick() << " addtime:" << task->AddTime() << " revoked times:" << ++i << endl;
});
timer->DelTimeout(task);
cout << "now time:" << Timer::GetTick() << endl;
epoll_event ev[64] = {};
while(true) {
cout << "waittime:" << timer->WaitTime() << endl;
int n = epoll_wait(epfd, ev, 64, timer->WaitTime());
time_t now = Timer::GetTick();
for (int i = 0; i < n; i++) {
/**/
}
timer->Update(now);
}
return 0;
}
5. 性能优化
针对 不同功能或不同对象 设置定时器
针对多线程进行优化：一个时间线程一个定时器 或者 单独时间轮线程
针对有规律的定时任务（有大量相同时间间隔的延时任务）
采用
emplace_hint接口，如timer.h中的52 - 55emplace_hint函数可以在指定的迭代器后面插入元素，它可以提高插入效率，因为它减少了元素的移动和复制操作。通过提供插入位置的提示，emplace_hint可以尽可能地减少容器的重新分配和元素的移动，特别是在有序容器中插入元素时，这种优化尤为明显。