태그: LRU
3편
-
C++ 캐시 교체 알고리즘: FIFO·LRU·LFU·Clock·MRU·OPT 구현과 비교
FIFO·LRU·LFU·MRU·Random·Clock·OPT 캐시 교체 정책의 동작 원리와 시간 복잡도를 비교하고, FIFO·LRU·Clock 캐시를 C++로 구현한 뒤 Redis 정책, OS 페이지 교체, CDN의 LFU 변형과 연결해 설명합니다.
-
C++로 O(1) LRU 캐시 만들기: unordered_map + list, splice, 흔한 반복자 실수
unordered_map에 list 반복자를 저장하고 splice로 노드를 앞으로 옮겨 get과 put을 모두 O(1)로 처리하는 LRU 캐시를 C++ 템플릿으로 구현합니다. 용량 초과 시 eviction 순서와 용량 0 같은 경계 조건도 다룹니다.
-
C++ 자료구조 구현 실습: 해시테이블, 트라이 자동완성, O(1) LRU 캐시, Skip List 성능 비교
std::unordered_map만으로 부족할 때 직접 만드는 자료구조입니다. 체이닝과 개방 주소법 해시테이블, 자동완성용 트라이, O(1) LRU 캐시, Skip List를 구현하고 rehash 반복자 무효화 같은 함정을 함께 다룹니다.