C++23 flat_map & flat_set — 캐시 친화적 정렬 컨테이너

개요

std::flat_map과 std::flat_set은 C++23에서 도입된 연속 메모리 기반 정렬 컨테이너입니다. 내부적으로 두 개의 정렬된 벡터(키/값)를 사용해 std::map의 트리 구조 대비 캐시 효율이 높습니다.

---

1. 기본 사용

#include <flat_map>
#include <flat_set>
#include <string>
#include <iostream>

int main()
{
    // flat_map — 키/값 쌍 (정렬 유지)
    std::flat_map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"]   = 87;
    scores["Carol"] = 92;

    // 반복 순서: 키 기준 정렬
    for (auto& [name, score] : scores)
        std::cout << name << ": " << score << '\n';

    // flat_set — 유일한 정렬 값
    std::flat_set<int> ids = {3, 1, 4, 1, 5, 9};
    // 내부: {1, 3, 4, 5, 9} (중복 제거, 정렬)
}

---

2. 내부 구조

std::map<K, V>          std::flat_map<K, V>
┌──────────────┐        ┌─────────────────────────┐
│  트리 노드    │        │ keys:   [k1, k2, k3 ...] │  ← 연속 메모리
│  (포인터 3개)│        │ values: [v1, v2, v3 ...] │  ← 연속 메모리
└──────────────┘        └─────────────────────────┘
- 각 노드 힙 할당       - 단일 벡터 할당
- 캐시 미스 多          - 캐시 친화적

---

3. 성능 특성

연산	std::map	std::flat_map
조회	O(log n)	O(log n)
삽입	O(log n)	O(n) — 시프트 필요
순회	느림 (캐시 미스)	빠름 (연속 메모리)
메모리	노드당 오버헤드	밀집
적합 규모	대용량 + 빈번한 삽입	소~중규모 + 읽기 위주

---

4. 배치 삽입 — 성능 최적화

#include <flat_map>
#include <vector>

// 좋지 않은 방법: 하나씩 삽입 → 매번 O(n) 시프트
std::flat_map<int, std::string> m;
for (int i = 0; i < 1000; ++i)
    m[i] = std::to_string(i);

// 좋은 방법: 정렬된 데이터로 일괄 생성
std::vector<std::pair<int, std::string>> data;
for (int i = 0; i < 1000; ++i)
    data.emplace_back(i, std::to_string(i));

// std::sorted_unique 힌트로 O(n) 생성
std::flat_map<int, std::string> fast(std::sorted_unique, data);

---

5. 커스텀 비교자 & 기반 컨테이너

#include <flat_map>
#include <deque>

// deque를 기반 컨테이너로 사용 (양쪽 O(1) 삽입)
std::flat_map<int, int,
    std::less<int>,
    std::deque<int>,  // 키 컨테이너
    std::deque<int>>  // 값 컨테이너
    dm;

// 대소문자 무시 flat_set
struct CaseInsensitive {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](char x, char y){ return std::tolower(x) < std::tolower(y); });
    }
};

std::flat_set<std::string, CaseInsensitive> keywords;
keywords.insert("Public");
keywords.contains("public"); // true

---

6. flat_multimap / flat_multiset

#include <flat_map>

// 중복 키 허용
std::flat_multimap<std::string, int> events;
events.emplace("click", 1);
events.emplace("click", 2);
events.emplace("hover", 3);

auto [begin, end] = events.equal_range("click");
for (auto it = begin; it != end; ++it)
    std::cout << it->second << ' '; // 1 2

---

7. 언제 flat_map을 선택해야 하나

flat_map 선택:

• 빌드 후 읽기 위주(조회 90%+)
• 컨테이너 크기가 수백~수천 개
• 메모리 밀집도가 중요한 경우

map 선택:

• 빈번한 삽입/삭제
• 컨테이너 크기가 수만 개 이상
• 반복자 무효화를 피해야 하는 경우

---

정리

std::flat_map은 읽기 위주 정렬 맵의 성능을 캐시 지역성으로 개선합니다. 빌드 시점에 데이터를 일괄 삽입하고 이후 조회만 하는 패턴(설정 테이블, 코드 테이블, 사전 등)에서 std::map을 그대로 교체하면 의미 있는 성능 향상을 얻을 수 있습니다.