Home
How to Implement a LRU (Least Recently Used) Cache in C++?
Tags:, , , ,

How to Implement a LRU (Least Recently Used) Cache in C++?

November 19, 2013 1 Comment c / c++, data structure, interview questions

Design and Implement a LRU (Least Recently Used) Cache that supports two operations i.e. get and set.

get(key) – This method will retrieve the value (non-negative) of the key if the key exists in the cache, return -1 otherwise.

set(key, value) – This method sets or inserts the value if the key is not existent When the cache reached its maximum capacity, it should remove the least recently used item before adding the new item.

O(N) LRU Implementation

First we need to define the basic data structure for holding the pair of key and value, we name it elem by using the struct data type in C/C++.

1
2
3
4

typedef struct {
    int key;
    int val;
} elem;
typedef struct {
    int key;
    int val;
} elem;

In the constructor, we takes the parameter of the maximum capacity of the list. We should also declare a private attribute for holding the list in the class and additionally, we have another integer type holding the current number of elements held in the list.

1
2
3
4
5
6
7
8
9
10
11
12

class LRUCache{
public:
    elem *arr;
    int sz;  // holds the current number of elements
    int cap;
 
    LRUCache(int capacity) {
        arr = new elem[capacity];
        sz = 0;
        cap = capacity;
    }
}
class LRUCache{
public:
    elem *arr;
    int sz;  // holds the current number of elements
    int cap;

    LRUCache(int capacity) {
        arr = new elem[capacity];
        sz = 0;
        cap = capacity;
    }
}

If an element is recently used e.g. get, set (insert of update), we should move this to the end of the list and shift one position to the left for the other elements on the right.

1
2
3
4
5
6
7
8
9
10
11

/* move the used element to the end of list */
    void adjust(int a) {
        if (a == sz - 1) {
            return ;
        }
        elem cur = arr[a]; 
        for (int i = a; i < sz - 1; i ++) {
            arr[i] = arr[i + 1]; // move others 1 pos left
        }
        arr[sz - 1] = cur; // move to the end
    }
/* move the used element to the end of list */
    void adjust(int a) {
        if (a == sz - 1) {
            return ;
        }
        elem cur = arr[a]; 
        for (int i = a; i < sz - 1; i ++) {
            arr[i] = arr[i + 1]; // move others 1 pos left
        }
        arr[sz - 1] = cur; // move to the end
    }

To check if a key has been in the list, simply loop from the left to the right and remember to move the found key-pair to the end of the list.

1
2
3
4
5
6
7
8
9
10

    int get(int key) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) {
                int a = arr[i].val;
                adjust(i);
                return a; // existent key
            }
        }
        return -1;
    }
    int get(int key) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) {
                int a = arr[i].val;
                adjust(i);
                return a; // existent key
            }
        }
        return -1;
    }

To set a key-pair, first check if the key has been existent, if yes, update the value otherwise, add a new element to the end of the list, in which case, you have to check if the size has exceeded the capacity. If yes, remove the left-most element (shift all other elements one position to the left).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    void set(int key, int value) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) { // existent
                arr[i].val = value;
                adjust(i);
                return;
            }
        }
        if (sz == cap) { // check if reach the capacity
            for (int i = 0; i < sz - 1; i ++) {
                arr[i] = arr[i + 1]; // delete the least used element
            }
            arr[sz - 1].key = key;
            arr[sz - 1].val = value;
        } else {
            arr[sz].key = key;
            arr[sz].val = value;            
            sz ++; // increase the size
        }
    }
    void set(int key, int value) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) { // existent
                arr[i].val = value;
                adjust(i);
                return;
            }
        }
        if (sz == cap) { // check if reach the capacity
            for (int i = 0; i < sz - 1; i ++) {
                arr[i] = arr[i + 1]; // delete the least used element
            }
            arr[sz - 1].key = key;
            arr[sz - 1].val = value;
        } else {
            arr[sz].key = key;
            arr[sz].val = value;            
            sz ++; // increase the size
        }
    }

Put all together:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

typedef struct {
    int key;
    int val;
} elem;
 
class LRUCache {
public:
    elem *arr; 
    int sz;  // total number of elements in the list currently.
    int cap;
 
    LRUCache(int capacity) {
        arr = new elem[capacity];
        sz = 0;
        cap = capacity;
    }
 
    /* move the used element to the end of list */
    void adjust(int a) {
        if (a == sz - 1) {
            return ;
        }
        elem cur = arr[a]; 
        for (int i = a; i < sz - 1; i ++) {
            arr[i] = arr[i + 1]; // move others 1 pos left
        }
        arr[sz - 1] = cur; // move to the end
    }
 
