C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시·Skip List

들어가며: “std::unordered_map으로 안 되는 경우"

"캐시 크기 제한이 필요한데, 오래된 항목을 자동으로 지우려면?”

C++ STL은 강력하지만, 모든 상황을 커버하지는 못한다. std::unordered_map은 크기 제한이 없으며, std::map은 O(log n)이라 대량 검색에 부담된다. 자동완성을 구현하려면 접두사 검색이 필요한데, STL에는 트라이가 없다. 비유하면: “일반 도로(map)와 고속도로(unordered_map)“가 있는데, LRU 캐시는 “주차장이 꽉 차면 가장 오래된 차를 내보내는 주차장”이으며, 트라이는 “단어의 한 글자씩 따라가는 나무”입니다.

flowchart TD
  subgraph problem[❌ STL 한계]
    P1[캐시 크기 제한?] --> P2[unordered_map은 무제한]
    P3[접두사 검색?] --> P4[map은 전체 키만]
    P5[정렬된 삽입/삭제 O(log n)?] --> P6[vector는 O(n)]
  end
  subgraph solution[✅ 커스텀 자료구조]
    S1[LRU 캐시] --> S2[해시 + 이중 연결 리스트]
    S3[트라이] --> S4[접두사 O(m) 검색]
    S5[Skip List] --> S6[균형 트리 대안]
  end

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 해시테이블·트라이·LRU 캐시·Skip List의 완전한 구현, 자주 하는 실수, 성능 비교, 프로덕션 패턴까지 다룬다. 이 글을 읽으면

• STL로 해결되지 않는 상황을 파악할 수 있습니다.
• 해시테이블 충돌 처리, 트라이, LRU 캐시를 직접 구현할 수 있습니다.
• 흔한 실수를 피하고 성능을 최적화할 수 있습니다. 요구 환경: C++17 이상

---

1. 문제 시나리오

시나리오 1: 캐시 크기 제한 + 오래된 항목 자동 제거 (LRU)

상황: API 응답을 캐시하는데, 메모리가 100MB로 제한되어 있습니다. 가장 최근에 사용한 1만 개만 유지하며, 오래된 것은 자동으로 제거해야 합니다. 잘못된 접근:

// ❌ std::unordered_map - 크기 제한 없음, "오래된 것" 판단 불가
std::unordered_map<std::string, Response> cache;
cache[/api/users/1] = fetchUser(1);  // 무한히 쌓임!
// 언제 뭘 지울지 알 수 없음

문제점: unordered_map은 삽입 순서를 기억하지 않습니다. “가장 오래 사용하지 않은” 항목을 O(1)에 찾을 수 없습니다. 올바른 접근: LRU 캐시 (해시 + 이중 연결 리스트) - 섹션 4 참조

시나리오 2: 접두사로 검색 (자동완성)

상황: 검색창에 “app”을 입력하면 “apple”, “application”, “apply” 등을 제안해야 합니다. 잘못된 접근:

// ❌ std::map - 전체 키만 검색, 접두사 검색 O(n)
// 실행 예제
std::map<std::string, int> words;
for (auto it = words.lower_bound("app"); it != words.end(); ++it) {
    if (it->first.substr(0, 3) != "app") break;  // 전체 순회 가능성
    suggest(it->first);
}

문제점: lower_bound는 “app” 이상인 첫 키를 찾지만, “appzzz” 이후의 모든 키도 순회합니다. 접두사가 “app”인 것만 O(접두사 길이)에 찾을 수 없습니다. 올바른 접근: 트라이 - 섹션 3 참조

시나리오 3: 커스텀 키에 대한 해시 (복합 키)

상황: (user_id, item_id) 쌍을 키로 쓰는데, std::pair의 기본 해시가 충돌을 많이 일으킵니다. 잘못된 접근:

// ❌ std::pair 해시 - 단순 XOR은 충돌 많음
std::unordered_map<std::pair<int,int>, int> cache;
// pair의 기본 해시 품질이 구현체마다 다름

올바른 접근:

