{"id":127,"date":"2013-06-01T01:27:34","date_gmt":"2013-05-31T23:27:34","guid":{"rendered":"http:\/\/blog.ramses-pyramidenbau.de\/?p=127"},"modified":"2013-06-11T17:55:20","modified_gmt":"2013-06-11T15:55:20","slug":"example-implementation-of-a-least-recently-used-cache-in-c11","status":"publish","type":"post","link":"https:\/\/blog.vmexit.de\/?p=127","title":{"rendered":"Example Implementation of a Least Recently Used Cache in C++11"},"content":{"rendered":"

This is yet another example implementation of a Least Recently Used Cache written in C++11.
\nIt is not<\/strong> designed to be threadsafe, but thread safety could easily be reached by locking
\nthe same mutex at the beginning of all public methods.<\/p>\n

This Cache uses std::map and std::list as container types. A copy and move constructor is implemented as well.
\nYou may also download it here<\/a>.
\nUsage:<\/p>\n

\r\nLRUCache<int, string> cache(10); \/\/ Max. 10 Elements\r\n\r\ncache[4] = "Foobar";\r\ncache.insert(2, "Barfoo");\r\n\r\ncout << cache[2] << endl;\r\n\r\nauto tmp = cache.getCopy(2);\r\nif(tmp == nullptr) {\r\n  cout << "Not found..." << endl;\r\n} else {\r\n cout << *tmp << endl;\r\n}\r\n<\/pre>\n
LRUCache.h:<\/p>\n
\r\n#ifndef LRUCACHE_H_\r\n#define LRUCACHE_H_\r\n\r\n#include <memory>\r\n#include <map>\r\n#include <list>\r\n\r\ntemplate <typename Key, typename Value>\r\nclass LRUCache {\r\n\r\nprivate:\r\n\ttypedef std::list<Key> HistoryType;\r\n\ttypedef typename HistoryType::iterator HistoryTypeIterator;\r\n\tHistoryType _history;\r\n\r\n\ttypedef std::map<Key, std::pair<Value, HistoryTypeIterator> > CacheType;\r\n\ttypedef typename CacheType::iterator CacheTypeIterator;\r\n\tCacheType _cache;\r\n\r\n\tsize_t _maxCapacity;\r\n\r\n\tvoid evict(size_t numElements = 1) {\r\n\t\tif(numElements > _history.size()) {\r\n\t\t\tnumElements = _history.size();\r\n\t\t}\r\n\r\n\t\twhile(numElements--) {\r\n\t\t\tauto it = _cache.find( _history.front() );\r\n\t\t\t_cache.erase(it);\r\n\t\t\t_history.pop_front();\r\n\t\t}\r\n\t}\r\n\r\n\tvoid updateHistory(const CacheTypeIterator& it) {\r\n\t\t_history.splice(_history.end(), _history, it->second.second);\r\n\t}\r\npublic:\r\n\t\/\/ if maxCapacity = 0 -> unlimited capacity\r\n\tLRUCache(size_t maxCapacity) : _maxCapacity(maxCapacity) {\r\n\r\n\t}\r\n\r\n\t~LRUCache() {\r\n\r\n\t}\r\n\r\n\tLRUCache(const LRUCache& other) : _maxCapacity(other._maxCapacity) {\r\n\t\tstd::cout << "Copy Con" << std::endl;\r\n\t\t_cache = other._cache;\r\n\t\t_history = other._history;\r\n\r\n\t\t\/\/ Adjust Iterators\r\n\t\tfor(auto it = _history.begin() ; it != _history.end() ; ++it)\r\n\t\t\t_cache.find(*it)->second.second = it;\r\n\t}\r\n\r\n\tLRUCache(LRUCache&& other) : _maxCapacity(other._maxCapacity) {\r\n\t\t_history = std::move(other._history);\r\n\t\t_cache = std::move(other._cache);\r\n\t}\r\n\r\n\tvoid dropCache(size_t maxRemainingElements = 0) {\r\n\t\tsize_t elementsDropped;\r\n\t\tif(maxRemainingElements == 0) {\r\n\t\t\telementsDropped = _history.size();\r\n\t\t\t_cache.clear();\r\n\t\t\t_history.clear();\r\n\t\t} else if (_history.size() > maxRemainingElements) {\r\n\t\t\telementsDropped = _history.size() - maxRemainingElements;\r\n\t\t\tevict(elementsDropped);\r\n\t\t}\r\n\t}\r\n\r\n\tsize_t size() {\r\n\t\treturn _history.size();\r\n\t}\r\n\r\n\tvoid setMaxCapacity(const size_t& maxCapacity) {\r\n\t\t\/\/ problematic case: shrink cache\r\n\t\tif(maxCapacity < _maxCapacity && maxCapacity != 0)\r\n\t\t\tdropCache(maxCapacity);\r\n\t\t_maxCapacity = maxCapacity;\r\n\t}\r\n\r\n\tstd::unique_ptr<Value> getCopy(const Key& id) {\r\n\t\tauto it = _cache.find(id);\r\n\t\tstd::unique_ptr<Value> retval = nullptr;\r\n\t\tif(it != _cache.end()) {\r\n\t\t\tupdateHistory(it);\r\n\t\t\t\/\/ Copy the element\r\n\t\t\tretval = std::unique_ptr<Value>(new Value(it->second.first));\r\n\t\t}\r\n\r\n\t\treturn retval;\r\n\t}\r\n\r\n\t\/\/ Inserts new element. If the element already exists, it will be overwritten.\r\n\t\/\/ Returns a reference to the inserted object\r\n\tValue& insert(const Key& id, Value c) {\r\n\t\t\/\/ Check if the element is already existing\r\n\t\tauto it = _cache.find(id);\r\n\t\tif(it != _cache.end()) {\r\n\t\t\t\/\/ If the element exists, overwrite it\r\n\t\t\tit->second.first = c;\r\n\t\t\tupdateHistory(it);\r\n\t\t} else {\r\n\t\t\tif(_maxCapacity != 0 && _history.size() == _maxCapacity) {\r\n\t\t\t\tevict();\r\n\t\t\t}\r\n\t\t\tauto end = _history.insert(_history.end(), id);\r\n\t\t\tauto newelem = _cache.insert( std::make_pair(id, std::make_pair(std::move(c), end ) ) );\r\n\t\t\tit = newelem.first;\r\n\t\t}\r\n\r\n\t\treturn it->second.first;\r\n\t}\r\n\r\n\tValue&\toperator[](const Key& id) {\r\n\t\tauto it = _cache.find(id);\r\n\t\tif(it != _cache.end()) {\r\n\t\t\tupdateHistory(it);\r\n\t\t\treturn it->second.first;\r\n\t\t}\r\n\r\n\t\t\/\/ Create new empty element\r\n\t\treturn insert(id, std::move(Value()));\r\n\t}\r\n};\r\n#endif\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
This is yet another example implementation of a Least Recently Used Cache written in C++11. It is not designed to be threadsafe, but thread safety could easily be reached by locking the same mutex at the beginning of all public methods. This Cache uses std::map and std::list as container types. A copy and move constructor … Continue reading Example Implementation of a Least Recently Used Cache in C++11<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-127","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=\/wp\/v2\/posts\/127","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=127"}],"version-history":[{"count":7,"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=\/wp\/v2\/posts\/127\/revisions"}],"predecessor-version":[{"id":139,"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=\/wp\/v2\/posts\/127\/revisions\/139"}],"wp:attachment":[{"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=127"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=127"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.vmexit.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=127"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}