LRU Cache--LeetCode

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

思路：LRU这里涉及是用向量记录内存地址，使用Map映射key和相应Key在向量中的映射，最前面的永远都是最新的，如果内存没有使用完，使用新的内存，如果使用完了，从第一个内存更新，然后将第一块内存放到最后一块中，需要注意的是这里需要map的信息。

class LRUCache{
public:
    LRUCache(int capacity) {
       m_capacity=capacity;
       m_size =0;
       for(int i=0;i<capacity;i++)
       {
         int* temp = (int*)malloc(sizeof(int));
         *temp =0;
         m_cache.push_back(temp);                    
       }
         
    }
    
    int get(int key) {
        map<int,int>::iterator itr=m_hash.find(key);
       
        if(itr == m_hash.end())
          return -1;
        else
          return *(m_cache[itr->second]);
    }
    
    void set(int key, int value) {
       map<int,int>::iterator itr=m_hash.find(key);
       map<int,int>::iterator index;
       if(itr == m_hash.end()) //没有找到 
       {
           if(m_size < m_capacity)
           {
              *m_cache[m_size] = value;
              m_hash.insert(pair<int,int>(key,m_size));
              m_size++;
           }
           else
           {
              for(index=m_hash.begin();index!=m_hash.end();index++)
               if(index->second ==0)
                  itr = index;
               else
                  index->second--;           
              m_hash.erase(itr);
              int* temp = m_cache[0];
              m_cache.erase(m_cache.begin());
              *temp = value;
              m_cache.push_back(temp);
              m_hash.insert(pair<int,int>(key,m_cache.size()-1)); 
           }   
       }
       else
       {
          int* temp = m_cache[itr->second];
          *m_cache[itr->second] = value;
          m_cache.erase(m_cache.begin()+itr->second);
          m_cache.push_back(temp);
          for(index=m_hash.begin();index != m_hash.end();index++)
             if(index->second > itr->second)
               index->second--;
          itr->second =  m_cache.size()-1;
       }   
    }
    ~LRUCache()
    {
       for(int i=0;i<m_capacity;i++)
         free(m_cache[i]);
    }
    private:
            int m_capacity;
            int m_size;
            vector<int*> m_cache;
            map<int,int> m_hash;
};

LRU Cache--LeetCode

原文：http://blog.csdn.net/yusiguyuan/article/details/45039255