    int get(int key) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) {
                int a = arr[i].val;
                adjust(i);
                return a; // existent key
            }
        }
        return -1;
    }
 
    void set(int key, int value) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) { // existent
                arr[i].val = value;
                adjust(i);
                return;
            }
        }
        if (sz == cap) { // check if reach the capacity
            for (int i = 0; i < sz - 1; i ++) {
                arr[i] = arr[i + 1]; // delete the least used element
            }
            arr[sz - 1].key = key;
            arr[sz - 1].val = value;
        } else {
            arr[sz].key = key;
            arr[sz].val = value;            
            sz ++; // increase the size
        }
    }
};
typedef struct {
    int key;
    int val;
} elem;

class LRUCache {
public:
    elem *arr; 
    int sz;  // total number of elements in the list currently.
    int cap;

    LRUCache(int capacity) {
        arr = new elem[capacity];
        sz = 0;
        cap = capacity;
    }

    /* move the used element to the end of list */
    void adjust(int a) {
        if (a == sz - 1) {
            return ;
        }
        elem cur = arr[a]; 
        for (int i = a; i < sz - 1; i ++) {
            arr[i] = arr[i + 1]; // move others 1 pos left
        }
        arr[sz - 1] = cur; // move to the end
    }

    int get(int key) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) {
                int a = arr[i].val;
                adjust(i);
                return a; // existent key
            }
        }
        return -1;
    }

    void set(int key, int value) {
        for (int i = 0; i < sz; i ++) {
            if (arr[i].key == key) { // existent
                arr[i].val = value;
                adjust(i);
                return;
            }
        }
        if (sz == cap) { // check if reach the capacity
            for (int i = 0; i < sz - 1; i ++) {
                arr[i] = arr[i + 1]; // delete the least used element
            }
            arr[sz - 1].key = key;
            arr[sz - 1].val = value;
        } else {
            arr[sz].key = key;
            arr[sz].val = value;            
            sz ++; // increase the size
        }
    }
};

Using Double Linked List to Implement a LRU in C++

We can improve the performance to O(1) in both get and set by using a Double Linked List:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

class LRUCache {
public:
    struct ListNode {
        int val;
        int key;
        ListNode* prev;
        ListNode* next;
    };
    
    LRUCache(int capacity) {
        sz = capacity;
        count = 0;
        head = nullptr;
        tail = nullptr;
    }
    
    int get(int key) {
        if (data.find(key) == data.end()) return -1;
        ListNode* cur = data[key];
        update(cur);
        return cur->val;
    }
    
    void removeNode(ListNode* cur) {        
        data.erase(cur->key);        
        count --;
        if (head == nullptr || tail == nullptr) return;
        if (head == tail) {
            head = nullptr;
            tail = nullptr;
            return;
        }
        if (head == cur) {
            head = head->next;
            head->prev = nullptr;
            return;
        }
        if (cur == tail) {
            tail = tail->prev;
            tail->next = nullptr;
            return;
        }
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;        
        //delete cur;
    }
    
    void addNode(ListNode* cur) {
        data[cur->key] = cur;
        count ++;
        if (head == nullptr || tail == nullptr) {
            head = cur;
            head->next = nullptr;
            head->prev = nullptr;
            tail = head;
            return;
        }
        tail->next = cur;
        cur->prev = tail;
        tail = cur;                
    }    
    
    void update(ListNode *cur) {
        removeNode(cur);
        addNode(cur);
    }
    
    void put(int key, int value) {
        if (data.find(key) != data.end()) {
            ListNode* cur = data[key];
            cur->val = value;
            update(cur);            
        } else {
            if (count == sz) {
                removeNode(head);
            }
            ListNode* cur = new ListNode();
            cur->val = value;
            cur->key = key;
            addNode(cur);
        }
    }
private:
    int sz;
    int count;
    ListNode* head;
    ListNode* tail;
    unordered_map<int, ListNode*> data;
};
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
class LRUCache {
public:
    struct ListNode {
        int val;
        int key;
        ListNode* prev;
        ListNode* next;
    };
    
    LRUCache(int capacity) {
        sz = capacity;
        count = 0;
        head = nullptr;
        tail = nullptr;
    }
    
    int get(int key) {
        if (data.find(key) == data.end()) return -1;
        ListNode* cur = data[key];
        update(cur);
        return cur->val;
    }
    
    void removeNode(ListNode* cur) {        
        data.erase(cur->key);        
        count --;
        if (head == nullptr || tail == nullptr) return;
        if (head == tail) {
            head = nullptr;
            tail = nullptr;
            return;
        }
        if (head == cur) {
            head = head->next;
            head->prev = nullptr;
            return;
        }
        if (cur == tail) {
            tail = tail->prev;
            tail->next = nullptr;
            return;
        }
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;        
        //delete cur;
    }
    