// ✅ 커스텀 해시 함수
struct PairHash {
    size_t operator()(const std::pair<int,int>& p) const {
        return std::hash<int>{}(p.first) ^ (std::hash<int>{}(p.second) << 16);
    }
};
std::unordered_map<std::pair<int,int>, int, PairHash> cache;

---

시나리오 4: 정렬된 삽입/삭제 + 인덱스 접근

상황: 실시간 랭킹에서 순위가 자주 바뀌으며, “k번째” 요소에 O(log n)으로 접근해야 합니다. std::map은 k번째 접근이 O(n)입니다. 잘못된 접근:

// ❌ std::map - k번째 접근이 O(n)
std::map<int, std::string> ranking;
// 5번째 찾으려면 begin에서 5번 ++
auto it = ranking.begin();
std::advance(it, 4);  // O(k) - 느림!

올바른 접근: Skip List (또는 order statistic tree) - 섹션 5 참조

시나리오 5: 메모리 제약 환경에서의 해시테이블

상황: 임베디드에서 std::unordered_map의 기본 버킷 수가 너무 커서 메모리를 초과합니다. 해결: 작은 초기 버킷 수를 지정하며, 로드 팩터를 조정합니다.

// ✅ 메모리 제한된 환경
std::unordered_map<int, int> small_map;
small_map.reserve(100);  // 100개만 저장 예정
small_map.max_load_factor(2.0f);  // 버킷당 2개까지 허용

---

2. 해시테이블 완전 구현

2.1 개요

체이닝(Chaining) 방식: 버킷 배열 + 각 버킷에 연결 리스트. 충돌 시 같은 버킷에 리스트로 추가합니다.

flowchart LR
  subgraph buckets[버킷 배열]
    B0[0]
    B1[1]
    B2[2]
    B3[3]
  end
  B1 --> N1[key1→val1]
  N1 --> N2[key5→val5]
  B2 --> N3[key2→val2]

2.2 완전한 구현

#include <vector>
#include <list>
#include <optional>
#include <functional>
template<typename Key, typename Value, typename Hash = std::hash<Key>>
class HashTable {
public:
    explicit HashTable(size_t bucket_count = 16)
        : buckets_(bucket_count), size_(0) {}
    void insert(const Key& key, const Value& value) {
        if (load_factor() > 0.75f) rehash();
        size_t idx = hash_(key) % buckets_.size();
        for (auto& [k, v] : buckets_[idx]) {
            if (k == key) {
                v = value;
                return;
            }
        }
        buckets_[idx].emplace_back(key, value);
        ++size_;
    }
    std::optional<Value> find(const Key& key) const {
        size_t idx = hash_(key) % buckets_.size();
        for (const auto& [k, v] : buckets_[idx]) {
            if (k == key) return v;
        }
        return std::nullopt;
    }
    bool erase(const Key& key) {
        size_t idx = hash_(key) % buckets_.size();
        auto& chain = buckets_[idx];
        for (auto it = chain.begin(); it != chain.end(); ++it) {
            if (it->first == key) {
                chain.erase(it);
                --size_;
                return true;
            }
        }
        return false;
    }
    size_t size() const { return size_; }
    float load_factor() const {
        return static_cast<float>(size_) / buckets_.size();
    }
private:
    void rehash() {
        std::vector<std::list<std::pair<Key, Value>>> new_buckets(buckets_.size() * 2);
        for (auto& chain : buckets_) {
            for (auto& [k, v] : chain) {
                size_t idx = hash_(k) % new_buckets.size();
                new_buckets[idx].emplace_back(std::move(k), std::move(v));
            }
        }
        buckets_ = std::move(new_buckets);
    }
    std::vector<std::list<std::pair<Key, Value>>> buckets_;
    size_t size_;
    Hash hash_;
};

핵심 포인트

• 로드 팩터 0.75: 초과 시 rehash로 버킷 수 2배
• 체이닝: std::list로 충돌 처리
• 삽입 시 기존 키: 덮어쓰기 후 return

2.3 사용 예시

HashTable<std::string, int> ht;
ht.insert("apple", 1);
ht.insert("banana", 2);
ht.insert("apple", 3);  // 덮어쓰기
if (auto v = ht.find("apple")) {
    std::cout << "apple: " << *v << "\n";  // 3
}
ht.erase("banana");

