LRU implementation in production code

by

Recently I implemented a LRU cache using a linked list spread over a hash map. 

    /// Typedef for URL/Entry pair
    typedef std::pair< std::string, Entry > EntryPair;

    /// Typedef for Cache list
    typedef std::list< EntryPair > CacheList;

    /// Typedef for URL-indexed map into the CacheList
    typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap;

    /// Cache LRU list
    CacheList mCacheList;

    /// Cache map into the list
    CacheMap mCacheMap;

It has the advantage of being O(1) for all important operations.

The insertion algorithm:

// create new entry
Entry iEntry( ... );

// push it to the front;
mCacheList.push_front( std::make_pair( aURL, iEntry ) );

// add it to the cache map
mCacheMap[ aURL ] = mCacheList.begin();

// increase count of entries
mEntries++;

// check if it's time to remove the last element
if ( mEntries > mMaxEntries )
{
    // erease from the map the last cache list element
    mCacheMap.erase( mCacheList.back().first );

    // erase it from the list
    mCacheList.pop_back();

    // decrease count
    mEntries--;
}

More Related Contents:

  1. LRU cache design
  2. Insertion sort stops working after million input
  3. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  4. C++ – Find numbers between first and last negative numbers in Array
  5. Program stopped working, when tried to run
  6. Absolute Distinct Numbers
  7. C++ throwing exception in recursive algorithm
  8. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  9. Calculating pow(a,b) mod n
  10. Rotating a point about another point (2D)
  11. Create Random Number Sequence with No Repeats
  12. Fast ceiling of an integer division in C / C++
  13. Getting the actual length of a UTF-8 encoded std::string?
  14. Search for a struct item in a vector by member data
  15. How can I find the actual path found by BFS?
  16. Splitting a string by a character
  17. How can I sort a std::map first by value, then by key?
  18. what is the difference between set and unordered_set in C++?
  19. Most efficient/elegant way to clip a number?
  20. Similar String algorithm
  21. The intersection of two sorted arrays
  22. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  23. Better shading on BW display while rendering filled surfaces
  24. Algorithm to add or subtract days from a date?
  25. Why would anyone use set instead of unordered_set?
  26. Creating N nested for-loops
  27. How to find Longest Common Substring using C++
  28. Mapping elements in 2D upper triangle and lower triangle to linear structure
  29. Fastest way to get the integer part of sqrt(n)?
  30. Generate N random numbers within a range with a constant sum

Leave a Comment