读写锁，TTL过期，O(log(N))时间复杂度的cache实现

class Solution {
public:
    void put(const std::string& key, const std::string& value, int ttl) {
        // 清理过期：内部自己拿写锁，调用前不能持有任何锁
        remove_expired_keys();

        std::shared_lock<std::shared_mutex> rlock(m_rw_mtx);
        auto it_store = m_store_map.find(key);
        if (it_store != m_store_map.end()) {
            // 拿到旧数据
            const auto old_expire = it_store->second.expire_time;
            rlock.unlock(); // 释放读锁，准备写操作

            std::unique_lock<std::shared_mutex> wlock(m_rw_mtx);
            // 删除旧ttl映射
            erase_from_ttl_map(key, old_expire);

            // 设置新值、新过期时间
            auto new_expire = get_expire_time(ttl);
            m_store_map[key] = StoreData{value, new_expire};
            insert_into_ttl_map(key, new_expire);
            return;
        }

        // key不存在，插入新kv
        rlock.unlock();
        std::unique_lock<std::shared_mutex> wlock(m_rw_mtx);
        auto new_expire = get_expire_time(ttl);
        m_store_map[key] = StoreData{value, new_expire};
        insert_into_ttl_map(key, new_expire);
    }

    std::unique_ptr<std::string> get(const std::string& key) {
        remove_expired_keys();

        std::shared_lock<std::shared_mutex> rlock(m_rw_mtx);
        auto it = m_store_map.find(key);
        if (it != m_store_map.end()) {
            return std::make_unique<std::string>(it->second.value);
        }
        return nullptr;
    }

    size_t size() {
        remove_expired_keys();

        std::shared_lock<std::shared_mutex> rlock(m_rw_mtx);
        return m_store_map.size();
    }

private:
    using Tp = std::chrono::steady_clock::time_point;

    struct StoreData {
        std::string value;
        Tp expire_time;
    };

    std::unordered_map<std::string, StoreData> m_store_map;
    // key:过期时间点，value:该时刻过期的key集合
    std::map<Tp, std::set<std::string>> m_ttl_map;
    std::shared_mutex m_rw_mtx;

    static Tp get_expire_time(int ttl) {
        return std::chrono::steady_clock::now() + std::chrono::seconds(ttl);
    }

    void insert_into_ttl_map(const std::string& key, Tp expire_time) {
        auto& key_set = m_ttl_map[expire_time];
        key_set.insert(key);
    }

    void erase_from_ttl_map(const std::string& key, Tp expire_time) {
        auto it = m_ttl_map.find(expire_time);
        if (it == m_ttl_map.end()) {
            return;
        }
        auto& key_set = it->second;
        key_set.erase(key);
        // set为空就删掉map条目，避免堆积空集合
        if (key_set.empty()) {
            m_ttl_map.erase(it);
        }
    }

    // 【重要】调用本函数前，本线程不要持有m_rw_mtx任何锁！
    void remove_expired_keys() {
        std::unique_lock<std::shared_mutex> wlock(m_rw_mtx);
        const auto now = std::chrono::steady_clock::now();

        auto it = m_ttl_map.begin();
        while (it != m_ttl_map.end() && it->first <= now) {
            // 删除该过期时间下所有key
            for (const auto& key : it->second) {
                m_store_map.erase(key);
            }
            it = m_ttl_map.erase(it);
        }
    }
};