C++ LRU 캐시 알고리즘 완벽 가이드 | Least Recently Used·O(1) 구현

LRU 알고리즘이란?

LRU(Least Recently Used)는 고정 크기 캐시가 꽉 찼을 때 가장 오랫동안 “사용되지 않은” 항목을 제거(evict) 하는 규칙입니다.

• 조회(get) 하거나 갱신(put) 하면 그 키는 “방금 사용됨” → 가장 최근 쪽으로 옮깁니다.
• 용량을 넘기면 가장 오래된(맨 뒤) 항목을 지웁니다.

운영체제 페이지 캐시, HTTP 프록시, DB 버퍼 풀, Redis의 allkeys-lru 정책, CPU/앱 레벨 객체 캐시 등에서 같은 아이디어가 쓰입니다.

왜 “해시 + 이중 연결 리스트”인가?

연산	요구사항	단독 unordered_map	단독 list
키로 값 찾기	O(1) 평균	✅	❌ O(n)
임의 키 삭제	O(1)	✅	❌
“최근 사용” 순서 유지·맨 앞 이동	O(1)	❌	✅ (splice)

둘을 함께 쓰면:

• std::list — 노드 순서 = MRU(맨 앞) … LRU(맨 뒤).
• std::unordered_map<K, list::iterator> — 키로 리스트 노드 위치를 바로 찾음.

리스트에서 노드를 떼어 맨 앞으로 붙이는 splice 는 포인터만 바꾸므로 O(1) 이고, 해당 키의 map 항목은 같은 반복자를 가리키므로 map을 수정할 필요가 없습니다.

flowchart LR
  subgraph list["std list (앞=MRU, 뒤=LRU)"]
    A["(k3,v3)"] --> B["(k1,v1)"] --> C["(k2,v2)"]
  end
  subgraph map["std unordered_map"]
    k3 --> A
    k1 --> B
    k2 --> C
  end

완전한 C++ 구현 (템플릿)

키 K는 std::hash<K> 및 operator== 가 가능해야 합니다. 값 타입 V는 복사·이동 가능하다고 가정합니다.

#include <cstddef>
#include <list>
#include <optional>
#include <stdexcept>
#include <unordered_map>
#include <utility>

template <typename K, typename V, typename Hash = std::hash<K>>
class LRUCache {
public:
  explicit LRUCache(std::size_t capacity) : capacity_(capacity) {
    if (capacity_ == 0) {
      throw std::invalid_argument("LRUCache: capacity must be > 0");
    }
  }

  /** 키가 없으면 std::nullopt */
  std::optional<V> get(const K& key) {
    auto it = index_.find(key);
    if (it == index_.end()) return std::nullopt;

    // 최근 사용: 해당 노드를 맨 앞으로
    items_.splice(items_.begin(), items_, it->second);
    return it->second->second;
  }

  void put(const K& key, V value) {
    auto it = index_.find(key);
    if (it != index_.end()) {
      it->second->second = std::move(value);
      items_.splice(items_.begin(), items_, it->second);
      return;
    }

    if (items_.size() >= capacity_) {
      evict_lru();
    }

    items_.emplace_front(key, std::move(value));
    index_[key] = items_.begin();
  }

  std::size_t size() const noexcept { return items_.size(); }
  std::size_t capacity() const noexcept { return capacity_; }

private:
  using Item = std::pair<K, V>;
  using ItemList = std::list<Item>;
  using Iterator = typename ItemList::iterator;

  void evict_lru() {
    if (items_.empty()) return;
    const K& victim = items_.back().first;
    index_.erase(victim);
    items_.pop_back();
  }

  std::size_t capacity_;
  ItemList items_;
  std::unordered_map<K, Iterator, Hash> index_;
};

사용 예시

#include <iostream>
#include <string>

int main() {
  LRUCache<int, std::string> cache(2);
  cache.put(1, "a");
  cache.put(2, "b");
  cache.get(1);           // 1이 최근 사용
  cache.put(3, "c");      // 용량 2 → LRU인 키 2 제거

  std::cout << cache.get(2).has_value() << '\n';  // 0 (없음)
  std::cout << cache.get(1).value() << '\n';      // a
  std::cout << cache.get(3).value() << '\n';      // c
}

동작을 단계로 따라가기 (put)

1. 키가 이미 있으면 → 값만 갱신하고 splice로 맨 앞.
2. 없고 자리가 있으면 → emplace_front 후 index_[key] = begin().
3. 없고 꽉 찼으면 → 맨 뒤(LRU) 키를 index_와 items_에서 제거 → 새 항목을 앞에 삽입.

get 은 값을 찾으면 반드시 splice로 맨 앞으로 옮겨야 “최근 사용”이 맞습니다.

시간 복잡도

• get / put (기존 키) — 해시 탐색 평균 O(1), splice O(1).
• put (신규 키, eviction) — LRU 하나 pop_back + map erase O(1) 평균.

해시 충돌이 많아지면 unordered_map 이 한 버킷에 몰려 최악에 가까워질 수 있으므로, 키가 많으면 reserve(capacity_) 로 재할당을 줄이는 것이 좋습니다.

// 생성자에서
index_.reserve(capacity_ * 2);  // 부하율 여유

흔한 실수

1. splice 없이 “순서만” 바꾸려 함

맵만 갱신하고 리스트 순서를 안 바꾸면 LRU 판별이 틀어집니다. get/put 모두에서 최근 사용이면 맨 앞으로 옮겨야 합니다.

2. 잘못된 반복자 저장

list가 재할당으로 노드 주소가 바뀌는 컨테이너는 아니지만, 해당 노드를 erase한 뒤 그 반복자를 map에 남기면 UB입니다. eviction 시에는 맨 뒤 노드의 키로 map만 먼저 지우고 pop_back 순서를 지키세요.

3. 용량 0

위 구현은 생성자에서 예외를 던집니다. “0이면 캐시 비활성” 같은 정책이면 별도 분기가 필요합니다.

4. 스레드 안전성

위 클래스는 스레드 안전하지 않습니다. 여러 스레드에서 쓰려면 std::mutex 로 get/put 전체를 감싸거나, 샤딩된 캐시 등을 검토하세요.

다른 정책과 한 줄 비교

정책	제거 대상	구현 난이도(개략)
LRU	가장 오래 사용 안 함	해시 + 리스트 O(1)
FIFO	먼저 들어온 것	큐 + 맵 가능
LFU	참조 횟수 최소	힙·추가 맵 등으로 무거워지기 쉬움

실무에서는 LRU 또는 TTL + LRU 조합이 많습니다.

정리

• LRU는 최근성을 기준으로 캐시를 비우는 대표 정책입니다.
• C++에서는 std::list + std::unordered_map<키, list::iterator> 가 정석 패턴입니다.
• splice 로 MRU 갱신, 맨 뒤 제거로 LRU eviction 을 O(1)에 가깝게 유지합니다.

더 넓은 맥락(커스텀 자료구조 시리즈, greedy와의 관계)은 relatedPosts에 연결된 글을 참고하면 좋습니다.

관련 글

• C++ 캐시 교체 알고리즘 총정리 | FIFO·LFU·Clock·MRU·OPT와 LRU 비교
• 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
• C++ map vs unordered_map 심층 비교 |
• C++ 시리즈 전체 목차
• C++ 기초 문법
• C++ STL 컨테이너