---

3. 트라이 완전 구현

3.1 개요

트라이(Trie): 각 노드가 문자 하나를 나타내으며, 루트에서 leaf까지의 경로가 하나의 단어입니다. 접두사 검색에 최적입니다.

flowchart TD
  R[""] --> A[a]
  A --> P[p]
  P --> P1[p]
  P1 --> L1[l]
  L1 --> E1[e]
  P --> P2[p]
  P2 --> L2[l]
  L2 --> E2[y]
  A --> N[n]

3.2 완전한 구현

#include <unordered_map>
#include <string>
#include <vector>
class Trie {
public:
    Trie() : root_(std::make_unique<Node>()) {}
    void insert(const std::string& word) {
        Node* cur = root_.get();
        for (char c : word) {
            if (cur->children.find(c) == cur->children.end()) {
                cur->children[c] = std::make_unique<Node>();
            }
            cur = cur->children[c].get();
        }
        cur->is_end = true;
    }
    bool search(const std::string& word) const {
        Node* cur = root_.get();
        for (char c : word) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return false;
            cur = it->second.get();
        }
        return cur->is_end;
    }
    bool startsWith(const std::string& prefix) const {
        Node* cur = root_.get();
        for (char c : prefix) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return false;
            cur = it->second.get();
        }
        return true;
    }
    std::vector<std::string> getPrefixMatches(const std::string& prefix) const {
        std::vector<std::string> result;
        Node* cur = root_.get();
        for (char c : prefix) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return result;
            cur = it->second.get();
        }
        collectWords(cur, prefix, result);
        return result;
    }
private:
    struct Node {
        std::unordered_map<char, std::unique_ptr<Node>> children;
        bool is_end = false;
    };
    void collectWords(Node* node, const std::string& prefix,
                      std::vector<std::string>& result) const {
        if (node->is_end) result.push_back(prefix);
        for (const auto& [c, child] : node->children) {
            collectWords(child.get(), prefix + c, result);
        }
    }
    std::unique_ptr<Node> root_;
};

핵심 포인트

• insert: 각 문자마다 자식 노드 생성, 마지막에 is_end = true
• search: 단어 전체가 존재하는지
• startsWith: 접두사만 존재하는지
• getPrefixMatches: 접두사로 시작하는 모든 단어 수집

3.3 사용 예시

Trie trie;
trie.insert("apple");
trie.insert("application");
trie.insert("apply");
trie.insert("banana");
assert(trie.search("apple") == true);
assert(trie.startsWith("app") == true);
auto matches = trie.getPrefixMatches("app");
// matches: {"apple", "application", "apply"}

---

4. LRU 캐시 완전 구현

4.1 개요

LRU (Least Recently Used): 가장 오래 사용하지 않은 항목을 제거합니다. 해시테이블 + 이중 연결 리스트로 O(1) get/put을 구현합니다.

• 해시테이블: 키 → (값, 리스트 이터레이터) 매핑
• 이중 연결 리스트: 최근 사용 순서 (head = 최신, tail = 가장 오래됨)

flowchart LR
  subgraph list["이중 연결 리스트 (최신→오래됨)"]
    H[head] --> N1[k1:v1]
    N1 --> N2[k2:v2]
    N2 --> N3[k3:v3]
    N3 --> T[tail]
  end
  subgraph hash[해시테이블]
    M[k1→iter1]
    M2[k2→iter2]
    M3[k3→iter3]
  end

4.2 완전한 구현

#include <unordered_map>
#include <list>
#include <optional>
template<typename Key, typename Value>
class LRUCache {
public:
    explicit LRUCache(size_t capacity) : capacity_(capacity) {
        if (capacity_ == 0) capacity_ = 1;
    }
    std::optional<Value> get(const Key& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;
        // 최근 사용으로 이동: 리스트에서 제거 후 맨 앞에 삽입
        list_.splice(list_.begin(), list_, it->second);
        return it->second->second;
    }
    void put(const Key& key, const Value& value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }
        if (list_.size() >= capacity_) {
            // 가장 오래된 항목 제거 (tail)
            auto last = list_.back();
            map_.erase(last.first);
            list_.pop_back();
        }
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }
    size_t size() const { return list_.size(); }
    bool erase(const Key& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return false;
        list_.erase(it->second);
        map_.erase(it);
        return true;
    }
