C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시·Skip List [#54-2]
![C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시·Skip List [#54-2]](/og/s/cpp-series-54-2-data-structures.webp)
이 글의 핵심
STL로 부족할 때 직접 구현하는 자료구조. 충돌 처리, 자동완성, 캐시 eviction, 정렬된 삽입 삭제. 문제 시나리오, 완전한 구현, 흔한 실수, 성능 비교, 프로덕션 패턴.
들어가며: “std::unordered_map으로 안 되는 경우"
"캐시 크기 제한이 필요한데, 오래된 항목을 자동으로 지우려면?”
C++ STL은 강력하지만, 모든 상황을 커버하지는 못합니다. std::unordered_map은 크기 제한이 없고, std::map은 O(log n)이라 대량 검색에 부담됩니다. 자동완성을 구현하려면 접두사 검색이 필요한데, STL에는 트라이가 없습니다.
비유하면: “일반 도로(map)와 고속도로(unordered_map)“가 있는데, LRU 캐시는 “주차장이 꽉 차면 가장 오래된 차를 내보내는 주차장”이고, 트라이는 “단어의 한 글자씩 따라가는 나무”입니다.
아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
// 실행 예제
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 이상
실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.
목차
1. 문제 시나리오
시나리오 1: 캐시 크기 제한 + 오래된 항목 자동 제거 (LRU)
상황: API 응답을 캐시하는데, 메모리가 100MB로 제한되어 있습니다. 가장 최근에 사용한 1만 개만 유지하고, 오래된 것은 자동으로 제거해야 합니다.
잘못된 접근:
다음은 간단한 cpp 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ❌ 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” 등을 제안해야 합니다.
잘못된 접근:
아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ❌ 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의 기본 해시 품질이 구현체마다 다름올바른 접근:
아래 코드는 cpp를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ✅ 커스텀 해시 함수
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)입니다.
잘못된 접근:
아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ❌ 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의 기본 버킷 수가 너무 커서 메모리를 초과합니다.
해결: 작은 초기 버킷 수를 지정하고, 로드 팩터를 조정합니다.
다음은 간단한 cpp 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ✅ 메모리 제한된 환경
std::unordered_map<int, int> small_map;
small_map.reserve(100); // 100개만 저장 예정
small_map.max_load_factor(2.0f); // 버킷당 2개까지 허용2. 해시테이블 완전 구현
2.1 개요
체이닝(Chaining) 방식: 버킷 배열 + 각 버킷에 연결 리스트. 충돌 시 같은 버킷에 리스트로 추가합니다.
아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 완전한 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 사용 예시
아래 코드는 cpp를 사용한 구현 예제입니다. 조건문으로 분기 처리를 수행합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
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까지의 경로가 하나의 단어입니다. 접두사 검색에 최적입니다.
아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 완전한 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 사용 예시
아래 코드는 cpp를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 = 가장 오래됨)
아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 완전한 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 사용 예시
아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
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) 기대 시간을 달성합니다. 균형 트리보다 구현이 단순합니다.
다음은 mermaid를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 완전한 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 중에 기존 이터레이터를 사용하면 크래시.
아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ❌ 잘못된 예
for (auto it = map_.begin(); it != map_.end(); ++it) {
if (condition(it)) {
insert(new_key, new_val); // rehash 발생 가능!
// it 무효화 - UB
}
}해결법:
아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ✅ 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_에서 해당 키를 제거해야 합니다.
다음은 간단한 cpp 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ✅ 올바른 순서
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 시 검사.
다음은 간단한 cpp 코드 예제입니다. 조건문으로 분기 처리를 수행합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
void insert(const std::string& word) {
if (word.empty()) return; // 또는 예외
// ...
}에러 4: 해시 함수 품질 - 충돌 과다
증상: 해시테이블 성능이 급격히 저하 (체인이 매우 길어짐).
다음은 간단한 cpp 코드 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ❌ 나쁜 해시 - 모든 키가 같은 버킷으로
struct BadHash {
size_t operator()(int x) const { return 1; }
};해결법: 비트 조합, 소수 곱셈 등으로 분산.
아래 코드는 cpp를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ✅ 개선된 해시
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로 힙에 할당하고, 컨테이너에 보관.
아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
// ✅ 올바른 예
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 선택 가이드
아래 코드는 mermaid를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
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 캐시
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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_에서도 제거하는 콜백이 필요합니다.
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 트라이 + 빈도수 (자동완성 순위)
다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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
다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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, 메트릭 |
핵심 원칙:
- STL 우선 -
unordered_map,map으로 해결되면 사용 - 요구사항 정확히 - 크기 제한, 접두사, k번째 등
- 측정 후 선택 - 벤치마크로 검증
- 반복자/포인터 무효화 주의
자주 묻는 질문 (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를 직접 구현할 수 있습니다.