{"id":7681,"date":"2026-08-18T18:07:45","date_gmt":"2026-08-18T10:07:45","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7681"},"modified":"2026-08-18T18:07:45","modified_gmt":"2026-08-18T10:07:45","slug":"%e8%af%bb%e5%86%99%e9%94%81%ef%bc%8cttl%e8%bf%87%e6%9c%9f%ef%bc%8cologn%e6%97%b6%e9%97%b4%e5%a4%8d%e6%9d%82%e5%ba%a6%e7%9a%84cache%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7681","title":{"rendered":"\u8bfb\u5199\u9501\uff0cTTL\u8fc7\u671f\uff0cO(log(N))\u65f6\u95f4\u590d\u6742\u5ea6\u7684cache\u5b9e\u73b0"},"content":{"rendered":"<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">class Solution {\r\npublic:\r\n    void put(const std::string&amp; key, const std::string&amp; value, int ttl) {\r\n        \/\/ \u6e05\u7406\u8fc7\u671f\uff1a\u5185\u90e8\u81ea\u5df1\u62ff\u5199\u9501\uff0c\u8c03\u7528\u524d\u4e0d\u80fd\u6301\u6709\u4efb\u4f55\u9501\r\n        remove_expired_keys();\r\n\r\n        std::shared_lock&lt;std::shared_mutex&gt; rlock(m_rw_mtx);\r\n        auto it_store = m_store_map.find(key);\r\n        if (it_store != m_store_map.end()) {\r\n            \/\/ \u62ff\u5230\u65e7\u6570\u636e\r\n            const auto old_expire = it_store-&gt;second.expire_time;\r\n            rlock.unlock(); \/\/ \u91ca\u653e\u8bfb\u9501\uff0c\u51c6\u5907\u5199\u64cd\u4f5c\r\n\r\n            std::unique_lock&lt;std::shared_mutex&gt; wlock(m_rw_mtx);\r\n            \/\/ \u5220\u9664\u65e7ttl\u6620\u5c04\r\n            erase_from_ttl_map(key, old_expire);\r\n\r\n            \/\/ \u8bbe\u7f6e\u65b0\u503c\u3001\u65b0\u8fc7\u671f\u65f6\u95f4\r\n            auto new_expire = get_expire_time(ttl);\r\n            m_store_map[key] = StoreData{value, new_expire};\r\n            insert_into_ttl_map(key, new_expire);\r\n            return;\r\n        }\r\n\r\n        \/\/ key\u4e0d\u5b58\u5728\uff0c\u63d2\u5165\u65b0kv\r\n        rlock.unlock();\r\n        std::unique_lock&lt;std::shared_mutex&gt; wlock(m_rw_mtx);\r\n        auto new_expire = get_expire_time(ttl);\r\n        m_store_map[key] = StoreData{value, new_expire};\r\n        insert_into_ttl_map(key, new_expire);\r\n    }\r\n\r\n    std::unique_ptr&lt;std::string&gt; get(const std::string&amp; key) {\r\n        remove_expired_keys();\r\n\r\n        std::shared_lock&lt;std::shared_mutex&gt; rlock(m_rw_mtx);\r\n        auto it = m_store_map.find(key);\r\n        if (it != m_store_map.end()) {\r\n            return std::make_unique&lt;std::string&gt;(it-&gt;second.value);\r\n        }\r\n        return nullptr;\r\n    }\r\n\r\n    size_t size() {\r\n        remove_expired_keys();\r\n\r\n        std::shared_lock&lt;std::shared_mutex&gt; rlock(m_rw_mtx);\r\n        return m_store_map.size();\r\n    }\r\n\r\nprivate:\r\n    using Tp = std::chrono::steady_clock::time_point;\r\n\r\n    struct StoreData {\r\n        std::string value;\r\n        Tp expire_time;\r\n    };\r\n\r\n    std::unordered_map&lt;std::string, StoreData&gt; m_store_map;\r\n    \/\/ key:\u8fc7\u671f\u65f6\u95f4\u70b9\uff0cvalue:\u8be5\u65f6\u523b\u8fc7\u671f\u7684key\u96c6\u5408\r\n    std::map&lt;Tp, std::set&lt;std::string&gt;&gt; m_ttl_map;\r\n    std::shared_mutex m_rw_mtx;\r\n\r\n    static Tp get_expire_time(int ttl) {\r\n        return std::chrono::steady_clock::now() + std::chrono::seconds(ttl);\r\n    }\r\n\r\n    void insert_into_ttl_map(const std::string&amp; key, Tp expire_time) {\r\n        auto&amp; key_set = m_ttl_map[expire_time];\r\n        key_set.insert(key);\r\n    }\r\n\r\n    void erase_from_ttl_map(const std::string&amp; key, Tp expire_time) {\r\n        auto it = m_ttl_map.find(expire_time);\r\n        if (it == m_ttl_map.end()) {\r\n            return;\r\n        }\r\n        auto&amp; key_set = it-&gt;second;\r\n        key_set.erase(key);\r\n        \/\/ set\u4e3a\u7a7a\u5c31\u5220\u6389map\u6761\u76ee\uff0c\u907f\u514d\u5806\u79ef\u7a7a\u96c6\u5408\r\n        if (key_set.empty()) {\r\n            m_ttl_map.erase(it);\r\n        }\r\n    }\r\n\r\n    \/\/ \u3010\u91cd\u8981\u3011\u8c03\u7528\u672c\u51fd\u6570\u524d\uff0c\u672c\u7ebf\u7a0b\u4e0d\u8981\u6301\u6709m_rw_mtx\u4efb\u4f55\u9501\uff01\r\n    void remove_expired_keys() {\r\n        std::unique_lock&lt;std::shared_mutex&gt; wlock(m_rw_mtx);\r\n        const auto now = std::chrono::steady_clock::now();\r\n\r\n        auto it = m_ttl_map.begin();\r\n        while (it != m_ttl_map.end() &amp;&amp; it-&gt;first &lt;= now) {\r\n            \/\/ \u5220\u9664\u8be5\u8fc7\u671f\u65f6\u95f4\u4e0b\u6240\u6709key\r\n            for (const auto&amp; key : it-&gt;second) {\r\n                m_store_map.erase(key);\r\n            }\r\n            it = m_ttl_map.erase(it);\r\n        }\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>class Solution { pub<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7681","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7681","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7681"}],"version-history":[{"count":1,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7681\/revisions"}],"predecessor-version":[{"id":7682,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7681\/revisions\/7682"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7681"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7681"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7681"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}