    void addNode(ListNode* cur) {
        data[cur->key] = cur;
        count ++;
        if (head == nullptr || tail == nullptr) {
            head = cur;
            head->next = nullptr;
            head->prev = nullptr;
            tail = head;
            return;
        }
        tail->next = cur;
        cur->prev = tail;
        tail = cur;                
    }    
    
    void update(ListNode *cur) {
        removeNode(cur);
        addNode(cur);
    }
    
    void put(int key, int value) {
        if (data.find(key) != data.end()) {
            ListNode* cur = data[key];
            cur->val = value;
            update(cur);            
        } else {
            if (count == sz) {
                removeNode(head);
            }
            ListNode* cur = new ListNode();
            cur->val = value;
            cur->key = key;
            addNode(cur);
        }
    }
private:
    int sz;
    int count;
    ListNode* head;
    ListNode* tail;
    unordered_map<int, ListNode*> data;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Using STL::list and unordered_map to implement a LRU

We can use STL::list class to implement a linked list, and thus making the LRU easier to implement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

struct Node {
    int key;
    int value;
};
 
class LRUCache {
private:
    list<Node> values;
    unordered_map<int, list<Node>::iterator> data;    
    int capacity;
    
public:
    LRUCache(int capacity): capacity(capacity) {}
    
    int get(int key) {
        auto item = data.find(key);
        if (item == data.end()) {
            return -1;
        }
        auto it = item->second;
        auto node = *it;
        values.erase(it);
        values.push_back(node);
        data[key] = prev(values.end());
        return node.value;
    }
    
    void put(int key, int value) {
        auto item = data.find(key);
        if (item == data.end()) {
            if (values.size() == capacity) {
                auto node = values.front();
                values.pop_front();
                auto it = data.find(node.key);
                data.erase(it);
            }
            values.push_back({key, value});
            data[key] = prev(values.end());
        } else {
            auto it = item->second;
            auto node = *it;
            values.erase(it);
            node.value = value;
            values.push_back(node);
            data[key] = prev(values.end());
        }        
    }
};
struct Node {
    int key;
    int value;
};

class LRUCache {
private:
    list<Node> values;
    unordered_map<int, list<Node>::iterator> data;    
    int capacity;
    
public:
    LRUCache(int capacity): capacity(capacity) {}
    
    int get(int key) {
        auto item = data.find(key);
        if (item == data.end()) {
            return -1;
        }
        auto it = item->second;
        auto node = *it;
        values.erase(it);
        values.push_back(node);
        data[key] = prev(values.end());
        return node.value;
    }
    
    void put(int key, int value) {
        auto item = data.find(key);
        if (item == data.end()) {
            if (values.size() == capacity) {
                auto node = values.front();
                values.pop_front();
                auto it = data.find(node.key);
                data.erase(it);
            }
            values.push_back({key, value});
            data[key] = prev(values.end());
        } else {
            auto it = item->second;
            auto node = *it;
            values.erase(it);
            node.value = value;
            values.push_back(node);
            data[key] = prev(values.end());
        }        
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1226 words
Last Post: C++ Chess Board Printing in Windows Using CodePage 437 - Extended ASCII
Next Post: Algorithms to Find the Single Number in C++

The Permanent URL is: How to Implement a LRU (Least Recently Used) Cache in C++?

Related posts:

  1. The String ZigZag Conversion Algorithms The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows...
  2. How to Implement Integer Square Root in C/C++? Question: Implement integer square root for int sqrt(int x) There are many ways to compute the...
  3. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  4. Get Help With SQL Database Design and Development For Your Business with SQL Server Consulting If you want to design an SQL database from scratch, revamp an existing system, or...
  5. C++ Coding Exercise – Product of Array Except Self Given an array of n integers where n > 1, nums, return an array output...
  6. How to Fix a Slow/Incorrect Clock on Windows? I have been using HP Z800 Server for a couple of years and lately, the...
  7. Review: Lenovo ThinkCenter M900 Tower Station The new machine Lenovo ThinkCenter M900 Tower Station has just arrived! my current Lenovo Laptop...
  8. Breadth First Search Algorithm to Find Nearest Right Node in Binary Tree Given the root of a binary tree and a node u in the tree, return...

One Response

  1. Rahul Jain

    Hey,I made a video explaining the solution using doubly linked list and hashmap, you can check this out !!
    Please do subscribe if you find this helpful
    https://www.youtube.com/watch?v=uIojskB-xAo

    Reply

Leave a Reply