[C++23 새기능 소개] std::flat_map과 std::flat_set

C++23에서는 표준 컨테이너에 새로운 멤버들을 추가하여 성능과 메모리 효율성을 높이고, 특정 상황에서 더 나은 선택지를 제공하기 위해 std::flat_map과 std::flat_set이 도입되었습니다. 이번 글에서는 std::flat_map과 std::flat_set의 개념과 사용법, 그리고 이전 표준 컨테이너와 비교하여 어떻게 개선되었는지 알아보겠습니다.

std::flat_map과 std::flat_set란 무엇인가요?

std::flat_map과 std::flat_set은 기존의 std::map과 std::set과 유사한 인터페이스를 제공하지만, 내부적으로 연속적인 메모리 블록(배열)을 사용하여 요소를 저장하는 정렬된 컨테이너입니다. 이는 트리 기반(std::map, std::set) 컨테이너와 달리, 원소들이 인접한 메모리에 저장되므로 캐시 친화적이고, 특정 작업에서 더 나은 성능을 기대할 수 있습니다.

이전 버전에서는 어떻게 했나요?

C++23 이전에는 정렬된 연속 메모리 구조를 직접 관리하기 위해 다음과 같은 방법을 사용했습니다.

1. std::vector를 사용한 정렬과 이진 탐색

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9};
    std::sort(vec.begin(), vec.end()); // 정렬

    // 이진 탐색을 통한 검색
    auto it = std::lower_bound(vec.begin(), vec.end(), 4);
    if (it != vec.end() && *it == 4) {
        // 4를 찾음
    }

    return 0;
}

• 문제점:
  • 키-값 쌍을 처리하려면 별도의 구조체나 pair 관리 필요
  • 삽입이나 삭제 시 재정렬 및 이동 비용 발생
  • std::map이나 std::set처럼 직관적인 인터페이스 제공 어려움

2. std::map, std::set 사용

#include <map>
#include <set>

int main() {
    std::map<int, int> mp = {{1,10}, {2,20}, {3,30}};
    mp[4] = 40; // 로그 복잡도 삽입

    std::set<int> st = {1,2,3};
    st.insert(4); // 로그 복잡도 삽입

    return 0;
}

• 문제점:
  • 내부적으로 레드-블랙 트리를 사용하여, 삽입/삭제는 O(log n)이지만, 메모리 접근 지역성(Locality) 낮음
  • 순차 순회 성능이 vector 기반 접근 대비 비효율적일 수 있음
  • 캐시 친화적이지 않아 대량의 순차 탐색 시 성능 저하 가능

C++23의 std::flat_map과 std::flat_set을 사용한 개선

std::flat_map과 std::flat_set은 다음과 같이 동작합니다:

• 내부적으로 정렬된 std::vector와 유사한 구조를 사용
• 검색, 삽입, 삭제 시 정렬 상태 유지
• std::map, std::set과 유사한 인터페이스 제공 (예: find, insert, lower_bound 등)

예제: std::flat_map 사용

#include <flat_map>
#include <iostream>

int main() {
    std::flat_map<int, std::string> fm = {{1, "one"}, {2, "two"}, {4, "four"}};

    fm.insert({3, "three"}); // 삽입 시 내부적으로 정렬 상태 유지
    auto it = fm.find(3);
    if (it != fm.end()) {
        std::cout << it->second << '\n'; // 출력: three
    }

    // 순회 시 메모리 접근이 연속적이므로 캐시 효율적
    for (auto& [k, v] : fm) {
        std::cout << k << ": " << v << '\n';
    }

    return 0;
}

예제: std::flat_set 사용

#include <flat_set>
#include <iostream>

int main() {
    std::flat_set<int> fs = {10, 1, 7, 3};
    // {1, 3, 7, 10} 형태로 정렬된 상태로 내부 저장

    fs.insert(5); // 삽입 후 {1,3,5,7,10}

    auto it = fs.find(7);
    if (it != fs.end()) {
        std::cout << "Found 7\n";
    }

    // 연속 메모리 저장으로 순차 순회 성능 향상
    for (auto x : fs) {
        std::cout << x << ' ';
    }

    return 0;
}

 

어떻게 좋아졌나요?

• 캐시 친화적 구조: 요소가 연속된 메모리에 저장되어 순차 순회 성능이 향상되고, 캐시 적중률 증가
• 인터페이스 일관성: std::map/std::set 유사한 인터페이스를 제공하여 학습 비용 낮음
• 특정 시나리오 성능 개선: 삽입/삭제 비용은 여전히 O(n)일 수 있으나, 검색 및 순회가 빈번한 경우에 유리
• 메모리 사용 효율성: 트리 기반 구조보다 메모리 오버헤드가 적을 수 있음

상세한 예제와 비교

std::map vs std::flat_map

• std::map: 레드-블랙 트리 기반, 삽입/삭제 O(log n), 검색 O(log n), 순차 접근 성능은 중간 정도
• std::flat_map: 정렬된 배열 기반, 삽입/삭제 평균적으로 O(n) (재배치 필요), 검색 O(log n), 순차 접근 성능 우수

// 데이터가 거의 변하지 않고, 주로 검색/순회만 하는 경우 `std::flat_map`이 유리
// 빈번한 삽입/삭제가 있다면 `std::map` 유지

std::set vs std::flat_set

• std::set: 트리 기반, O(log n) 검색/삽입/삭제, 하지만 순차 성능 떨어짐
• std::flat_set: 정렬된 배열 기반, 검색 O(log n), 순회 성능 우수하지만 삽입/삭제 O(n)

// 읽기 전용 또는 삽입/삭제 빈도가 낮고, 순회 및 검색 빈도가 높은 경우 `std::flat_set` 적합

주의 사항

• 삽입/삭제 빈도 고려: std::flat_* 컨테이너는 삽입/삭제 시 재정렬 비용 때문에 O(n) 발생. 데이터 변동이 빈번한 경우 불리
• 플랫폼/컴파일러 지원: C++23 기능이므로, 해당 기능을 지원하는 컴파일러와 표준 라이브러리가 필요
• 사용 시나리오 선정: 주로 검색과 순회가 빈번하고 구조 변화가 적은 시나리오에 최적

요약

C++23의 std::flat_map과 std::flat_set은 연속된 메모리를 활용하여 검색과 순회에 강점을 가진 정렬 컨테이너를 제공하는 새로운 선택지입니다. 기존 std::map, std::set과 유사한 인터페이스를 가지므로 사용 방법이 익숙하며, 특정 상황(검색/순회 중심 시나리오)에서 성능 최적화를 달성할 수 있습니다. 이를 통해 다양한 알고리즘과 자료 구조 선택 시 더욱 정교한 성능 튜닝이 가능합니다.

 

참고 자료:

• C++23 std::flat_map 문서
• C++23 std::flat_set 문서
• C++ 공식 웹사이트