C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시 [#54-2]
![C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시 [#54-2]](/og/s/cpp-series-54-2-custom-data-structures.webp)
이 글의 핵심
C++ 자료구조 직접 구현: 해시테이블 충돌 처리, 트라이 자동완성, LRU 캐시, Skip List. 문제 시나리오, 완전한 예제, 흔한 에러, 성능 비교, 프로덕션 패턴. std::map은 균형 이진 트리 기반이라 조회가 O(log n)입니다. 수백만 건의 키를 다룰 때 O(1) 해시테이블이 필요합니다. 검색창 자동완성처럼 접두사로 검색하려면 트라이(Trie)가 적합하고,.
들어가며: std::map만으로는 부족할 때
”키-값 조회가 O(log n)이라 느려요” / “접두사 검색이 필요해요” / “캐시 용량 제한이 있어요”
std::map은 균형 이진 트리 기반이라 조회가 O(log n)입니다. 수백만 건의 키를 다룰 때 O(1) 해시테이블이 필요합니다. 검색창 자동완성처럼 접두사로 검색하려면 트라이(Trie)가 적합하고, 최근 사용 항목만 유지하는 LRU 캐시는 std::map만으로 구현하기 까다롭습니다. 이 글에서는 해시테이블·트라이·LRU 캐시·Skip List를 직접 구현하면서, 문제 시나리오부터 프로덕션 패턴까지 다룹니다.
요구 환경: C++17 이상
이 글을 읽으면:
- 해시테이블 충돌 처리(체이닝, 개방 주소법)를 이해할 수 있습니다.
- 트라이로 자동완성·접두사 검색을 구현할 수 있습니다.
- LRU 캐시를 O(1)에 동작하도록 구현할 수 있습니다.
- 흔한 에러를 피하고 성능을 최적화할 수 있습니다.
실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.
목차
1. 문제 시나리오
시나리오 1: 대량 키-값 조회가 느림
상황: 100만 개 ID를 키로 하는 설정 맵을 조회합니다. std::map은 O(log n)이라 100만 건에서 약 20번 비교가 필요합니다. 초당 수만 건 조회 시 병목이 됩니다.
해결: 해시테이블을 직접 구현하거나 std::unordered_map을 사용해 O(1) 평균 조회를 달성합니다. 충돌 처리(체이닝, 개방 주소법)를 이해하면 튜닝이 가능합니다.
시나리오 2: 접두사 검색·자동완성
상황: 검색창에 “app”을 입력하면 “apple”, “application”, “apply”를 자동완성으로 보여줘야 합니다. std::map은 정렬된 키만 지원하므로, “app”으로 시작하는 모든 키를 찾으려면 O(n) 선형 검색이 필요합니다.
해결: 트라이(Trie)를 구현하면 “app” 노드에서 하위 경로를 따라 O(k)에 접두사 일치하는 모든 문자열을 얻을 수 있습니다. k는 접두사 길이입니다.
시나리오 3: 최근 N개만 유지하는 캐시
상황: API 응답 캐시에 최대 1000개만 저장하고, 오래된 항목은 자동으로 제거해야 합니다. std::map은 삽입 순서를 보장하지 않아 “가장 오래된 항목”을 O(1)에 찾을 수 없습니다.
해결: LRU(Least Recently Used) 캐시를 구현합니다. 해시테이블 + 이중 연결 리스트로 조회·삽입·삭제를 모두 O(1)에 처리합니다.
시나리오 4: 정렬된 데이터에서 빠른 삽입·삭제
상황: 실시간으로 점수가 들어오는 리더보드에서, 정렬된 순서를 유지하면서 삽입·삭제가 빈번합니다. std::vector + std::sort는 삽입마다 O(n)이고, std::map은 O(log n)이지만 균형 트리 재구성이 필요합니다.
해결: Skip List는 평균 O(log n)에 삽입·삭제·검색을 지원하며, 구현이 상대적으로 단순하고 확률적 균형을 사용합니다.
커스텀 자료구조 선택 다이어그램
flowchart TB
subgraph need[요구사항]
N1["O(1) 키-값 조회"]
N2["접두사 검색/자동완성"]
N3["최근 N개만 유지"]
N4["정렬된 순서 + 빠른 삽입"]
end
subgraph sol[추천 자료구조]
S1[해시테이블]
S2[트라이]
S3["LRU 캐시"]
S4["Skip List"]
end
N1 --> S1
N2 --> S2
N3 --> S3
N4 --> S4
2. 해시테이블 (충돌 처리)
체이닝(Chaining) 방식
충돌 시 같은 버킷에 연결 리스트로 연결합니다. 구현이 단순하고 로드 팩터가 높아도 성능 저하가 완만합니다.
// g++ -std=c++17 -o hash_table hash_table.cpp
#include <vector>
#include <list>
#include <string>
#include <functional>
#include <optional>
#include <iostream>
template <typename K, typename V>
class HashTable {
using Bucket = std::list<std::pair<K, V>>;
std::vector<Bucket> buckets_;
size_t size_;
std::hash<K> hasher_;
size_t index(const K& key) const {
return hasher_(key) % buckets_.size();
}
public:
explicit HashTable(size_t capacity = 16) : buckets_(capacity), size_(0) {}
void insert(const K& key, const V& value) {
size_t i = index(key);
for (auto& [k, v] : buckets_[i]) {
if (k == key) {
v = value;
return;
}
}
buckets_[i].emplace_back(key, value);
++size_;
// 리사이즈: 로드 팩터 > 0.75
if (size_ * 4 > buckets_.size() * 3) {
rehash(buckets_.size() * 2);
}
}
std::optional<V> get(const K& key) const {
size_t i = index(key);
for (const auto& [k, v] : buckets_[i]) {
if (k == key) return v;
}
return std::nullopt;
}
bool erase(const K& key) {
size_t i = index(key);
for (auto it = buckets_[i].begin(); it != buckets_[i].end(); ++it) {
if (it->first == key) {
buckets_[i].erase(it);
--size_;
return true;
}
}
return false;
}
void rehash(size_t new_capacity) {
std::vector<Bucket> new_buckets(new_capacity);
for (auto& bucket : buckets_) {
for (auto& [k, v] : bucket) {
size_t i = hasher_(k) % new_capacity;
new_buckets[i].emplace_back(std::move(k), std::move(v));
}
}
buckets_ = std::move(new_buckets);
}
size_t size() const { return size_; }
};
int main() {
HashTable<std::string, int> ht;
ht.insert("apple", 1);
ht.insert("banana", 2);
ht.insert("cherry", 3);
if (auto v = ht.get("banana")) {
std::cout << "banana: " << *v << "\n"; // 2
}
ht.erase("banana");
if (!ht.get("banana")) {
std::cout << "banana removed\n";
}
return 0;
}주의: std::hash는 기본 타입과 std::string만 지원합니다. 커스텀 타입은 std::hash 특수화 또는 해시 함수 객체를 넘겨야 합니다.
개방 주소법 (Open Addressing)
충돌 시 다른 빈 버킷을 찾아 삽입합니다. 선형 탐사(linear probing) 또는 이차 탐사(quadratic probing)를 사용합니다. 캐시 지역성이 좋아 체이닝보다 빠를 수 있지만, 로드 팩터가 높으면 성능이 급격히 떨어집니다.
#include <vector>
#include <optional>
#include <functional>
template <typename K, typename V>
class HashTableOpenAddressing {
enum class EntryState { Empty, Occupied, Deleted };
struct Entry {
K key;
V value;
EntryState state = EntryState::Empty;
};
std::vector<Entry> table_;
size_t size_;
std::hash<K> hasher_;
size_t probe(const K& key, size_t start) const {
size_t i = start;
while (table_[i].state == EntryState::Occupied && table_[i].key != key) {
i = (i + 1) % table_.size(); // 선형 탐사
}
return i;
}
public:
explicit HashTableOpenAddressing(size_t capacity = 16) : table_(capacity), size_(0) {}
void insert(const K& key, const V& value) {
if (size_ * 2 >= table_.size()) rehash(table_.size() * 2);
size_t i = hasher_(key) % table_.size();
i = probe(key, i);
if (table_[i].state == EntryState::Occupied) {
table_[i].value = value;
return;
}
table_[i] = {key, value, EntryState::Occupied};
++size_;
}
std::optional<V> get(const K& key) const {
size_t i = hasher_(key) % table_.size();
i = probe(key, i);
if (table_[i].state == EntryState::Occupied) return table_[i].value;
return std::nullopt;
}
// ...
};3. 트라이 (자동완성)
트라이 노드 구조
각 노드는 자식 포인터 배열(또는 std::map)과 단어 종료 여부를 가집니다.
#include <vector>
#include <string>
#include <memory>
#include <unordered_map>
class TrieNode {
public:
std::unordered_map<char, std::unique_ptr<TrieNode>> children;
bool is_end = false;
};
class Trie {
std::unique_ptr<TrieNode> root_ = std::make_unique<TrieNode>();
void collect_words(TrieNode* node, std::string& prefix,
std::vector<std::string>& result) const {
if (node->is_end) result.push_back(prefix);
for (auto& [ch, child] : node->children) {
prefix.push_back(ch);
collect_words(child.get(), prefix, result);
prefix.pop_back();
}
}
public:
void insert(const std::string& word) {
TrieNode* cur = root_.get();
for (char c : word) {
if (cur->children.find(c) == cur->children.end()) {
cur->children[c] = std::make_unique<TrieNode>();
}
cur = cur->children[c].get();
}
cur->is_end = true;
}
bool search(const std::string& word) const {
TrieNode* 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 starts_with(const std::string& prefix) const {
TrieNode* 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> autocomplete(const std::string& prefix) const {
std::vector<std::string> result;
TrieNode* cur = root_.get();
for (char c : prefix) {
auto it = cur->children.find(c);
if (it == cur->children.end()) return result;
cur = it->second.get();
}
std::string p = prefix;
collect_words(cur, p, result);
return result;
}
};트라이 자동완성 사용 예
int main() {
Trie trie;
trie.insert("apple");
trie.insert("application");
trie.insert("apply");
trie.insert("banana");
trie.insert("app");
auto suggestions = trie.autocomplete("app");
for (const auto& s : suggestions) {
std::cout << s << "\n"; // app, apple, application, apply
}
return 0;
}트라이 구조 다이어그램
flowchart TB
R[root] --> A[a]
A --> P[p]
P --> P2[p]
P2 --> P3[(end)]
P2 --> L[l]
L --> E[e]
E --> E2[(end)]
P --> L2[l]
L2 --> I[i]
I --> C[c]
C --> A2[a]
A2 --> T[t]
T --> I2[i]
I2 --> O[o]
O --> N[n]
N --> N2[(end)]
L2 --> Y[y]
Y --> Y2[(end)]
4. LRU 캐시
핵심 아이디어
- 해시테이블: 키 → (값, 리스트 반복자) 매핑
- 이중 연결 리스트: 최근 사용 순서 유지 (최신 = 앞, 오래됨 = 뒤)
- 조회 시: 해당 노드를 리스트 앞으로 이동
- 삽입 시: 새 노드를 앞에 추가, 용량 초과 시 뒤에서 제거
#include <unordered_map>
#include <list>
#include <optional>
#include <iostream>
template <typename K, typename V>
class LRUCache {
size_t capacity_;
std::list<std::pair<K, V>> list_; // [최신 ... 오래됨]
std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> map_;
public:
explicit LRUCache(size_t capacity) : capacity_(capacity) {}
std::optional<V> get(const K& 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 K& key, const V& 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_) {
auto& [k, v] = list_.back();
map_.erase(k);
list_.pop_back();
}
list_.emplace_front(key, value);
map_[key] = list_.begin();
}
bool erase(const K& key) {
auto it = map_.find(key);
if (it == map_.end()) return false;
list_.erase(it->second);
map_.erase(it);
return true;
}
size_t size() const { return list_.size(); }
};
int main() {
LRUCache<int, std::string> cache(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // 1이 최근 사용됨
cache.put(4, "four"); // 2가 evict (가장 오래됨)
std::cout << cache.get(2).has_value() << "\n"; // false
std::cout << *cache.get(1) << "\n"; // "one"
return 0;
}주의: std::list::splice는 O(1)에 노드를 이동합니다. 반복자는 무효화되지 않습니다.
5. Skip List
개념
여러 레벨의 연결 리스트로 구성된 확률적 자료구조입니다. 상위 레벨은 “빠른 탐색”을 위한 스킵 포인터 역할을 합니다. 평균 O(log n)에 삽입·삭제·검색이 가능합니다.
#include <random>
#include <vector>
#include <optional>
#include <iostream>
class SkipList {
struct Node {
int value;
std::vector<Node*> forward;
Node(int v, int level) : value(v), forward(level + 1, nullptr) {}
};
Node* head_;
int max_level_;
int level_;
std::mt19937 rng_{std::random_device{}()};
int random_level() {
int lvl = 0;
while (lvl < max_level_ && (rng_() & 1)) ++lvl;
return lvl;
}
public:
SkipList(int max_level = 16) : max_level_(max_level), level_(0) {
head_ = new Node(-1, max_level);
}
~SkipList() {
Node* cur = head_;
while (cur) {
Node* next = cur->forward[0];
delete cur;
cur = next;
}
}
bool search(int target) const {
Node* cur = head_;
for (int i = level_; i >= 0; --i) {
while (cur->forward[i] && cur->forward[i]->value < target)
cur = cur->forward[i];
}
cur = cur->forward[0];
return cur && cur->value == target;
}
void insert(int value) {
std::vector<Node*> update(max_level_ + 1, nullptr);
Node* cur = head_;
for (int i = level_; i >= 0; --i) {
while (cur->forward[i] && cur->forward[i]->value < value)
cur = cur->forward[i];
update[i] = cur;
}
int lvl = random_level();
if (lvl > level_) {
for (int i = level_ + 1; i <= lvl; ++i) update[i] = head_;
level_ = lvl;
}
Node* newNode = new Node(value, lvl);
for (int i = 0; i <= lvl; ++i) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
bool erase(int value) {
std::vector<Node*> update(max_level_ + 1, nullptr);
Node* cur = head_;
for (int i = level_; i >= 0; --i) {
while (cur->forward[i] && cur->forward[i]->value < value)
cur = cur->forward[i];
update[i] = cur;
}
cur = cur->forward[0];
if (!cur || cur->value != value) return false;
for (int i = 0; i <= level_; ++i) {
if (update[i]->forward[i] != cur) break;
update[i]->forward[i] = cur->forward[i];
}
delete cur;
while (level_ > 0 && !head_->forward[level_]) --level_;
return true;
}
};6. 완전한 커스텀 자료구조 예제
예제 1: API 응답 캐시 (LRU)
// g++ -std=c++17 -o api_cache api_cache.cpp
#include <string>
#include <chrono>
#include <iostream>
// LRUCache 구현 (위와 동일) ...
struct CachedResponse {
std::string body;
std::chrono::steady_clock::time_point cached_at;
};
std::string fetch_from_api(const std::string& url) {
// 실제로는 HTTP 요청
return "response for " + url;
}
int main() {
LRUCache<std::string, CachedResponse> cache(100);
auto get_or_fetch = [&](const std::string& url) -> std::string {
if (auto v = cache.get(url)) {
if (std::chrono::steady_clock::now() - v->cached_at <
std::chrono::minutes(5)) {
return v->body;
}
}
std::string body = fetch_from_api(url);
cache.put(url, {body, std::chrono::steady_clock::now()});
return body;
};
std::cout << get_or_fetch("/api/users") << "\n";
std::cout << get_or_fetch("/api/users") << "\n"; // 캐시 히트
return 0;
}예제 2: 검색 자동완성 (트라이)
#include <algorithm>
#include <iostream>
// Trie 구현 (위와 동일) ...
int main() {
Trie trie;
std::vector<std::string> words = {"apple", "banana", "application",
"apply", "ban", "band", "bandage"};
for (const auto& w : words) trie.insert(w);
std::string prefix;
std::cout << "Enter prefix: ";
std::cin >> prefix;
auto suggestions = trie.autocomplete(prefix);
std::sort(suggestions.begin(), suggestions.end());
std::cout << "Suggestions: ";
for (const auto& s : suggestions) std::cout << s << " ";
std::cout << "\n";
return 0;
}예제 3: 설정 저장소 (해시테이블)
#include <sstream>
// HashTable 구현 (위와 동일) ...
int main() {
HashTable<std::string, std::string> config(64);
config.insert("host", "localhost");
config.insert("port", "8080");
config.insert("timeout", "30");
std::string port = config.get("port").value_or("80");
std::cout << "Port: " << port << "\n";
config.erase("timeout");
return 0;
}7. 자주 발생하는 에러와 해결법
에러 1: 해시 버킷 수가 2의 거듭제곱이 아닐 때
증상: 해시 분포가 불균형해 특정 버킷에만 몰립니다.
원인: key % size에서 size가 2의 거듭제곱이면 하위 비트만 사용되어, key의 하위 비트 패턴이 비슷하면 충돌이 많아집니다.
// ❌ 나쁜 예: 2의 거듭제곱
size_t index = hasher_(key) % 16; // 하위 4비트만 사용
// ✅ 좋은 예: 소수 사용 또는 더 나은 해시 조합
size_t index = (hasher_(key) * 2654435761u) % 4294967291u; // 큰 소수
// 또는 size를 소수로 선택에러 2: LRU에서 splice 후 반복자 무효화
증상: Segmentation fault 또는 잘못된 값 반환.
원인: std::list::splice는 반복자를 무효화하지 않지만, 다른 리스트로 splice할 때는 원본 리스트의 반복자가 무효화됩니다. 같은 리스트 내 이동은 안전합니다.
// ✅ 안전: 같은 리스트 내 이동
list_.splice(list_.begin(), list_, it->second);
// ❌ 위험: 다른 리스트로 이동 시 map_의 반복자 갱신 필요에러 3: 트라이에서 메모리 누수
증상: 삭제 연산 후 메모리 사용량이 줄지 않습니다.
원인: erase 구현 시 unique_ptr의 자식 노드를 재귀적으로 해제해야 합니다. 노드만 제거하고 자식 트리를 놓치면 누수가 발생합니다.
// ✅ erase 구현 예
void erase_impl(TrieNode* node, const std::string& word, size_t idx) {
if (idx == word.size()) {
node->is_end = false;
return;
}
char c = word[idx];
auto it = node->children.find(c);
if (it == node->children.end()) return;
erase_impl(it->second.get(), word, idx + 1);
if (!it->second->is_end && it->second->children.empty()) {
node->children.erase(it); // unique_ptr 자동 해제
}
}에러 4: 해시테이블 리사이즈 시 무한 루프
증상: rehash 호출 시 무한 루프 또는 크래시.
원인: insert 내부에서 rehash를 호출할 때, rehash가 this의 buckets_를 수정하면서 insert가 사용 중인 반복자가 무효화됩니다. rehash 호출 시점에 반복자를 사용하지 않도록 해야 합니다.
// ✅ rehash 전에 bucket 참조 제거
void insert(const K& key, const V& value) {
// ... 삽입 로직 ...
if (size_ * 4 > buckets_.size() * 3) {
rehash(buckets_.size() * 2); // 재진입 시 buckets_가 새로 할당됨
}
}에러 5: Skip List에서 랜덤 레벨 생성
증상: 레벨이 거의 항상 0이거나, 모든 노드가 최대 레벨이 됩니다.
원인: random_level()의 확률 분포가 잘못되었습니다. 일반적으로 1/2 확률로 레벨을 올립니다.
// ✅ 올바른 random_level (1/2 확률)
int random_level() {
int lvl = 0;
double p = 0.5;
std::uniform_real_distribution<> dis(0, 1);
while (lvl < max_level_ && dis(rng_) < p) ++lvl;
return lvl;
}에러 6: 커스텀 타입에 std::hash 미정의
증상: std::unordered_map<MyKey, V> 또는 HashTable<MyKey, V> 컴파일 에러.
원인: std::hash는 기본 타입과 std::string만 지원합니다.
// ✅ 해결: std::hash 특수화
struct MyKey {
int id;
std::string name;
bool operator==(const MyKey& o) const {
return id == o.id && name == o.name;
}
};
namespace std {
template <>
struct hash<MyKey> {
size_t operator()(const MyKey& k) const {
return hash<int>()(k.id) ^ (hash<string>()(k.name) << 1);
}
};
}8. 성능 비교
자료구조별 연산 복잡도
| 자료구조 | 삽입 | 삭제 | 검색 | 접두사 검색 | 메모리 |
|---|---|---|---|---|---|
| std::map | O(log n) | O(log n) | O(log n) | O(n) | O(n) |
| std::unordered_map | O(1)* | O(1)* | O(1)* | O(n) | O(n) |
| 해시테이블(체이닝) | O(1)* | O(1)* | O(1)* | O(n) | O(n + buckets) |
| 트라이 | O(k) | O(k) | O(k) | O(k + m) | O(N·k) |
| LRU 캐시 | O(1) | O(1) | O(1) | - | O(capacity) |
| Skip List | O(log n) | O(log n) | O(log n) | O(n) | O(n log n)* |
*평균 복잡도. k=문자열 길이, m=접두사 일치 개수, N=총 노드 수.
벤치마크 예시 (100만 건 삽입·조회)
환경: Apple M1, -O2
std::map: 삽입 1.2s, 조회 0.8s
std::unordered_map: 삽입 0.4s, 조회 0.15s
HashTable(체이닝): 삽입 0.5s, 조회 0.18s선택 가이드
| 요구사항 | 추천 |
|---|---|
| O(1) 키-값, 표준 라이브러리 사용 | std::unordered_map |
| O(1) 키-값, 커스텀 해시/제약 환경 | 해시테이블 직접 구현 |
| 접두사 검색, 자동완성 | 트라이 |
| 최근 N개만 유지하는 캐시 | LRU 캐시 |
| 정렬 + 빠른 삽입, 구현 단순성 | Skip List |
9. 프로덕션 패턴
패턴 1: 해시테이블 로드 팩터 모니터링
로드 팩터(load factor) = size / capacity. 0.75 이상이면 리사이즈를 고려합니다.
double load_factor() const {
return static_cast<double>(size_) / buckets_.size();
}
void maybe_rehash() {
if (load_factor() > 0.75) rehash(buckets_.size() * 2);
}패턴 2: LRU 캐시 TTL(Time-To-Live)
template <typename K, typename V>
class LRUCacheWithTTL {
LRUCache<K, std::pair<V, std::chrono::steady_clock::time_point>> cache_;
std::chrono::seconds ttl_;
public:
std::optional<V> get(const K& key) {
auto v = cache_.get(key);
if (!v) return std::nullopt;
if (std::chrono::steady_clock::now() - v->second > ttl_) {
cache_.erase(key); // erase 구현 필요
return std::nullopt;
}
return v->first;
}
};패턴 3: 트라이에서 최대 검색 결과 개수 제한
자동완성에서 수천 개가 나오면 성능·UX 저하. 상위 N개만 반환합니다.
void collect_words_limited(TrieNode* node, std::string& prefix,
std::vector<std::string>& result, size_t max) const {
if (result.size() >= max) return;
if (node->is_end) result.push_back(prefix);
for (auto& [ch, child] : node->children) {
prefix.push_back(ch);
collect_words_limited(child.get(), prefix, result, max);
prefix.pop_back();
}
}패턴 4: 스레드 안전 래퍼
#include <mutex>
template <typename K, typename V>
class ThreadSafeLRUCache {
LRUCache<K, V> cache_;
std::mutex mtx_;
public:
std::optional<V> get(const K& key) {
std::lock_guard lock(mtx_);
return cache_.get(key);
}
void put(const K& key, const V& value) {
std::lock_guard lock(mtx_);
cache_.put(key, value);
}
};패턴 5: 구현 체크리스트
프로덕션에 커스텀 자료구조를 적용할 때 확인할 항목입니다.
- 해시테이블: 로드 팩터 > 0.75 시 리사이즈
- 해시테이블: 커스텀 키 타입에
std::hash특수화 또는 해시 함수 객체 제공 - 트라이: 대용량 시
autocomplete결과 개수 제한 - LRU:
splice는 같은 리스트 내에서만 사용 - Skip List:
random_level확률 분포 검증 - 멀티스레드: 공유 시 뮤텍스 또는 lock-free 구조 검토
패턴 6: 자료구조 선택 플로우
flowchart TD
A["키-값 저장 필요?"] -->|Yes| B["접두사 검색?"]
A -->|No| C["다른 요구사항"]
B -->|Yes| D[트라이]
B -->|No| E["캐시 용량 제한?"]
E -->|Yes| F["LRU 캐시"]
E -->|No| G["std::unordered_map 사용"]
정리
| 항목 | 설명 |
|---|---|
| 해시테이블 | 체이닝·개방 주소법, 충돌 처리, 리사이즈 |
| 트라이 | 접두사 검색, 자동완성, O(k) 연산 |
| LRU 캐시 | 해시 + 이중 연결 리스트, O(1) 조회·삽입·삭제 |
| Skip List | 확률적 균형, O(log n) 평균 |
| 에러 | 해시 분포, splice, 메모리 누수, hash 특수화 |
| 성능 | 로드 팩터, reserve, TTL |
| 프로덕션 | TTL, 결과 제한, 스레드 안전 래퍼 |
핵심 원칙:
- 요구사항에 맞는 자료구조 선택 (std::unordered_map vs 트라이 vs LRU)
- 해시테이블은 로드 팩터 모니터링 및 리사이즈
- LRU는 splice로 O(1) 최근 사용 갱신
- 트라이는 접두사 검색에 최적
- 프로덕션에서는 TTL·용량 제한·스레드 안전 고려
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 캐싱 시스템, 자동완성, 빠른 검색, 메모리 제약 환경 등에 활용합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
참고 자료
- std::unordered_map - cppreference
- std::hash - cppreference
- std::list::splice - cppreference
- Skip List - William Pugh, 1990
한 줄 요약: 해시테이블·트라이·LRU 캐시를 직접 구현하고, 흔한 에러를 피하며 프로덕션 패턴을 적용할 수 있습니다.
관련 글
- C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시·Skip List [#54-2]
- C++ vector 기초 완벽 가이드 | 초기화·연산·용량 관리와 실전 패턴
- C++ Custom Allocator |
- C++ Allocator |