private:
    size_t capacity_;
    std::list<std::pair<Key, Value>> list_;
    std::unordered_map<Key, decltype(list_.begin())> map_;
};

핵심 포인트

• splice: O(1)에 노드를 다른 위치로 이동
• get 시: 해당 노드를 리스트 맨 앞으로 이동
• put 시 용량 초과: tail 제거 후 새 항목을 head에 추가

4.3 사용 예시

LRUCache<int, std::string> cache(2);
cache.put(1, "one");
cache.put(2, "two");
assert(cache.get(1).value() == "one");  // 1이 최근 사용됨
cache.put(3, "three");  // 2가 evict됨 (가장 오래됨)
assert(!cache.get(2).has_value());
assert(cache.get(1).value() == "one");
assert(cache.get(3).value() == "three");

---

5. Skip List 완전 구현

5.1 개요

Skip List: 여러 레벨의 연결 리스트로, 상위 레벨을 건너뛰며 검색해 O(log n) 기대 시간을 달성합니다. 균형 트리보다 구현이 단순합니다.

flowchart LR
  subgraph L3[레벨 3]
    H3[head] --> N30[30]
  end
  subgraph L2[레벨 2]
    H2[head] --> N20[10]
    N20 --> N30
  end
  subgraph L1[레벨 1]
    H1[head] --> N10[5]
    N10 --> N20
    N20 --> N25[25]
    N25 --> N30
    N30 --> N40[40]
  end

5.2 완전한 구현

#include <random>
#include <vector>
#include <optional>
template<typename Key, typename Value>
class SkipList {
    static constexpr int MAX_LEVEL = 16;
    static constexpr double P = 0.5;
public:
    SkipList() : level_(0) {
        head_ = std::make_unique<Node>(Key{}, Value{}, MAX_LEVEL);
    }
    void insert(const Key& key, const Value& value) {
        std::vector<Node*> update(MAX_LEVEL + 1);
        Node* cur = head_.get();
        for (int i = level_; i >= 0; --i) {
            while (cur->forward[i] && cur->forward[i]->key < key) {
                cur = cur->forward[i];
            }
            update[i] = cur;
        }
        int new_level = randomLevel();
        if (new_level > level_) {
            for (int i = level_ + 1; i <= new_level; ++i) {
                update[i] = head_.get();
            }
            level_ = new_level;
        }
        auto node = std::make_unique<Node>(key, value, new_level);
        for (int i = 0; i <= new_level; ++i) {
            node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = node.get();
        }
        nodes_.push_back(std::move(node));
    }
    std::optional<Value> find(const Key& key) const {
        Node* cur = head_.get();
        for (int i = level_; i >= 0; --i) {
            while (cur->forward[i] && cur->forward[i]->key < key) {
                cur = cur->forward[i];
            }
        }
        cur = cur->forward[0];
        if (cur && cur->key == key) return cur->value;
        return std::nullopt;
    }
    bool erase(const Key& key) {
        std::vector<Node*> update(MAX_LEVEL + 1);
        Node* cur = head_.get();
        for (int i = level_; i >= 0; --i) {
            while (cur->forward[i] && cur->forward[i]->key < key) {
                cur = cur->forward[i];
            }
            update[i] = cur;
        }
        cur = cur->forward[0];
        if (!cur || cur->key != key) return false;
        for (int i = 0; i <= level_; ++i) {
            if (update[i]->forward[i] != cur) break;
            update[i]->forward[i] = cur->forward[i];
        }
        while (level_ > 0 && !head_->forward[level_]) --level_;
        return true;
    }
private:
    struct Node {
        Key key;
        Value value;
        std::vector<Node*> forward;
        Node(const Key& k, const Value& v, int level)
            : key(k), value(v), forward(level + 1, nullptr) {}
    };
    int randomLevel() {
        int lvl = 0;
        static std::mt19937 rng{std::random_device{}()};
        static std::uniform_real_distribution<> dist(0, 1);
        while (dist(rng) < P && lvl < MAX_LEVEL) ++lvl;
        return lvl;
    }
    std::unique_ptr<Node> head_;
    int level_;
    std::vector<std::unique_ptr<Node>> nodes_;  // 소유권 관리
};

