Least Recently Used

생각의 흐름 -> 접근 방식

1. List는 삽입 삭제 -> O(1)임
2. Search -> O(n)
3. 그럼 Search가 O(1)인 자료구조를 사용하자
4. Hash에 각 요소의 주소값을 넣어두자

코드

#include <iostream>
#include <list>
#include <unordered_map>

int main()
{
    int cache_capacity, input_size;
    std::cin >> cache_capacity >> input_size;

    std::list<int> cache;
    std::unordered_map<int, std::list<int>::iterator> hash_table;

    for(int i = 0; i < input_size; ++i)
    {
        int input;
        std::cin >> input;

        // hit
        if(hash_table.find(input) != hash_table.end())
        {
            auto it = hash_table[input];
            cache.erase(it);
            cache.push_front(input);
            hash_table[input] = cache.begin();
            continue;
        }
        
        // 한계값 넘어가면 퇴출
        if(cache.size() == cache_capacity)
        {
            auto del = cache.back();
            hash_table.erase(del);
            cache.pop_back();
        }

        // 리스트에 최신거 업데이트
        cache.push_front(input);
        hash_table[input] = cache.begin();
    }

    for(auto data : cache)
    {
        std::cout << data << " ";
    }
}