Coders Packet

LFU Cache Implementation in C++

By Siddharth Vinayak Bawane

This project is a basic implementation of LFU (Least Frequently Used) cache algorithm in C++.

LFU algorithm eliminates the least frequently used item in the cache memory if it exceeds its maximum capacity. It is an efficient method for handling huge data requests.

This project consists of a header file lfu.hppwhich implements class LFUCache.

LFUCache contains the following public functions:

1) Constructor(capacity): It accepts an integer value that represents the capacity of LFU cache.

2) get(key): It accepts an integer that represents the key and returns its value if the key exists in the LFU cache.

3) add(key, value): It accepts two integers, the first integer is the key and the second integer represents its value. It adds the (key, value) pair to the cache memory.

Working of the Project: The key point is a Node that stores the information of the list and frequency. Whenever this Node is touched, the list and frequency are to be updated.

We need 2 hashmaps. One is key to value; another one is the frequency to the doubly linked list which stores the Nodes from head (most recent accessed units) to tail (least recently accessed units).

get(key) gets the value from the hashmap (key to value), also needs to update the hashmap (key to list). Move from freq list to freq+1 list. If the key doesn't exist in the memory, it returns -1.

add(key, value) checks if the key already exists. If yes, update the value, and update frequency (move from freq list to freq+1 list). If no, remove it from the freq list, and add a new Node with freq = 1.

Time Complexity: This project implements LFU cache in O(1) time since get() and add() operation requires constant time.

Below is an example of how this project can be used:

LFU1

LFU2

Go ahead and implement this library in your own project and use the memory efficiently.

Download project

Reviews Report

Submitted by Siddharth Vinayak Bawane (Sidb07)

Download packets of source code on Coders Packet