핵심 포인트

• randomLevel: 50% 확률로 레벨 증가, 평균 O(log n) 레벨
• insert: 각 레벨에서 삽입 위치 찾은 뒤, 새 노드 연결
• find: 상위 레벨부터 건너뛰며 하강

---

6. 자주 발생하는 에러와 해결법

에러 1: 해시테이블 rehash 시 반복자 무효화

증상: rehash 중에 기존 이터레이터를 사용하면 크래시.

// ❌ 잘못된 예
for (auto it = map_.begin(); it != map_.end(); ++it) {
    if (condition(it)) {
        insert(new_key, new_val);  // rehash 발생 가능!
        // it 무효화 - UB
    }
}

해결법:

// ✅ rehash 후 이터레이터 재획득
std::vector<Key> to_process;
for (auto it = map_.begin(); it != map_.end(); ++it) {
    if (condition(it)) to_process.push_back(it->first);
}
for (const auto& k : to_process) {
    insert(k, compute(k));
}

---

에러 2: LRU 캐시에서 map에 리스트 이터레이터 저장 시 무효화

증상: list::splice나 list::erase 후 map_에 저장된 이터레이터가 무효화될 수 있음. 해결법: splice는 노드를 이동할 뿐이므로 같은 리스트 내에서는 이터레이터가 유효합니다. 단, list::erase로 제거된 노드의 이터레이터는 무효화되므로, erase 전에 map_에서 해당 키를 제거해야 합니다.

// ✅ 올바른 순서
auto last = list_.back();
map_.erase(last.first);   // 먼저 map에서 제거
list_.pop_back();        // 그 다음 리스트에서 제거

---

에러 3: 트라이에서 빈 문자열 처리

증상: insert("") 시 root가 is_end가 되어, search("")가 true를 반환. 의도에 따라 다를 수 있음.

// ❌ 빈 문자열 insert 시
trie.insert("");  // root->is_end = true
trie.search("");  // true - 원하는 동작인가?

해결법: 빈 문자열을 허용하지 않는다면 insert 시 검사.

void insert(const std::string& word) {
    if (word.empty()) return;  // 또는 예외
    // ...
}

---

에러 4: 해시 함수 품질 - 충돌 과다

증상: 해시테이블 성능이 급격히 저하 (체인이 매우 길어짐).

// ❌ 나쁜 해시 - 모든 키가 같은 버킷으로
struct BadHash {
    size_t operator()(int x) const { return 1; }
};

해결법: 비트 조합, 소수 곱셈 등으로 분산.

// ✅ 개선된 해시
struct PairHash {
    size_t operator()(const std::pair<int,int>& p) const {
        size_t h1 = std::hash<int>{}(p.first);
        size_t h2 = std::hash<int>{}(p.second);
        return h1 ^ (h2 << 1);  // 또는 h1 * 31 + h2
    }
};

---

에러 5: Skip List에서 노드 소유권

증상: insert에서 Node를 스택에 생성하면 함수 반환 시 dangling pointer.

// ❌ 잘못된 예
Node node(key, value, new_level);
update[i]->forward[i] = &node;  // 함수 종료 시 UB

해결법: unique_ptr로 힙에 할당하며, 컨테이너에 보관.

// ✅ 올바른 예
auto node = std::make_unique<Node>(key, value, new_level);
Node* raw = node.get();
nodes_.push_back(std::move(node));
update[i]->forward[i] = raw;

---

에러 6: LRU 캐시 capacity 0

증상: capacity_ == 0일 때 put에서 list_.size() >= 0이 항상 참이 되어, 삽입 직후 제거되는 무한 루프 가능성. 해결법: 생성자에서 capacity_를 최소 1로 보장.

