Here is an application for a C++ LRU datastructure in computer graphics: http://aim.adc.rmit.edu.au/phd/sgreuter/papers/graphite2003.pdf
In a nutshell, the datastructure is a fairly generic arrangement of std::list and std::map, but the replacement policy is fairly application-oriented.
<Chuckles> That's exactly the same data structure I used to cache regex-traits classes and locales in boost/pending/object_cache.hpp. So it looks like at least two of us came up with the same idea...
It's a fairly well cited paper now after three years, I don't recall boost having the MultiIndex stuff back when that work was being done. It would be nice revisit all that stuff with boost added to the toolchain... I'm also involved in applying graph-based optimisation to computer graphics, but the boost graph stuff turned up a little bit late for my purposes... :-) Glad we didn't do anything too strange for our LRU cache! Nigel