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

개요

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

핵심 특징:

키와 값이 각각 별도의 연속 배열에 저장 (SoA 레이아웃)
이진 탐색으로 O(log n) 조회, 연속 메모리로 캐시 효율 극대화
삽입은 O(n) (배열 시프트 필요), 따라서 읽기 위주 워크로드에 적합
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 선택:

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

8. 반복자 무효화 주의사항

std::flat_map은 연속 메모리를 사용하므로 삽입/삭제 시 모든 반복자가 무효화됩니다. 이는 std::map과 다른 중요한 차이점입니다.

#include <flat_map>

std::flat_map<int, std::string> m = {{1, "a"}, {2, "b"}, {3, "c"}};

auto it = m.find(2);  // 유효한 반복자
m.insert({4, "d"});   // 삽입 후 it는 무효화됨!

// 올바른 사용 패턴: 삽입 후 반복자 재획득
m.insert({4, "d"});
it = m.find(2);  // 재획득

9. std::map과의 상세 비교

#include <flat_map>
#include <map>
#include <chrono>
#include <iostream>
#include <random>

void benchmark_lookup(int n) {
    // 데이터 준비
    std::vector<std::pair<int, int>> data;
    std::mt19937 rng(42);
    for (int i = 0; i < n; ++i)
        data.emplace_back(rng() % (n * 10), i);

    // std::map
    std::map<int, int> tree_map(data.begin(), data.end());
    // std::flat_map
    std::flat_map<int, int> flat(data.begin(), data.end());

    // 조회 성능 측정
    auto start = std::chrono::high_resolution_clock::now();
    volatile int sum = 0;
    for (auto& [k, v] : data) {
        auto it = tree_map.find(k);
        if (it != tree_map.end()) sum += it->second;
    }
    auto t_map = std::chrono::duration_cast<std::chrono::microseconds>(
        std::chrono::high_resolution_clock::now() - start).count();

    start = std::chrono::high_resolution_clock::now();
    sum = 0;
    for (auto& [k, v] : data) {
        auto it = flat.find(k);
        if (it != flat.end()) sum += it->second;
    }
    auto t_flat = std::chrono::duration_cast<std::chrono::microseconds>(
        std::chrono::high_resolution_clock::now() - start).count();

    std::cout << "map:      " << t_map  << " µs\n";
    std::cout << "flat_map: " << t_flat << " µs\n";
    // flat_map은 캐시 친화적 메모리 레이아웃으로 보통 2~5x 빠른 조회
}

10. 실전 활용 패턴

#include <flat_map>
#include <flat_set>

// 패턴 1: 설정 테이블 (빌드 후 읽기 전용)
const std::flat_map<std::string, int> HTTP_STATUS = {
    {"OK",           200},
    {"NOT_FOUND",    404},
    {"SERVER_ERROR", 500},
};

// 패턴 2: 열거값 이름 매핑
enum class Color { Red, Green, Blue };
const std::flat_map<Color, std::string_view> COLOR_NAMES = {
    {Color::Red,   "Red"},
    {Color::Green, "Green"},
    {Color::Blue,  "Blue"},
};

// 패턴 3: 중복 없는 정렬 집합 (ID, 태그 등)
std::flat_set<std::string> active_features = {
    "dark_mode", "notifications", "analytics"
};
if (active_features.contains("dark_mode")) {
    // 기능 활성화 처리
}

// 패턴 4: 누적 후 일괄 생성 (성능 최적화)
std::vector<std::pair<int, std::string>> entries;
entries.reserve(10000);
for (int i = 0; i < 10000; ++i)
    entries.emplace_back(i, std::to_string(i));
// 정렬된 경우 sorted_unique 태그로 O(n) 생성
std::sort(entries.begin(), entries.end());
auto it = std::unique(entries.begin(), entries.end(),
    [](auto& a, auto& b) { return a.first == b.first; });
entries.erase(it, entries.end());
std::flat_map<int, std::string> lookup(std::sorted_unique, std::move(entries));

정리

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

언제 flat_map이 유리한가:

컨테이너 구축 후 주로 조회만 하는 경우 (읽기 90% 이상)
컨테이너 크기 수백~수천 개 (너무 크면 삽입 비용이 지배적)
메모리 밀집도와 캐시 지역성이 중요한 임베디드/게임 환경
std::map에서 단순 교체로 성능 개선이 필요할 때

std::map을 유지해야 하는 경우:

빈번한 삽입/삭제가 수명 주기 전반에 걸쳐 발생
삽입/삭제 후에도 반복자 유효성을 유지해야 하는 경우
원소 수가 수만 개 이상으로 삽입 시 O(n) 비용이 큰 경우