explicit LRUCache(size_t capacity) : capacity_(capacity) {
    if (capacity_ == 0) capacity_ = 1;
}

---

7. 성능 비교

7.1 자료구조별 연산 복잡도

자료구조	삽입	검색	삭제	접두사 검색	k번째 접근
std::unordered_map	O(1) 평균	O(1) 평균	O(1) 평균	❌	❌
std::map	O(log n)	O(log n)	O(log n)	부분 지원	O(n)
해시테이블 (체이닝)	O(1) 평균	O(1) 평균	O(1) 평균	❌	❌
트라이	O(m)	O(m)	O(m)	O(m)	❌
LRU 캐시	O(1)	O(1)	O(1)	❌	❌
Skip List	O(log n) 기대	O(log n) 기대	O(log n) 기대	❌	O(log n)
m = 키/접두사 길이

7.2 벤치마크 시나리오 (100만 연산)

시나리오	unordered_map	map	커스텀 해시테이블	LRU(1만)
삽입 100만	~200ms	~400ms	~250ms	~220ms
검색 100만 (존재)	~150ms	~350ms	~200ms	~180ms
삽입+검색 혼합	~180ms	~380ms	~230ms	~200ms
환경에 따라 차이 있음. 프로파일링 권장.

7.3 선택 가이드

flowchart TD
  Q[요구사항] --> A{크기 제한?}
  A -->|예| B[LRU 캐시]
  A -->|아니오| C{접두사 검색?}
  C -->|예| D[트라이]
  C -->|아니오| E{k번째 접근?}
  E -->|예| F[Skip List / order statistic tree]
  E -->|아니오| G[unordered_map / map]

---

8. 프로덕션 패턴

8.1 스레드 안전 LRU 캐시

#include <mutex>
template<typename Key, typename Value>
class ThreadSafeLRUCache {
public:
    explicit ThreadSafeLRUCache(size_t capacity) : cache_(capacity) {}
    std::optional<Value> get(const Key& key) {
        std::lock_guard<std::mutex> lock(mutex_);
        return cache_.get(key);
    }
    void put(const Key& key, const Value& value) {
        std::lock_guard<std::mutex> lock(mutex_);
        cache_.put(key, value);
    }
private:
    LRUCache<Key, Value> cache_;
    std::mutex mutex_;
};

---

8.2 TTL(Time-To-Live) 캐시

참고: 프로덕션에서는 LRU eviction 시 expiry_에서도 제거하는 콜백이 필요합니다.

#include <chrono>
template<typename Key, typename Value>
class TTLCache {
public:
    explicit TTLCache(size_t capacity, std::chrono::seconds ttl)
        : cache_(capacity), ttl_(ttl) {}
    std::optional<Value> get(const Key& key) {
        auto it = expiry_.find(key);
        if (it == expiry_.end()) return std::nullopt;
        if (std::chrono::steady_clock::now() > it->second) {
            cache_.erase(key);  // 간단화: LRU에 erase 추가 필요
            expiry_.erase(it);
            return std::nullopt;
        }
        return cache_.get(key);
    }
    void put(const Key& key, const Value& value) {
        cache_.put(key, value);
        expiry_[key] = std::chrono::steady_clock::now() + ttl_;
    }
private:
    LRUCache<Key, Value> cache_;
    std::chrono::seconds ttl_;
    std::unordered_map<Key, std::chrono::steady_clock::time_point> expiry_;
};

---

8.3 트라이 + 빈도수 (자동완성 순위)

class AutocompleteTrie {
public:
    void insert(const std::string& word, int freq = 1) {
        Node* cur = root_.get();
        for (char c : word) {
            if (!cur->children[c]) cur->children[c] = std::make_unique<Node>();
            cur = cur->children[c].get();
        }
        cur->is_end = true;
        cur->freq += freq;
    }
    std::vector<std::pair<std::string, int>> getTopSuggestions(
            const std::string& prefix, size_t k = 10) const {
        Node* cur = root_.get();
        for (char c : prefix) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return {};
            cur = it->second.get();
        }
        std::vector<std::pair<std::string, int>> candidates;
        collectWithFreq(cur, prefix, candidates);
        std::partial_sort(candidates.begin(),
            candidates.begin() + std::min(k, candidates.size()),
            candidates.end(),
             { return a.second > b.second; });
        candidates.resize(std::min(k, candidates.size()));
        return candidates;
    }
