C++로 O(1) LRU 캐시 만들기: unordered_map + list, splice, 흔한 반복자 실수

LRU 알고리즘이란?

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

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

운영체제 페이지 캐시, HTTP 프록시, DB 버퍼 풀, Redis의 allkeys-lru 정책, CPU/앱 레벨 객체 캐시 등에서 같은 아이디어가 사용됩니다. 다만 이런 시스템 대부분은 교과서적인 LRU를 그대로 쓰지 않습니다. Redis는 모든 키를 연결 리스트로 관리하는 대신 몇 개를 무작위로 뽑아 그중 가장 오래된 키를 지우는 근사 LRU를 쓰고, 리눅스 페이지 캐시는 active/inactive 두 리스트로 나눈 변형을 씁니다. 정확한 LRU는 접근할 때마다 공유 자료구조를 수정해야 하므로, 동시성이 높은 환경에서는 그 비용을 줄이려고 정확도를 조금 포기하는 것입니다. 이 글의 구현은 단일 스레드에서 정확한 LRU가 필요할 때, 그리고 코딩 테스트(LeetCode 146번 같은)에서 요구하는 형태의 기준 구현입니다.

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

연산	요구사항	단독 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

std::map(레드블랙 트리)에 “마지막 접근 시각”을 값으로 저장하는 방법도 떠올릴 수 있지만, 그러면 eviction 대상을 찾으려고 전체를 훑거나 시각 기준 인덱스를 하나 더 두어야 해서 O(log n)이 됩니다. 우선순위 큐도 “이미 들어 있는 원소의 우선순위를 올리는” 연산을 표준 라이브러리가 지원하지 않습니다. 결국 “임의 위치의 원소를 O(1)에 떼어 맨 앞으로 붙인다”는 요구를 만족하는 표준 컨테이너는 std::list뿐이고, 그 위치를 O(1)에 찾아 주는 역할을 해시 맵이 맡는 구조입니다.

대가는 메모리입니다. 항목 하나마다 list 노드(앞뒤 포인터 2개 + pair<K,V>)와 해시 맵 노드(다음 포인터 + 키 + 반복자)가 따로 할당되고, 키가 두 번 저장됩니다. int 키라면 문제가 없지만 긴 std::string 키를 수백만 개 담으면 키 복사본과 노드 할당 오버헤드가 값보다 커질 수 있습니다. 이런 경우에는 맵의 키를 list 노드 안의 키를 가리키는 std::string_view로 두거나, Boost.Intrusive처럼 노드에 링크를 내장하는 방식으로 할당을 한 번으로 줄이는 최적화를 고려합니다.

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

키 K는 std::hash<K> 및 operator== 가 가능해야 합니다. 값 타입 V는 복사·이동 가능하다고 가정합니다. get이 std::optional<V>로 값의 복사본을 돌려주는 점도 설계상의 선택입니다. 포인터나 참조를 돌려주면 복사 비용은 없지만, 다음 put이 그 항목을 evict하는 순간 호출자가 들고 있던 참조가 댕글링이 됩니다. 값이 크다면 V를 std::shared_ptr<T>로 두어 복사를 포인터 복사로 바꾸는 편이 안전합니다.

#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로 맨 앞으로 옮겨야 “최근 사용”이 맞습니다.

3단계에서 eviction을 삽입보다 먼저 하는 순서도 의미가 있습니다. 삽입을 먼저 하면 잠깐 동안 capacity + 1개가 되는데, 용량이 1인 캐시에서는 방금 넣은 항목과 지울 항목을 헷갈려 새 항목을 지우는 버그가 나기 쉽습니다. 또 put의 키가 이미 있을 때는 eviction이 일어나면 안 되므로, 존재 여부 검사를 용량 검사보다 앞에 두어야 합니다. 이 순서를 바꾸면 꽉 찬 캐시에서 기존 키를 갱신할 때 엉뚱한 항목 하나가 사라집니다.

시간 복잡도

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

