lfu_cache.cpp File Reference

Implementation for [LFU Cache] (https://en.wikipedia.org/wiki/Least_frequently_used) More...

#include <cassert>
#include <iostream>
#include <unordered_map>

Include dependency graph for lfu_cache.cpp:

Go to the source code of this file.

Classes
class	others::Cache::D_Node< T >
	Node for a doubly linked list with data, prev and next pointers. More...
class	others::Cache::LFUCache< K, V >
	LFUCache. More...

Namespaces
namespace	others
	for vector
namespace	others::Cache
	Cache algorithm.

Typedefs
template<typename K , typename V >
using	others::Cache::CacheNode = D_Node<std::pair<K, V>>

Functions
static void	test ()
	self test implementation
int	main ()
	main function

Detailed Description

Implementation for [LFU Cache] (https://en.wikipedia.org/wiki/Least_frequently_used)

LFU discards the least frequently used value. if there are multiple items with the same minimum frequency then, the least recently used among them is discarded. Data structures used - doubly linked list and unordered_map(hash map).

Hashmap maps the key to the address of the node of the linked list and its current usage frequency. If the element is accessed the element is removed from the linked list of the current frequency and added to the linked list of incremented frequency.

When the cache is full, the last element in the minimum frequency linked list is popped.

Author

Karan Sharma

Definition in file lfu_cache.cpp.

Function Documentation

main()

int main

(

void

)

main function

Returns

0 on exit

Definition at line 301 of file lfu_cache.cpp.

           {
    test();  // run the self test implementation
    return 0;
}

test()

static void test ( )

static

self test implementation

Returns

void

Definition at line 250 of file lfu_cache.cpp.

                   {
    others::Cache::LFUCache<int, int> cache(5);
 
    // test the initial state of the cache
    assert(cache.size() == 0);
    assert(cache.capacity() == 5);
    assert(cache.empty());
 
    // test insertion in the cache
    cache.put(1, 10);
    cache.put(-2, 20);
 
    // test the state of cache after inserting some items
    assert(cache.size() == 2);
    assert(cache.capacity() == 5);
    assert(!cache.empty());
 
    // test getting items from the cache
    assert(cache.get(1) == 10);
    assert(cache.get(-2) == 20);
 
    cache.put(-3, -30);
    cache.put(4, 40);
    cache.put(5, -50);
    cache.put(6, 60);
 
    // test the state after inserting more items than the capacity
    assert(cache.size() == 5);
    assert(cache.capacity() == 5);
    assert(!cache.empty());
 
    // test retrieval of all items in the cache
    assert(cache.get(1) == 10);
    assert(cache.get(-2) == 20);
 
    // fetching -3 throws runtime_error
    // as -3 was evicted being the least frequently used
    // when 6 was added
    // assert(cache.get(-3) == -30);
 
    assert(cache.get(4) == 40);
    assert(cache.get(5) == -50);
    assert(cache.get(6) == 60);
 
    std::cout << "test - passed\n";
}