LRU C++ implementation using boost::bimaps (.h)

LRU stands for "Least Recently Used"; it is a very common algorithm used in tons and tons of applications, system engineering works. It is a very critical component interms of performance desired from it. For instance: if you are assigned to design a cache mechanism with a limited capacity, as capacity is limited and cache performance weights alot towards the application/systems overall performance; the engineer would consider below points while designing it:


1. Overhead cost of maintaining the datastructure; which incudes: insertion and deletion cost. 

2. Eviction criteria (as locality of reference plays its role in many aspects of systems engineering, the element that is recently used has high probability of being accessed again).

3. Lookup cost. 

If we consider Boost libraries; one of the datastructure that could be interesting to use is "Bimaps". It is a birectional map, simply it can be visualized as two maps tied together i.e. relations exists in both directions:


           <right elements>  -----> <left elements>


           <left elements>    -----> <right elements>


 


Above all design considerations are applicable here as well.