时间轮定时器

优点：可保证每次执行定时器任务都是O（1）复杂度，在定时器任务密集的情况下，性能优势非常明显。
缺点：内存占用较大，当定时器使用不频繁，处理时间跨度很大的时候，效率低下。

C++实现：

//  timer.h
#pragma once

#include <array>
#include <queue>
#include <deque>
#include <tuple>
#include <memory>
#include <string>
#include <chrono>
#include <vector>
#include <utility>
#include <optional>
#include <algorithm>
#include <functional>

template <int Day>
class Timer {
public:
    using NormalTime = std::tuple<std::uint8_t, std::uint8_t, std::uint8_t, std::uint8_t, std::uint16_t>;

    static NormalTime TimeNormal(std::uint64_t time)
    {
        auto d = (std::uint8_t)(time / 86400000); time -= d * 86400000;
        auto h = (std::uint8_t)(time / 3600000); time -= h * 3600000;
        auto m = (std::uint8_t)(time / 60000); time -= m * 60000;
        auto s = (std::uint8_t)(time / 1000); time -= s * 1000;
        auto ms = (std::uint16_t)time;
        return { d, h, m, s, ms };
    }

    static std::uint64_t TimeNormalNeg(const NormalTime & normal)
    {
        return std::get<0>(normal) * 86400000
            + std::get<1>(normal) * 3600000
            + std::get<2>(normal) * 60000
            + std::get<3>(normal) * 1000
            + std::get<4>(normal);
    }

private:
    struct Task {
        Task()
        { }
        Task(const std::size_t _id,
            const std::uint64_t & _time,
            const std::function<void()> & _func) : id(_id), time(_time), func(_func), normal(TimeNormal(_time))
        { }
        bool operator==(const Task & other) const
        {
            return other.id == id;
        }
        bool operator==(std::size_t id) const
        {
            return this->id == id;
        }
        std::function<void()> func;
        std::uint64_t time;
        NormalTime normal;
        std::size_t id;
    };

    struct Slot {
        std::array<std::vector<Task>, Day> day;
        std::array<std::vector<Task>, 24> hour;
        std::array<std::vector<Task>, 60> minute;
        std::array<std::vector<Task>, 60> second;
        std::array<std::vector<Task>, 1000> millis;
    };

public:
    Timer(std::uint64_t time)
        : _slot(new Slot())
        , _startTime(time)
        , _lastTime(0)
    { }

    ~Timer()
    { }

    void Set(std::size_t id, std::uint64_t time, const std::function<void()> & func)
    {
        InsertTo<0>(Task(id, time - _startTime, func));
    }

    void Timer::Del(size_t id)
    {
        RemoveFrom(_slot->day.begin(), _slot->day.end(), id)
            || RemoveFrom(_slot->hour.begin(), _slot->hour.end(), id)
            || RemoveFrom(_slot->minute.begin(), _slot->minute.end(), id)
            || RemoveFrom(_slot->second.begin(), _slot->second.end(), id)
            || RemoveFrom(_slot->millis.begin(), _slot->millis.end(), id);
    }

    void Update(std::uint64_t time)
    {
        if (time > _lastTime + _startTime)
        {
            do {
                auto[fromd1, fromh1, fromm1, froms1, fromms1] = TimeNormal(_lastTime);
                _lastTime += std::min(time - _startTime - _lastTime, 16ULL);
                auto[fromd2, fromh2, fromm2, froms2, fromms2] = TimeNormal(_lastTime);
                Update<0, Day>(_slot->day.begin(), fromd1, fromd2);
                Update<1, 24>(_slot->hour.begin(), fromh1, fromh2);
                Update<2, 60>(_slot->minute.begin(), fromm1, fromm2);
                Update<3, 60>(_slot->second.begin(), froms1, froms2);
                Update<4, 1000>(_slot->millis.begin(), fromms1, fromms2);
            } while (_lastTime + _startTime != time);
        }
    }

private:
    template <class Iter>
    bool RemoveFrom(Iter first, Iter last, size_t id)
    {
        for (; first != last; ++first)
        {
            auto iter = std::find_if(first->begin(), first->end(),
                [id](const Task & task) { return task == id; });
            if (iter != first->end())
            {
                first->erase(iter);
                return true;
            }
        }
        return false;
    }

    template <int I, int N, class Iter>
    void Update(Iter iter, std::uint64_t first, std::uint64_t last)
    {
        if (first != last)
        {
            for (first = (first + 1) % N; first != last; first = (first + 1) % N)
            {
                Update<I>(*std::next(iter, (std::ptrdiff_t)first));
            }
            Update<I>(*std::next(iter, (std::ptrdiff_t)first));
        }
    }

    template <int N>
    void Update(std::vector<Task> & tasks)
    {
        std::for_each(tasks.begin(), tasks.end(),
            std::bind(&Timer::InsertTo<N + 1>, this, std::placeholders::_1));
        tasks.clear();
    }

    template <int N>
    void InsertTo(const Task & task)
    {
        if constexpr (N == 5)
        {
            std::invoke(task.func);
        }
        else if (std::get<N>(task.normal) == 0)
        {
            InsertTo<N + 1>(task);
        }
        else if (std::get<N>(task.normal) != 0)
        {
            if constexpr (N == 0)
            {
                _slot->day.at(std::get<0>(task.normal)).emplace_back(task);
            }
            else if constexpr (N == 1)
            {
                _slot->hour.at(std::get<1>(task.normal)).emplace_back(task);
            }
            else if constexpr (N == 2)
            {
                _slot->minute.at(std::get<2>(task.normal)).emplace_back(task);
            }
            else if constexpr (N == 3)
            {
                _slot->second.at(std::get<3>(task.normal)).emplace_back(task);
            }
            else if constexpr (N == 4)
            {
                _slot->millis.at(std::get<4>(task.normal)).emplace_back(task);
            }
        }
    }

private:
    uint64_t _lastTime;
    uint64_t _startTime;
    std::unique_ptr<Slot> _slot;
};

//  main.cpp
#include "timer/timer.h"
#include <iostream>
#include <thread>

std::int64_t NowTime(std::int64_t time)
{
    return std::chrono::time_point_cast<std::chrono::milliseconds>(std::chrono::system_clock::now()).time_since_epoch().count() + time;
}

int main()
{
    auto now = NowTime(0);
    Timer<31> timer(now);
    timer.Set(0, NowTime(5000), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(100), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(0), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(33), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(2333), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(2007), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(3600), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(60000), [now]() { std::cout << NowTime(0) - now << std::endl; });
    timer.Set(0, NowTime(61050), [now]() { std::cout << NowTime(0) - now << std::endl; });
    while (true)
    {
        now = NowTime(0);
        timer.Update(now);
    }
    return 0;
}

linux内核使用的是时间轮定时器，因为内核必须考虑定时器任务密集的情况，同时，内核很容易保证时间跨度是固定的。其他场合下，用堆来实现定时器比较合适。