C++ 자료구조 구현 실습: 해시테이블, 트라이 자동완성, O(1) LRU 캐시, Skip List 성능 비교
들어가며: “std::unordered_map으로 안 되는 경우”
“캐시 크기 제한이 필요한데, 오래된 항목을 자동으로 지우려면?”
C++ STL은 강력하지만 모든 요구를 그대로 해결하지는 못합니다. std::unordered_map에는 크기 제한이나 “가장 오래 안 쓴 항목”이라는 개념이 없고, std::map은 k번째 원소에 빠르게 접근하는 기능이 없으며, STL에는 트라이도 없습니다.
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를 직접 구현하고, 구현할 때 자주 하는 실수를 함께 살펴봅니다.
요구 환경: 예제에 구조화된 바인딩과 std::optional을 쓰므로 C++17 이상으로 컴파일합니다.
표준 컨테이너만으로 부족해지는 순간
캐시 크기 제한 + 오래된 항목 자동 제거 (LRU)
상황: API 응답을 캐시하는데 메모리 한도가 있어서, 가장 최근에 사용한 일정 개수만 유지하고 오래된 것은 자동으로 제거해야 합니다. 잘못된 접근:
// ❌ std::unordered_map - 크기 제한 없음, "오래된 것" 판단 불가
std::unordered_map<std::string, Response> cache;
cache["/api/users/1"] = fetchUser(1); // 무한히 쌓임!
// 언제 뭘 지울지 알 수 없음문제점: unordered_map은 삽입 순서를 기억하지 않습니다. “가장 오래 사용하지 않은” 항목을 O(1)에 찾을 수 없습니다.
올바른 접근: LRU 캐시 (해시 + 이중 연결 리스트) - 아래 LRU 캐시 구현 참조
접두사로 검색 (자동완성)
상황: 검색창에 “app”을 입력하면 “apple”, “application”, “apply” 등을 제안해야 합니다. 잘못된 접근:
// std::map으로도 접두사 검색은 가능
std::map<std::string, int> words;
for (auto it = words.lower_bound("app"); it != words.end(); ++it) {
if (it->first.compare(0, 3, "app") != 0) break; // 접두사가 달라지면 바로 종료
suggest(it->first);
}정렬된 컨테이너에서는 접두사가 같은 키들이 연속해 있으므로, lower_bound로 시작 위치를 찾은 뒤 접두사가 달라지는 순간 멈추면 O(log n + 결과 수)로 끝납니다. 트라이가 필요한 경우는 따로 있습니다. 사용자가 한 글자씩 입력할 때마다 처음부터 다시 찾지 않고 이전 노드에서 이어서 내려가고 싶을 때, 노드마다 빈도·인기도 같은 정보를 붙여 상위 후보를 빠르게 뽑고 싶을 때입니다. 아래 트라이 구현을 참고하세요.
커스텀 키에 대한 해시 (복합 키)
상황: (user_id, item_id) 쌍을 키로 쓰고 싶습니다.
문제: 표준에는 std::pair에 대한 std::hash 특수화가 없어서, 아래 코드는 컴파일되지 않습니다.
// ❌ 컴파일 에러: std::hash<std::pair<int,int>>가 없음
std::unordered_map<std::pair<int,int>, int> cache;해시 함수를 직접 제공해야 하는데, 두 해시를 단순히 XOR하면 (1, 2)와 (2, 1)이 같은 값이 되고 (x, x)는 모두 0이 됩니다. Boost의 hash_combine 방식처럼 값을 섞어서 합칩니다.
// ✅ 커스텀 해시 함수
struct PairHash {
size_t operator()(const std::pair<int,int>& p) const {
size_t seed = std::hash<int>{}(p.first);
seed ^= std::hash<int>{}(p.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
std::unordered_map<std::pair<int,int>, int, PairHash> cache;두 값이 32비트 정수라면 (uint64_t(a) << 32) | uint32_t(b)처럼 하나의 64비트 값으로 합친 뒤 해시하는 방법도 충돌이 없어 간단합니다.
정렬된 삽입/삭제 + 인덱스 접근
상황: 실시간 랭킹에서 순위가 자주 바뀌고, “k번째” 요소에 O(log n)으로 접근해야 합니다. std::map은 k번째 접근이 O(k)입니다.
잘못된 접근:
// ❌ std::map - k번째 접근이 O(n)
std::map<int, std::string> ranking;
// 5번째 찾으려면 begin에서 5번 ++
auto it = ranking.begin();
std::advance(it, 4); // O(k) - 느림!올바른 접근: 각 노드에 서브트리 크기를 저장하는 order statistic tree(GCC의 __gnu_pbds::tree가 대표적)나, 링크마다 건너뛰는 원소 수를 저장하는 indexable skip list를 씁니다. 아래 Skip List 구현은 기본형이라 k번째 접근을 지원하지 않으며, 링크별 폭(width)을 추가해야 O(log n) 순위 접근이 가능합니다.
메모리 제약 환경에서의 해시테이블
상황: 메모리가 빠듯한 환경에서 std::unordered_map이 원소마다 노드를 할당하고 버킷 배열까지 따로 잡아 예상보다 메모리를 많이 씁니다.
해결: 버킷 배열을 줄이려면 로드 팩터를 높이고, 원소 수를 알면 미리 예약합니다. reserve(n)은 현재 max_load_factor를 기준으로 버킷 수를 정하므로 로드 팩터를 먼저 바꿔야 합니다. 노드별 할당 자체가 부담이라면 개방 주소법 해시테이블(아래)이나 정렬된 std::vector가 더 맞습니다.
// ✅ 메모리 제한된 환경
std::unordered_map<int, int> small_map;
small_map.max_load_factor(2.0f); // 버킷당 평균 2개까지 허용 (먼저 설정)
small_map.reserve(100); // 100개 기준으로 버킷 수 결정체이닝·개방 주소법 해시테이블 직접 구현
개요
체이닝(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]
완전한 구현
#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
사용 예시
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");개방 주소법(Open Addressing)과 툼스톤 함정
체이닝은 구현이 단순하지만 노드마다 힙 할당이 일어나고 포인터를 따라가느라 캐시 미스가 많습니다. 개방 주소법은 충돌이 나면 배열 안의 다음 빈 칸을 찾아(선형 탐사) 넣기 때문에 데이터가 연속 메모리에 있어 조회가 빠르고, absl::flat_hash_map이나 boost::unordered_flat_map 같은 고성능 해시맵이 모두 이 계열입니다. 대신 로드 팩터가 0.7~0.8을 넘으면 탐사 길이가 급격히 늘어나므로 더 일찍 rehash해야 합니다.
직접 구현할 때 거의 모든 사람이 한 번은 밟는 버그가 삭제입니다. 칸을 그냥 Empty로 되돌리면, 그 칸을 지나 뒤쪽에 들어간 키를 찾을 때 탐사가 빈 칸에서 멈춰서 “없는 키”로 판정됩니다. 그래서 삭제된 칸은 Deleted(툼스톤)로 표시하고, 조회는 툼스톤을 건너뛰고 Empty에서만 멈추며, 삽입은 처음 만난 툼스톤을 재사용해야 합니다. 툼스톤이 쌓이면 빈 칸이 사라져 탐사가 길어지므로, rehash 판단에 툼스톤 개수도 포함해야 합니다.
template <typename K, typename V>
class FlatHashTable {
enum class State : unsigned char { Empty, Occupied, Deleted };
struct Slot { State state = State::Empty; std::optional<std::pair<K, V>> kv; };
std::vector<Slot> slots_;
size_t size_ = 0, used_ = 0; // used_ = Occupied + Deleted
size_t home(const K& key) const {
// std::hash<int>가 항등 함수인 구현이 있으므로 비트를 섞은 뒤 2^n 마스크
size_t h = std::hash<K>{}(key) * 0x9E3779B97F4A7C15ull;
return (h >> 17) & (slots_.size() - 1);
}
// 키가 있으면 그 위치, 없으면 삽입할 위치(첫 툼스톤 우선)를 반환
std::pair<size_t, bool> locate(const K& key) const {
size_t i = home(key), firstTomb = SIZE_MAX;
while (true) {
const Slot& s = slots_[i];
if (s.state == State::Empty) return {firstTomb != SIZE_MAX ? firstTomb : i, false};
if (s.state == State::Deleted) { if (firstTomb == SIZE_MAX) firstTomb = i; }
else if (s.kv->first == key) return {i, true};
i = (i + 1) & (slots_.size() - 1);
}
}
void rehash(size_t n) {
std::vector<Slot> old = std::move(slots_);
slots_.assign(n, Slot{}); size_ = used_ = 0;
for (auto& s : old) if (s.state == State::Occupied) insert(s.kv->first, std::move(s.kv->second));
}
public:
FlatHashTable() : slots_(16) {}
void insert(const K& key, V value) {
if ((used_ + 1) * 4 > slots_.size() * 3) rehash(slots_.size() * 2); // 툼스톤 포함 0.75
auto [i, found] = locate(key);
if (found) { slots_[i].kv->second = std::move(value); return; }
if (slots_[i].state == State::Empty) ++used_;
slots_[i].state = State::Occupied;
slots_[i].kv.emplace(key, std::move(value));
++size_;
}
const V* find(const K& key) const {
auto [i, found] = locate(key);
return found ? &slots_[i].kv->second : nullptr;
}
bool erase(const K& key) {
auto [i, found] = locate(key);
if (!found) return false;
slots_[i].state = State::Deleted; // Empty로 되돌리면 뒤쪽 키 조회가 끊김
slots_[i].kv.reset();
--size_;
return true;
}
};std::optional로 슬롯을 감싼 건 K·V가 기본 생성 가능하지 않아도 되게 하려는 것입니다. 용량을 2의 거듭제곱으로 두고 & 마스크를 쓰면 나눗셈이 빠지지만, 하위 비트만 쓰게 되므로 위처럼 곱셈으로 비트를 먼저 섞지 않으면 std::hash<int>가 항등인 libstdc++에서 4의 배수 키만 넣어도 칸의 3/4가 비는 분포가 나옵니다. 소수 크기 테이블은 이 문제를 피하는 대신 매 조회마다 나머지 연산 비용을 냅니다.
트라이(접두사 트리) 구현
개요
트라이(Trie)는 각 간선이 문자 하나를 나타내고, 루트에서 어떤 노드까지의 경로가 하나의 문자열(접두사)이 되는 트리입니다. 단어의 끝은 리프가 아니라 is_end 표시로 구분하므로, “apple”과 “apply”는 “appl”까지 같은 경로를 공유합니다.
flowchart TD R["(root)"] --> A[a] A --> P[p] P --> P1[p] P1 --> L1[l] L1 --> E1["e (apple)"] L1 --> Y1["y (apply)"] A --> N["n (an)"]
완전한 구현
#include <memory>
#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: 접두사로 시작하는 모든 단어 수집
사용 예시
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"}해시맵 + 이중 연결 리스트로 만드는 LRU 캐시
개요
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
완전한 구현
#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에 추가
사용 예시
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");Skip List 구현
개요
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
완전한 구현
#include <memory>
#include <random>
#include <vector>
#include <optional>
// 단순화한 구현: 같은 키를 다시 insert하면 중복 노드가 생기고,
// erase한 노드의 메모리는 nodes_에 남아 있다가 SkipList 소멸 시 해제된다.
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: 상위 레벨부터 건너뛰며 하강
rehash 반복자 무효화·LRU 이터레이터·노드 소유권 문제
해시테이블 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));
}LRU 캐시에서 map에 리스트 이터레이터 저장 시 무효화
증상: list::splice나 list::erase 후 map_에 저장된 이터레이터가 무효화될 수 있음.
해결법: splice는 노드를 이동할 뿐이므로 같은 리스트 내에서는 이터레이터가 유효합니다. 단, list::erase로 제거된 노드의 이터레이터는 무효화되므로, erase 전에 map_에서 해당 키를 제거해야 합니다.
// ✅ 올바른 순서
auto last = list_.back();
map_.erase(last.first); // 먼저 map에서 제거
list_.pop_back(); // 그 다음 리스트에서 제거트라이에서 빈 문자열 처리
증상: 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; // 또는 예외
// ...
}해시 함수 품질 - 충돌 과다
증상: 해시테이블 성능이 급격히 저하 (체인이 매우 길어짐).
// ❌ 나쁜 해시 - 모든 키가 같은 버킷으로
struct BadHash {
size_t operator()(int x) const { return 1; }
};해결법: 여러 필드를 합칠 때는 앞의 hash_combine 방식처럼 비트를 섞습니다. 또 libstdc++와 libc++의 정수 해시는 값을 그대로 돌려주므로, 키가 일정한 간격(예: 모두 1024의 배수)으로 분포하고 버킷 수가 2의 거듭제곱인 테이블에서는 하위 비트가 같아 한 버킷에 몰릴 수 있습니다. 직접 만든 테이블이라면 앞의 FlatHashTable처럼 곱셈으로 비트를 섞은 뒤 인덱스를 구합니다.
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;LRU 캐시 capacity 0
증상: capacity_ == 0이면 첫 put에서 list_.size() >= 0이 참이 되어, 빈 리스트에 list_.back()과 pop_back()을 호출하는 정의되지 않은 동작이 됩니다.
해결법: 생성자에서 capacity_를 최소 1로 보장.
explicit LRUCache(size_t capacity) : capacity_(capacity) {
if (capacity_ == 0) capacity_ = 1;
}네 자료구조의 연산 복잡도 비교
자료구조별 연산 복잡도
| 자료구조 | 삽입 | 검색 | 삭제 | 접두사 검색 | k번째 접근 |
|---|---|---|---|---|---|
std::unordered_map | O(1) 평균 | O(1) 평균 | O(1) 평균 | ❌ | ❌ |
std::map | O(log n) | O(log n) | O(log n) | O(log n + 결과 수) | O(k) |
| 해시테이블 (체이닝) | 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(n), 폭 저장 시 O(log n) |
m = 키/접두사 길이
직접 측정할 때 볼 것
같은 O(1)이어도 실제 속도는 메모리 배치가 좌우합니다. 체이닝 해시테이블과 std::unordered_map은 원소마다 노드를 할당하므로 조회 때 포인터를 한 번 더 따라가고, 개방 주소법 테이블은 원소가 배열에 연속해 있어 캐시 효율이 좋습니다. std::map은 O(log n)번 노드를 따라가므로 원소가 많을수록 해시 계열과의 차이가 벌어집니다. 실제 배수는 키 타입, 해시 함수, 할당자, 데이터 크기에 따라 크게 달라지므로, 자신의 키 분포로 삽입·조회·삭제를 따로 재서 비교해야 합니다.
선택 가이드
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]
스레드 안전 LRU·TTL 캐시·자동완성 트라이로 확장하기
스레드 안전 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_;
};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); // 앞의 LRUCache::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_;
};트라이 + 빈도수 (자동완성 순위)
class AutocompleteTrie {
public:
AutocompleteTrie() : root_(std::make_unique<Node>()) {} // root_를 만들지 않으면 첫 insert에서 널 역참조
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(),
[](const auto& a, const auto& b) { 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_;
void collectWithFreq(const Node* node, const std::string& prefix,
std::vector<std::pair<std::string, int>>& out) const {
if (node->is_end) out.emplace_back(prefix, node->freq);
for (const auto& [c, child] : node->children) {
collectWithFreq(child.get(), prefix + c, out);
}
}
};메트릭 수집 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;
};같이 보면 좋은 글
- C++ std::vector 기초: 생성·삽입·삭제와 배열 대신 쓰는 이유
- C++ STL 컨테이너: 연산별 성능 비교와 상황별 선택 기준
- C++ map·unordered_map·flat_map: 성능 비교와 선택 기준
- 구간 쿼리와 누적합을 위한 트리