Implement LRU Cache in C++

Question

I have tried implementing LRU Cache Problem from LeetCode. https://leetcode.com/problems/lru-cache/ The entries in cache are in the form of {key, value} pairs. There is a weird issue that I am facing. To solve this problem, the approach is to use to a Doubly linked list with a HashMap. For Doubly linked list, What I have done is used a deque STL container instead of list STL container in my C++ code, but my code fails on below test case. If I just replace deque with list, the code got accepted. Can someone please help as what is the issue with using deque in implementing a LRU Cache. Also many test cases have passed with my code using deque. please help.

My Code :

class LRUCache {
public:
    unordered_map<int, pair<deque<int>::iterator,int>> mp; // {key, pair<iterator_position_in_deque, value>}; // iterator is the position in the deque where the key is stored.
    deque<int> dq; // {key} storing only keys.
    int size;
    int curr_size;
    LRUCache(int capacity) {
        curr_size = 0;
        size = capacity;
        dq.clear();
        mp.clear();
    }
    
    int get(int key) {
        if(mp.find(key) == mp.end()) {
            return -1;
        }
        
        // below 3 lines are same as in put function
        dq.erase(mp[key].first);
        dq.push_front(key);
        mp[key].first = dq.begin();
        
        return mp[key].second;
    }
    
    void put(int key, int value) {
        if(mp.find(key) != mp.end()) { // if key present in cache
            
            dq.erase(mp[key].first);
            dq.push_front(key);
            mp[key].first = dq.begin();
            
            mp[key].second = value; // update the new value to that key
        } else { // if key not present in our map and deque afterwards
            if (curr_size < size) {
                dq.push_front(key);
                mp[key] = make_pair(dq.begin(), value);
                curr_size++;
            } else if (curr_size == size) {
                mp.erase(dq.back()); // element will the key as deque stores key
                dq.pop_back();
                dq.push_front(key);
                mp[key] = make_pair(dq.begin(), value);
            }
        }
    }
    
};

/**
 * 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);
 */

Test Case on which it failing :

["LRUCache","put","put","put","put","put","get","put","get","get","put","get","put","put","put","get","put","get","get","get","get","put","put","get","get","get","put","put","get","put","get","put","get","get","get","put","put","put","get","put","get","get","put","put","get","put","put","put","put","get","put","put","get","put","put","get","put","put","put","put","put","get","put","put","get","put","get","get","get","put","get","get","put","put","put","put","get","put","put","put","put","get","get","get","put","put","put","get","put","put","put","get","put","put","put","get","get","get","put","put","put","put","get","put","put","put","put","put","put","put"]
[[10],[10,13],[3,17],[6,11],[10,5],[9,10],[13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],[1,30],[11],[9,12],[7],[5],[8],[9],[4,30],[9,3],[9],[10],[10],[6,14],[3,1],[3],[10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],[5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9],[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],[1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29],[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9],[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],[9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]] ```

Output :
```[null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,-1,null,null,18,null,null,11,null,null,null,null,null,18,null,null,-1,null,4,29,30,null,12,11,null,null,null,null,29,null,null,null,null,17,22,18,null,null,null,-1,null,null,null,-1,null,null,null,29,18,18,null,null,null,null,-1,null,null,null,null,null,null,null]```

Expected Output :
```[null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,-1,null,null,18,null,null,11,null,null,null,null,null,18,null,null,-1,null,4,29,30,null,12,11,null,null,null,null,29,null,null,null,null,17,22,18,null,null,null,-1,null,null,null,-1,null,null,null,29,18,18,null,null,null,null,-1,null,null,null,null,null,null,null]```

mp[key] = make_pair(dq.begin(), value); -- Off topic, but that line and lines that look like it could simply be: mp[key] = {dq.begin(), value};. The braces removes the need to specify make_pair. You also don't need to call dq.clear() or mq.clear() in the constructor, since they already start out as cleared. — PaulMcKenzie
– PaulMcKenzie, Commented Nov 22, 2020 at 15:42

Igor Tandetnik · Accepted Answer · 2020-11-22 15:24:05Z

2

std::deque::erase(it) invalidates all iterators into this deque, not just it (except when it refers to the first or the last element). mp is left holding now-invalid iterators, and a subsequent attempt to use them exhibits undefined behavior.

In contrast, std::list::erase(it) invalidates only it (or to be precise, all iterators referring to *it), but no other iterators.

answered Nov 22, 2020 at 15:24

Igor Tandetnik

53.1k4 gold badges65 silver badges93 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1726084 Over a year ago

Thanks for your answer. But I didn't understand what invalidates means here when you say it invalidates all iterators

Igor Tandetnik Over a year ago

"Invalidates" as in "makes invalid, no longer usable". Again, any attempt to use an invalid iterator exhibits undefined behavior. Practically speaking, the deque may move and rearrange its elements to close the gap when an element is removed from the middle, so an iterator that previously referred to some element may end up referring to some other element, or pointing to memory where some element used to exist but no longer does.

Sam Varshavchik · Accepted Answer · 2020-11-22 15:25:56Z

1

dq.erase(mp[key].first);

This is (potentially) erases a value from the middle of the deque.

Erasing from a middle of a deque invalidates all other existing iterators to the dequeue. Only erasing from the beginning or the end of a deque does not invalidate any other iterators to the non-erased deque values.

At this point, all other iterators in your map are no longer valid. From this point on, using any other remaining iterators, via your map, becomes undefined behavior.

You will need to completely redesign your implementation. deque cannot be used in this manner.

answered Nov 22, 2020 at 15:25

Sam Varshavchik

119k6 gold badges109 silver badges164 bronze badges

2 Comments

user1726084 Over a year ago

What does invalidates mean here. If I just replace deque with list in my code. Everything remains as it is. It will be accepted.

Sam Varshavchik Over a year ago

What it means, is that if you try to use them you will get demons flying out of your nose. If you don't want demons flying out of your nose, don't use invalidated iterators. And, of course if you replace the deque with a list, this is no longer an issue, because removing a value from the list does not invalidate any iterators to any other values in the list. Which is not the case with the deque. There are reasons why the C++ library has different containers, like vectors, lists, deques, etc. They all have different fundamental properties.

Collectives™ on Stack Overflow

Implement LRU Cache in C++

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related