Example Implementation of a Least Recently Used Cache in C++11

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 is implemented as well.
You may also download it here.
Usage:

LRUCache<int, string> cache(10); // Max. 10 Elements

cache[4] = "Foobar";
cache.insert(2, "Barfoo");

cout << cache[2] << endl;

auto tmp = cache.getCopy(2);
if(tmp == nullptr) {
  cout << "Not found..." << endl;
} else {
 cout << *tmp << endl;
}

LRUCache.h:

#ifndef LRUCACHE_H_
#define LRUCACHE_H_

#include <memory>
#include <map>
#include <list>

template <typename Key, typename Value>
class LRUCache {

private:
	typedef std::list<Key> HistoryType;
	typedef typename HistoryType::iterator HistoryTypeIterator;
	HistoryType _history;

	typedef std::map<Key, std::pair<Value, HistoryTypeIterator> > CacheType;
	typedef typename CacheType::iterator CacheTypeIterator;
	CacheType _cache;

	size_t _maxCapacity;

	void evict(size_t numElements = 1) {
		if(numElements > _history.size()) {
			numElements = _history.size();
		}

		while(numElements--) {
			auto it = _cache.find( _history.front() );
			_cache.erase(it);
			_history.pop_front();
		}
	}

	void updateHistory(const CacheTypeIterator& it) {
		_history.splice(_history.end(), _history, it->second.second);
	}
public:
	// if maxCapacity = 0 -> unlimited capacity
	LRUCache(size_t maxCapacity) : _maxCapacity(maxCapacity) {

	}

	~LRUCache() {

	}

	LRUCache(const LRUCache& other) : _maxCapacity(other._maxCapacity) {
		std::cout << "Copy Con" << std::endl;
		_cache = other._cache;
		_history = other._history;

		// Adjust Iterators
		for(auto it = _history.begin() ; it != _history.end() ; ++it)
			_cache.find(*it)->second.second = it;
	}

	LRUCache(LRUCache&& other) : _maxCapacity(other._maxCapacity) {
		_history = std::move(other._history);
		_cache = std::move(other._cache);
	}

	void dropCache(size_t maxRemainingElements = 0) {
		size_t elementsDropped;
		if(maxRemainingElements == 0) {
			elementsDropped = _history.size();
			_cache.clear();
			_history.clear();
		} else if (_history.size() > maxRemainingElements) {
			elementsDropped = _history.size() - maxRemainingElements;
			evict(elementsDropped);
		}
	}

	size_t size() {
		return _history.size();
	}

	void setMaxCapacity(const size_t& maxCapacity) {
		// problematic case: shrink cache
		if(maxCapacity < _maxCapacity && maxCapacity != 0)
			dropCache(maxCapacity);
		_maxCapacity = maxCapacity;
	}

	std::unique_ptr<Value> getCopy(const Key& id) {
		auto it = _cache.find(id);
		std::unique_ptr<Value> retval = nullptr;
		if(it != _cache.end()) {
			updateHistory(it);
			// Copy the element
			retval = std::unique_ptr<Value>(new Value(it->second.first));
		}

		return retval;
	}

	// Inserts new element. If the element already exists, it will be overwritten.
	// Returns a reference to the inserted object
	Value& insert(const Key& id, Value c) {
		// Check if the element is already existing
		auto it = _cache.find(id);
		if(it != _cache.end()) {
			// If the element exists, overwrite it
			it->second.first = c;
			updateHistory(it);
		} else {
			if(_maxCapacity != 0 && _history.size() == _maxCapacity) {
				evict();
			}
			auto end = _history.insert(_history.end(), id);
			auto newelem = _cache.insert( std::make_pair(id, std::make_pair(std::move(c), end ) ) );
			it = newelem.first;
		}

		return it->second.first;
	}

	Value&	operator[](const Key& id) {
		auto it = _cache.find(id);
		if(it != _cache.end()) {
			updateHistory(it);
			return it->second.first;
		}

		// Create new empty element
		return insert(id, std::move(Value()));
	}
};
#endif

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.