High-Concurrency C++ Timer Implementations: Red-Black Tree, Min-Heap, and Time Wheel

In modern high‑traffic systems such as e‑commerce, online gaming, and financial services, handling massive concurrent requests demands precise and efficient timers; C++ timers act as the time‑keeper that schedules tasks, enforces timeouts, and frees idle connections.

Red‑Black Tree Implementation – A self‑balancing binary search tree provides O(log n) insertion, deletion, and lookup, making it suitable for ordering timer tasks by expiration time. Each timer task is stored as a node with an expiration timestamp and a callback function. The smallest key (leftmost node) represents the next task to fire. Example code:

#include <iostream>
#include <set>
#include <functional>
#include <chrono>

struct TimerNode {
    std::chrono::system_clock::time_point expire;
    std::function<void()> callback;
    bool operator<(const TimerNode& other) const { return expire < other.expire; }
};

class Timer {
public:
    void addTimer(int delay, std::function<void()> cb) {
        auto expireTime = std::chrono::system_clock::now() + std::chrono::seconds(delay);
        timerSet.insert({expireTime, cb});
    }
    void checkAndExecute() {
        auto now = std::chrono::system_clock::now();
        while (!timerSet.empty() && timerSet.begin()->expire <= now) {
            timerSet.begin()->callback();
            timerSet.erase(timerSet.begin());
        }
    }
private:
    std::set<TimerNode> timerSet; // std::set uses a red‑black tree internally
};

Usage:

int main() {
    Timer timer;
    timer.addTimer(3, [](){ std::cout << "Task 1 executed" << std::endl; });
    timer.addTimer(5, [](){ std::cout << "Task 2 executed" << std::endl; });
    for (int i = 0; i < 10; ++i) {
        timer.checkAndExecute();
        std::this_thread::sleep_for(std::chrono::seconds(1));
    }
    return 0;
}

Min‑Heap Implementation – A binary heap keeps the smallest expiration time at the root, offering O(1) access to the next timer and O(log n) for insertion and removal. Tasks are stored in a vector, and heap operations (sift‑up/sift‑down) maintain the ordering.

#include <iostream>
#include <vector>
#include <functional>
#include <chrono>

struct TimerTask {
    std::chrono::system_clock::time_point expire;
    std::function<void()> callback;
    bool operator<(const TimerTask& other) const { return expire < other.expire; }
};

class MinHeapTimer {
public:
    void addTask(int delay, std::function<void()> cb) {
        auto expireTime = std::chrono::system_clock::now() + std::chrono::seconds(delay);
        heap.push_back({expireTime, cb});
        siftUp(heap.size() - 1);
    }
    void checkAndExecute() {
        auto now = std::chrono::system_clock::now();
        while (!heap.empty() && heap[0].expire <= now) {
            heap[0].callback();
            removeTop();
        }
    }
private:
    std::vector<TimerTask> heap;
    void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] < heap[i]) break;
            std::swap(heap[p], heap[i]);
            i = p;
        }
    }
    void siftDown(int i) {
        int n = heap.size();
        while (true) {
            int l = 2*i + 1, r = 2*i + 2, smallest = i;
            if (l < n && heap[l] < heap[smallest]) smallest = l;
            if (r < n && heap[r] < heap[smallest]) smallest = r;
            if (smallest == i) break;
            std::swap(heap[i], heap[smallest]);
            i = smallest;
        }
    }
    void removeTop() {
        heap[0] = heap.back();
        heap.pop_back();
        siftDown(0);
    }
};

Usage:

int main() {
    MinHeapTimer timer;
    timer.addTask(2, [](){ std::cout << "Task 1 executed" << std::endl; });
    timer.addTask(4, [](){ std::cout << "Task 2 executed" << std::endl; });
    for (int i = 0; i < 10; ++i) {
        timer.checkAndExecute();
        std::this_thread::sleep_for(std::chrono::seconds(1));
    }
    return 0;
}

Time‑Wheel Implementation – Inspired by a clock, a time wheel divides time into a fixed number of slots; each slot holds tasks whose expiration falls into that interval. The wheel pointer advances at a constant tick, triggering all tasks in the current slot. Insertion and removal are O(1), making it ideal for massive numbers of timers with coarse granularity.

#include <iostream>
#include <vector>
#include <list>
#include <functional>
#include <chrono>

struct TimerTask {
    std::function<void()> callback;
    std::chrono::system_clock::time_point expire;
};

class TimeWheel {
public:
    TimeWheel(int slotCount, int interval) : slotCount(slotCount), interval(interval) {
        slots.resize(slotCount);
        currentTime = std::chrono::system_clock::now();
    }
    void addTask(int delay, std::function<void()> cb) {
        auto expireTime = std::chrono::system_clock::now() + std::chrono::milliseconds(delay);
        int slotIdx = getSlotIndex(delay);
        slots[slotIdx].push_back({cb, expireTime});
    }
    void advanceTime() {
        currentTime = std::chrono::system_clock::now();
        int curSlot = getSlotIndex(0);
        auto &tasks = slots[curSlot];
        for (auto it = tasks.begin(); it != tasks.end();) {
            if (it->expire <= currentTime) {
                it->callback();
                it = tasks.erase(it);
            } else {
                ++it;
            }
        }
    }
private:
    int getSlotIndex(int delay) {
        auto totalMs = std::chrono::duration_cast
(
            (std::chrono::system_clock::now() + std::chrono::milliseconds(delay)) - currentTime).count();
        return totalMs % slotCount;
    }
    int slotCount;
    int interval; // milliseconds per slot
    std::vector<std::list<TimerTask>> slots;
    std::chrono::system_clock::time_point currentTime;
};

Usage:

int main() {
    TimeWheel wheel(100, 100); // 100 slots, 100 ms each
    wheel.addTask(500, [](){ std::cout << "Task executed" << std::endl; });
    for (int i = 0; i < 10; ++i) {
        wheel.advanceTime();
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
    return 0;
}

Finally, the article compares the three approaches: red‑black trees offer balanced O(log n) operations and fine‑grained precision; min‑heaps provide O(1) access to the next timer with similar logarithmic updates; time wheels achieve O(1) insertion/removal and excel when handling very large numbers of timers at the cost of limited granularity and higher memory usage for many slots. Choosing the right implementation depends on task volume, required precision, and implementation complexity.