For comparison's sake, here's a simple LRU in Erlang: <a href="http://erlangquicktips.heroku.com/2008/10/05/an-erlang-lru-module/" rel="nofollow">http://erlangquicktips.heroku.com/2008/10/05/an-erlang-lru-m...</a>
This algorithm is arguably already patented: <a href="http://www.patentstorm.us/patents/5893120.html" rel="nofollow">http://www.patentstorm.us/patents/5893120.html</a><p>In fact, you may remember that Google was sued over this last year: <a href="http://news.cnet.com/8301-13577_3-20056192-36.html?part=rss&subj=news&tag=2547-1_3-0-20" rel="nofollow">http://news.cnet.com/8301-13577_3-20056192-36.html?part=rss&...</a><p>Granted, using a timestamp to expire hash table entries is probably different enough from using a timestamp to evict cache entries where I would hope this wouldn't hold up in court, but IANAL and I could be totally wrong here. Another possibility is that there could be a totally different patent that already covers this algorithm.
Here is another simple implementation in C++: <a href="https://github.com/albertz/grub-fuse/blob/master/include/cache.h" rel="nofollow">https://github.com/albertz/grub-fuse/blob/master/include/cac...</a><p>Usage example: <a href="https://github.com/albertz/grub-fuse/blob/master/grub-core/fs/reiserfs_key_cache.cpp" rel="nofollow">https://github.com/albertz/grub-fuse/blob/master/grub-core/f...</a>
If this article shows anything it is that C++ never really "grew up". Even in Java, implementing an LRU cache is such a trivial thing to do because most people actually use, and build on, the standard library.