unordered_map은 원소 수가 bucket_count × max_load_factor를 넘으면 전체를 재해시하는데, 이때 한 번의 put이 O(n)이 되어 지연이 튑니다. 캐시는 최대 크기를 미리 알고 있으므로 생성자에서 reserve(capacity_) 를 호출해 두면 재해시가 일어나지 않습니다. reserve(n)은 이미 max_load_factor를 고려해 n개를 담을 버킷 수를 잡으므로 2배로 부풀릴 필요는 없습니다.

// 생성자에서
index_.reserve(capacity_);  // capacity_개까지 재해시 없음 (max_load_factor 반영됨)

해시 충돌로 한 버킷에 키가 몰리는 문제는 reserve로 해결되지 않습니다. 이것은 해시 함수의 품질 문제이고, 외부 입력을 키로 쓰는 서버라면 의도적으로 충돌을 유발하는 입력(hash flooding)도 고려해야 합니다.

내부 동작 원리: 왜 splice 한 번이 O(1)인가

std::list는 노드 기반 이중 연결 리스트입니다. splice는 노드 객체의 포인터만 재배선하므로 키·값 페이로드를 복사하지 않습니다. unordered_map이 들고 있는 반복자는 같은 노드를 가리키는 핸들이므로, 노드가 맨 앞으로 옮겨져도 맵 엔트리를 갱신할 필요가 없습니다. 반대로 vector로 순서를 유지하려면 임의 위치 삽입·삭제가 평균적으로 O(n)에 가까워져 LRU의 O(1) 목표와 충돌합니다.

해시 테이블은 평균 O(1)이지만 최악 O(n)입니다. 키 분포가 나쁘거나 재해시가 잦으면 지연이 튀므로, reserve로 재할당을 줄이고, 좋은 해시 함수·키 타입을 쓰는 것이 운영 체크포인트입니다.

프로덕션 패턴

• 샤딩: 멀티스레드 환경에서 단일 전역 LRU 대신 키 해시 샤드별로 캐시 인스턴스를 나누고 샤드 락을 잡으면 경합이 줄어듭니다.
• TTL 혼합: LRU만으로는 “시간 기반 만료”가 없으므로, 엔트리에 expires_at을 두고 get 시 만료를 먼저 확인하거나, 백그라운드 스윕을 병행합니다.
• 메모리 상한: 값 타입이 크면 바이트 예산을 기준으로 capacity를 잡으며, eviction 시 바이트 합계를 줄이는 가중 LRU로 확장합니다.
• 통계: 히트율·eviction 횟수·평균 리스트 길이를 노출하면 용량 튜닝이 쉬워집니다.

트러블슈팅

증상	가능 원인	조치
간헐적 크래시	erase 후 반복자 사용, 잘못된 splice 대상	모든 핸들러를 동일 연산 순서로 검토
예상보다 느림	해시 최악 경우, 재할당	reserve, 키 분포·std::hash 특수화 검토
LRU 순서가 어긋남	get 후 splice 누락	조회·갱신 경로 모두에서 MRU 갱신 확인
스레드 레이스	단일 락 없이 공유	mutex로 get/put 직렬화 또는 샤딩

흔한 실수

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

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

잘못된 반복자 저장

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

이 순서가 중요한 이유는 evict_lru의 const K& victim = items_.back().first;가 list 노드 안의 키를 참조로 잡기 때문입니다. pop_back()을 먼저 호출하면 노드가 해제되어 victim이 댕글링 참조가 되고, 그 뒤의 index_.erase(victim)은 해제된 메모리를 읽습니다. 이런 버그는 디버그 빌드에서는 해제된 메모리가 그대로 남아 있어 멀쩡히 동작하다가, 릴리스 빌드나 다른 할당자에서 엉뚱한 키가 지워지는 식으로 나타나서 찾기 어렵습니다. AddressSanitizer(-fsanitize=address)로 테스트를 돌리면 heap-use-after-free로 바로 잡힙니다.

