Clean Short Standard C++ solution -- NOT writing C in C++ like all other lengthy ones


  • 51
    F

    I saw so many (or all) "C++" solutions posted here were not written in C++ at all. For those 200-line solutions, I don't see the point in implementing a double-linked-list by themselves.

    If you are writing C++, please use STL!

    The code below is way cleaner, shorter and easier to read than most other C++ solutions posted here.
    And above all, it was written in a standard C++ way.

    class LRUCache{
        size_t m_capacity;
        unordered_map<int,  list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;
        list<pair<int, int>> m_list;                               //m_list_iter->first: key, m_list_iter->second: value;
    public:
        LRUCache(size_t capacity):m_capacity(capacity) {
        }
        int get(int key) {
            auto found_iter = m_map.find(key);
            if (found_iter == m_map.end()) //key doesn't exist
                return -1;
            m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
            return found_iter->second->second;                         //return value of the node
        }
        void set(int key, int value) {
            auto found_iter = m_map.find(key);
            if (found_iter != m_map.end()) //key exists
            {
                m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
                found_iter->second->second = value;                        //update value of the node
                return;
            }
            if (m_map.size() == m_capacity) //reached capacity
            {
               int key_to_del = m_list.back().first; 
               m_list.pop_back();            //remove node in list;
               m_map.erase(key_to_del);      //remove key in map
            }
            m_list.emplace_front(key, value);  //create new node in list
            m_map[key] = m_list.begin();       //create correspondence between key and node
        }
    };

  • 7
    Y

    elegant code. I learned list.splice(). thank you.


  • 9
    S

    In your code

    if (m_list.size() == m_capacity) //reached capacity
    

    as per C++98, mylist.size() is linear time complexity. So your time is 168 ms.
    Replace it with mymap.size() which is constant time. Your time will be reduced to 80 ms.


  • 0
    F

    That's weird, because clearly leetcode supports C++11, and in C++ 11, STL container size() operation should run in O(1), including list.size(). But it's true it is faster to use m_map.size() here. I guess the version of compiler leetcode uses hasn't supported this feature, since it requires a new member and may break ABI with old versions. Thanks for pointing this out.


  • 0

    I am one of "most other C++ solutions" = =|||


  • 1
    O

    Aha, I'm another one of 'the most other C++ solutions', which implemented a double linked list.

    I attached my code at the end.
    It turned out to be 72ms though, slightly faster.
    But given the size and complexity, I prefer your solution.

    Thanks for sharing you code!
    I learned how to use std::splice() and think in C++ way (instead of C way).

    struct Node{
    Node(int k, int v): key(k), value(v), prev(nullptr), next(nullptr){}

    int key;
    int value;
    Node* prev;
    Node* next;
    

    };

    class LRUCache{
    public:
    LRUCache(int capacity): m_capacity(capacity), m_head(nullptr), m_tail(nullptr) {

    }
    
    int get(int key) {
        auto match = m_locations.find(key);
        
        if (match == m_locations.end())
            return -1;
        else
        {
            moveNodeToHead(match->second);
            return match->second->value;
        }
    }
    
    void set(int key, int value) {
        auto match = m_locations.find(key);
        
        if (match == m_locations.end())
        {
            if (m_locations.size() >= m_capacity)
            {
                // Delete tail
                Node* tail = m_tail;
                
                if (m_locations.size() == 1)
                {
                    m_head = nullptr;
                    m_tail = nullptr;
                }
                else
                {
                    m_tail->prev->next = nullptr;
                    m_tail = m_tail->prev;
                }
                m_locations.erase(tail->key);
                delete tail;
            }
            
            // Insert new node to front
            Node* node = new Node(key, value);
            
            if (m_locations.size() == 0)
            {
                m_head = node;
                m_tail = node;
            }
            else
            {
                node->next = m_head;
                m_head->prev = node;
                m_head = node;
            }
            m_locations[key] = node;
        }
        else
        {
            // Update existing node, move it to the front;
            match->second->value = value;
            moveNodeToHead(match->second);
        }
    }
    
    void moveNodeToHead(Node* node)
    {
        // Move node to the front;
        if (m_locations.size() == 1) // Node is the only one
                ;
        else if (node->prev == nullptr) // Node is head
                ;
        else if (node->next == nullptr) // Node is tail
        {
            // Make the second to last node the new tail
            node->prev->next = nullptr;
            m_tail = node->prev;
            
            // Make 'node' the new head;
            node->prev = nullptr;
            node->next = m_head;
            m_head->prev = node;
            m_head = node;
        }
        else // 'node' is in the middle of list
        {
            node->prev->next = node->next;
            node->next->prev = node->prev;
            
            node->prev = nullptr;
            node->next = m_head;
            m_head->prev = node;
            m_head = node;
        }
    }
    
    int m_capacity;
    Node* m_head;
    Node* m_tail;
    std::unordered_map<int, Node*> m_locations;
    

    };


  • 0
    P

    Excellent solution. I had to read up documentation to understand the splice part, but very elegant solution


  • 0
    X

    a standard C++ way! a nice lesson,thank you very much


  • 0
    C

    I learn list, emplace_front() and splice() from your solution. Thank you!

    The first half code in your set() is the same to get() expect that you need to update the value in m_list.front(), you could call get() in your set() and save a few lines.

        void set(int key, int value) {
            if (get(key) != -1) {
                m_list.front().second = value;
                return;
            } else if (m_map.size() == limit) {
                m_map.erase(m_list.back().first);
                m_list.pop_back();
            }
            m_list.emplace_front(key, value);
            m_map[key] = m_list.begin();
        }

  • 0
    D

    Could you explain why you use emplace front instead of push front?


  • 0
    A

    is it possible to just keep the value in the list, not the pair? I try the following code, but keep giving run time error. I can't understand why... Does it seem right?

    class LRUCache { //why keep giving run time error?
    public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (mp.find(key) == mp.end()) return -1;
        auto it = mp[key];
        l.splice(l.begin(), l, it);
        return *l.begin();
    }
    
    void set(int key, int value) {
        if (mp.find(key) != mp.end()) {
            l.splice(l.begin(), l, mp[key]);
            *l.begin() = value;
            return;   
        }
        
        if (mp.size() == cap) {
            int removekey = l.back();
            l.pop_back();
            mp.erase(removekey);
        }
        l.push_front(value);
        mp[key] = l.begin();
    }
    

    private:
    int cap;
    unordered_map<int, list<int>::iterator> mp;
    list<int> l;
    };


  • 0
    M

    @fentoyal Have you tested in your own machine, and confirm list.size() has the same complexity with map.size()?


  • 0
    F

    @matrixyy
    We don't "test" to find an answer for such a question.

    Why? Because I'm lazy to run tests? Nope, that's the reason:
    Testing results are just a suggestion , not a proof. What does it mean when the results show X method runs 200 ms faster for an input size N? A single case doesn't mean anything, so you need run 10K test then. After it's done, what now? How about input size N + 1, N -1, N*2, N/4? Ok, then run 10K N for each test, now you got 100 million tests to run. And finally, after probably one week of work, you found Oh, based on my test, X method does run faster than Y method. So what? Does that mean X has O(1) and Y has O(N)? Or it could be O(1) v.s. O(10), or O(lgN) v.s. O(N)? You really can't conclude anything from testing results. And even if you did a really convoluted design (now, it's 1 month of work) with your tests that can prove X method runs on O(1) and Y runs on O(N), this is probably just a compiler/platform optimization that is not part of the ISO standard, which means your conclusion doesn't universally holds, which means on a different platform you may have unexpected results.

    So, please just look it up in your language's standard for a question like this (or in an easier word, Google it). It takes you 5 mins and gives you a way more confident conclusion than 1 month of testing.


  • 0
    Z

    Very good solution. Learned a lot from it. Why don't we need a return at the end of the set function?


  • 0
    F

    @zandy1989
    I think the interface is pre-defined by Leetcode.


  • 0
    Z

    @fentoyal So that we don't need a return at any void()?


  • 0
    M

    great, you remind me to learn more about stl...


  • 0
    C

    this is so clean, best demonstration, thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.