private:
    struct Node {
        std::unordered_map<char, std::unique_ptr<Node>> children;
        bool is_end = false;
        int freq = 0;
    };
    std::unique_ptr<Node> root_;
    // collectWithFreq 구현 생략
};

---

8.4 메트릭 수집 LRU

template<typename Key, typename Value>
class InstrumentedLRUCache {
public:
    explicit InstrumentedLRUCache(size_t capacity) : cache_(capacity) {}
    std::optional<Value> get(const Key& key) {
        ++get_count_;
        auto result = cache_.get(key);
        if (result) ++hit_count_;
        return result;
    }
    void put(const Key& key, const Value& value) {
        ++put_count_;
        cache_.put(key, value);
    }
    double hit_rate() const {
        return get_count_ == 0 ? 0.0
            : static_cast<double>(hit_count_) / get_count_;
    }
private:
    LRUCache<Key, Value> cache_;
    size_t get_count_ = 0, put_count_ = 0, hit_count_ = 0;
};

---

9. 구현 체크리스트

해시테이블

• 로드 팩터 임계값 설정 (0.75 권장)
• rehash 시 기존 이터레이터 사용 금지
• 커스텀 키 시 해시 품질 검증

트라이

• 빈 문자열 처리 정책
• 메모리: 자식이 없으면 노드 정리 (선택)

LRU 캐시

• capacity 0 방어
• splice 사용 시 이터레이터 유효성 확인
• evict 시 콜백 필요하면 확장

Skip List

• 노드 소유권 (unique_ptr 등)
• randomLevel 시드 고정 (재현성 필요 시)

공통

• 예외 안전성 (RAII)
• const 정확성
• 단위 테스트 (경계 조건)

---

정리

항목	핵심
문제 시나리오	캐시 제한, 접두사 검색, 커스텀 키, k번째 접근
해시테이블	체이닝, rehash, 로드 팩터
트라이	접두사 O(m), 자동완성
LRU	해시 + 이중 연결 리스트, splice O(1)
Skip List	다중 레벨, O(log n) 기대
흔한 에러	반복자 무효화, 해시 품질, capacity 0
성능	요구사항에 맞는 자료구조 선택
프로덕션	스레드 안전, TTL, 메트릭
핵심 원칙:

1. STL 우선 - unordered_map, map으로 해결되면 사용
2. 요구사항 정확히 - 크기 제한, 접두사, k번째 등
3. 측정 후 선택 - 벤치마크로 검증
4. 반복자/포인터 무효화 주의

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 캐싱 시스템(LRU), 검색 자동완성(트라이), 커스텀 해시가 필요한 키, 정렬된 시퀀스의 k번째 접근(Skip List) 등 STL로 해결하기 어려운 상황에서 활용합니다.

Q. 선행으로 읽으면 좋은 글은?

A. STL map/set, 알고리즘 선택, 트리 알고리즘을 먼저 익히면 좋습니다.

Q. 더 깊이 공부하려면?

A. 《Introduction to Algorithms》의 해시·트리 장, LeetCode 146 (LRU Cache), 208 (Implement Trie), cppreference의 unordered_map 구현 노트를 참고하세요. 한 줄 요약: STL 한계를 넘어서는 해시테이블·트라이·LRU·Skip List를 직접 구현할 수 있습니다.

관련 글

• C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시 [#54-2]
• C++ vector 기초 완벽 가이드 | 초기화·연산·용량 관리와 실전 패턴
• C++ vector vs list vs deque

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시 [#54-2]
• C++ map·set 완벽 가이드 | ordered vs unordered· 커스텀 키
• C++ 트리 알고리즘 완벽 가이드 | 세그먼트 트리·펜윅 트리·트라이 [실전]

---

이 글에서 다루는 키워드 (관련 검색어)

C++, 자료구조, 해시테이블, 트라이, LRU, SkipList 등으로 검색하시면 이 글이 도움이 됩니다.