list 대신 std::vector나 std::deque로 바꿔 보려는 시도도 같은 이유로 실패합니다. vector는 삽입 시 재할당으로 모든 반복자가 무효화되고, deque는 중간 삽입·삭제에서 반복자가 무효화되므로 map에 저장한 위치 정보를 믿을 수 없게 됩니다.

용량 0

위 구현은 생성자에서 예외를 던집니다. “0이면 캐시 비활성” 같은 정책이면 별도 분기가 필요합니다. 예외를 던지지 않고 용량 0을 허용하면 put에서 evict_lru()가 빈 리스트를 보고 그냥 반환한 뒤 항목을 넣으므로, “용량 0인데 항목 1개가 들어 있는” 상태가 됩니다. 설정 파일에서 캐시 크기를 읽는 서비스라면 0이 “끄기”를 뜻하는지 오타인지부터 정해 두는 것이 좋습니다.

스레드 안전성

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

처음 멀티스레드로 옮길 때 흔히 하는 실수가 “get은 읽기니까 std::shared_mutex의 공유 락이면 충분하다”고 생각하는 것입니다. LRU의 get은 splice로 리스트를 수정하므로 읽기 연산이 아닙니다. 공유 락으로 여러 스레드가 동시에 splice하면 리스트 포인터가 꼬여 무한 루프나 크래시로 이어집니다. 그래서 LRU는 읽기 비중이 높아도 배타 락이 필요하고, 이것이 경합이 심할 때 샤딩이나 근사 LRU(접근 시 플래그만 세우는 CLOCK 등)로 넘어가는 이유입니다.

다른 정책과 한 줄 비교

정책	제거 대상	구현 난이도(개략)
LRU	가장 오래 사용 안 함	해시 + 리스트 O(1)
FIFO	먼저 들어온 것	큐 + 맵 가능
LFU	참조 횟수 최소	빈도별 리스트로 O(1) 가능하지만 구현이 복잡

실무에서는 LRU 또는 TTL + LRU 조합이 많습니다. LRU가 약한 대표적인 경우는 한 번만 읽히는 대량 스캔입니다. 배치 작업이 테이블 전체를 한 번 훑으면 그 키들이 모두 “최근 사용”이 되어, 정작 자주 쓰이던 항목이 전부 밀려납니다. 이 문제 때문에 DB 버퍼 풀은 새로 읽은 페이지를 리스트 중간에 넣는 midpoint 삽입(MySQL InnoDB)을 쓰고, 애플리케이션 캐시 라이브러리(Caffeine 등)는 빈도와 최근성을 함께 보는 W-TinyLFU 같은 정책을 씁니다.

자주 묻는 질문 (FAQ)

Q. list의 splice로 노드를 옮기면 map에 저장해 둔 반복자가 무효화되지 않나요?

A. std::list::splice는 노드를 복사하거나 새로 할당하지 않고 연결 포인터만 바꾸기 때문에, 옮겨진 원소를 가리키는 반복자와 참조는 그대로 유효합니다. 그래서 get에서 노드를 맨 앞으로 옮긴 뒤에도 unordered_map에 저장한 반복자를 갱신할 필요가 없습니다. 반대로 eviction에서 erase한 노드의 반복자는 무효가 되므로 map에서도 같은 키를 반드시 지워야 하며, list 대신 vector나 deque를 쓰면 이 전제가 성립하지 않는다는 점이 본문의 잘못된 반복자 저장 실수와 연결됩니다.

---

같이 보면 좋은 글

• C++ 캐시 교체 알고리즘: FIFO·LRU·LFU·Clock·MRU·OPT 구현과 비교
• 배열과 연결 리스트
• C++ map vs unordered_map 심층 비교
• C++ 시리즈 전체 목차
• C++ map·unordered_map·flat_map
• C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화
• C++ 캐시 최적화 실전 | 캐시 친화적 구조·프리페치·False Sharing·AoS vs SoA 가이드