CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: LRU cache

  1. #1
    Join Date
    May 2015
    Posts
    500

    LRU cache

    Hi All,

    I was trying to practice some LRU cache example from the online practice. Also checking the discussions, where somebody already solved using the hash map and the doubly linked list. Another was , using the stl map and list. It was easier to implement with the stl. But I am not getting why they have put iterator within the map. I tried their solution, which works as expected. But not able to get why the iterator is used in the map.

    Sorry for my basic Q.

    I was wondering, whether i can make it easier, if i change to unordered map. But googling tells, unordered map, may not insert in timely order ! i., ie
    map<int, list<pair<int, int> to
    unordered_map<int, int>

    Code:
    #include <list>
    #define key first
    #define val second
    class LRUCache {
        int cp;
        map<int, list<pair<int, int> >::iterator> mp;
        list<pair<int, int> > lru;
    public:
        LRUCache(int capacity) : cp(capacity){}
        void set(int key, int val) {
            if(mp.find(key) != mp.end()) {
                mp[key]->key = key;
                mp[key]->val = val;
            }
            else {
                lru.push_front({key, val});
                mp[key] = lru.begin();
                if(lru.size() > cp) {
                    mp.erase(lru.back().key);
                    lru.pop_back();
                }
            }
        }
        int get(int key) {
            if(mp.find(key) != mp.end()) {
                lru.push_front(*mp[key]);
                lru.erase(mp[key]);
                mp[key] = lru.begin();
                return mp[key]->val;
            }
            else
                return -1;
        }
    };
    +int main() {...
    Thanks a lot
    pdk

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: LRU cache

    Basically for a LRU:

    If the item exists, move to top
    If the item does not exist, insert at top. If the size now exceeds max items, remove bottom.

    This can be simply implemented using a list (try it). HOWEVER, the problem is one of performance. Determining if the item exists means traversing the list - a time consuming business. So what is wanted is some-way to quickly determine if the item exists and its position (iterator) in the list. This is where a map (or preferably unordered map) comes in. The map contains the items and 'pointers (iterators)' to the element in the list. Finding if an item exists in a map is quicker than traversing a list (a lot quicker with unordered map with correct hashing etc). Once you know if the item exists/not exists, then the required manipulation of the list is simply pointer changes - and possibly deletion/amend of an item in the map.

    Note that in the code in post#1:

    Code:
    if(mp.find(key) != mp.end()) {
                mp[key]->key = key;
                mp[key]->val = val;
            }
    This is not the best implementation. .find() returns an iterator to the found item, so this should be used rather than mp[key] (twice!) which does a tree traversal each time! The same elsewhere.

    If this code came from the Internet, I'd think twice about using that site again.

    PS Also the definition of the map can be simplified. Consider:

    Code:
    list<pair<int, int> > lru;
    map<int, decltype(lru.begin())> mp;
    From the way the list is typed (with > >) rather than just >>, I'd hazard a guess this is old code as requiring > > rather than >> was fixed years ago (C++11?)
    Last edited by 2kaud; January 3rd, 2021 at 08:32 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  3. #3
    Join Date
    May 2015
    Posts
    500

    Re: LRU cache

    Thankyou very much kaud. much appreciated. Sorry for the delay, was busy with some personal stuff.

    Yes, the site i was going through. because sometime back, i was searching for job, a company told they will ask me to solve questions from this site. I didnot attend then, but i was looking that site now, to improve c++ skills, by solving practice questions.

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: LRU cache

    For lru using unordered_map (hash) and list, consider:

    Code:
    #include <list>
    #include <iostream>
    #include <algorithm>
    #include <unordered_map>
    
    class LRU {
    	const static size_t MAXELM {10};
    
    	std::list<int> lru;
    	std::unordered_map<int, decltype(lru.cbegin())> um;
    
    public:
    	void add(int n)
    	{
    		if (const auto fnd1 {um.find(n)}; fnd1 != um.end())
    			lru.splice(lru.cbegin(), lru, fnd1->second);
    		else {
    			if (lru.size() == MAXELM) {
    				um.erase(lru.back());
    				lru.pop_back();
    			}
    
    			lru.push_front(n);
    			um.emplace(n, lru.cbegin());
    		}
    	}
    
    	bool remove(int n)
    	{
    		if (const auto fnd1 {um.find(n)}; fnd1 != um.end()) {
    			lru.erase(fnd1->second);
    			um.erase(fnd1);
    			return true;
    		}
    
    		return false;
    	}
    
    	void display()
    	{
    		for (const auto& l : lru)
    			std::cout << l << ' ';
    
    		std::cout << '\n';
    	}
    };
    
    int main()
    {
    	LRU lru;
    
    	lru.add(1);
    	lru.add(2);
    	lru.add(3);
    	lru.display();
    
    	lru.add(1);
    	lru.display();
    
    	lru.add(4);
    	lru.add(5);
    	lru.add(6);
    	lru.add(7);
    	lru.add(8);
    	lru.add(9);
    	lru.add(10);
    	lru.add(11);
    	lru.display();
    }
    Note .splice() for moving elements within/between lists.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured