Recursive reference issue in hashmap and list definition in implementing LRU Cache

[kapil2905]

Hi ppl :),

I am trying to implement a LRU Cache but stuck with the recursive definition for "list" and "unordered_map".

Since I am required to have a pair of (value, map iterator) in the list and a pair of (key, list iterator) in the map; I am not able to figure out how to define it :/

It is never ending recursion :/

std::list<int, std::unordered_map<int, std::unordered_map<int, std::list<int, std::unordered_map<............>>>>

Would be glad to know how can we tackle this type of problems.

[kapil2905]

EDIT :
The advantage of having the iterator to the map element in the list is that it would avoid lookup of map when I have to delete an entry from the list as well as the map when the cache is full and least recently used key has to be removed to make room for the new key.

std::unordered_map<int, std::list<std::pair<int, int>>::iterator> hMap;
std::list<std::pair<int, int>> List;
int Capacity;

class LRUCache
{
    public:
    LRUCache(int);
    int get(int key);
    void set(int key, int value);
};



void LRUCache::set(int key, int value) {
    auto mIt = hMap.find(key);
    if (Capacity <= 0)  return;
    
    if (List.size() < Capacity)
    {
        if (mIt != hMap.end())  List.erase(mIt->second);
        
        List.emplace_front(value, key);
        auto tIt = List.begin();
        if (mIt != hMap.end())  
        {
            List.erase(mIt->second);
            mIt->second = tIt;
        }
        else
        {
            hMap.emplace(key, tIt);
        }
    }
    else
    {
        hMap.erase(List.back().second); //the lookup needed here to find the entry to be erased can be 
        List.pop_back();                           //avoided if an iterator to the map entry is available as second pair
        auto mIt = hMap.find(key);           //element.
        List.emplace_front(value, key);
        auto tIt = List.begin();

        if (mIt != hMap.end())  mIt->second = tIt;
        else    hMap.emplace(key, tIt);
    }
}




LRUCache::LRUCache(int capacity) {
    hMap.clear();
    List.clear();
    Capacity = capacity;
}

int LRUCache::get(int key) {
    auto mIt = hMap.find(key);

    if (mIt == hMap.end())  return -1;
    return mIt->second->first;
}

Thanks :)

P.S. : Kindly ignore the class design issues and use of globals :)

[kapil2905]

This is an ill-formed question.
Please ignore.