Modern C++ : std::map (98, 11, 17, 20)

Modern C++

std::map

 

개요

std::map은 C++ 표준 라이브러리의 연관 컨테이너로, 키-값 쌍을 저장하고 관리합니다. 이진 탐색 트리(BST) 기반으로 구현되어 있으며, 키를 기준으로 자동으로 정렬됩니다. 각 키는 유일해야 하며, 삽입/삭제/검색 연산이 O(log n)의 시간 복잡도를 가집니다.

 

C++ 버전별 주요 키워드 도입 시기

• C++98: 기본 std::map 도입
• C++11: emplace, cbegin(), cend(), 범위 기반 for 루프 지원
• C++17: extract, insert_or_assign, try_emplace, merge 메서드 추가
• C++20: contains 메서드 추가 (C++20 이전에는 find와 end() 비교로 대체)

 

내용 설명

std::map은 다음과 같은 주요 특징을 가집니다:

• 정렬된 순서로 요소 저장
• 각 키는 유일함 (중복 불가)
• 삽입, 삭제, 검색이 O(log n) 시간 복잡도
• 내부적으로 레드-블랙 트리로 구현
• 반복자는 양방향 반복자(bidirectional iterator) 제공

 

예제 코드

#include <cstdint>
#include <iostream>
#include <map>

void print_map(const std::map<std::string, std::int32_t> &map)
{
    for (const auto &[key, val] : map)
    {
        std::cout << key << ": " << val << '\n';
    }
    std::cout << '\n';
}

int main()
{
    // 초기화
    auto my_map = std::map<std::string, std::int32_t>{{"Jan", 28}};

    // 요소 추가 (키가 없을 경우)
    my_map["Sam"] = 40;
    my_map["Veronika"] = 24;
    print_map(my_map);

    // 요소 수정 (키가 있을 경우)
    my_map["Veronika"] = 25;
    print_map(my_map);

    // 안전한 요소 추가 (키 존재 여부 확인 후 추가)
    if (!my_map.contains("Sam")) {
        my_map["Sam"] = 40;
    }
    if (!my_map.contains("Lisa")) {
        my_map["Lisa"] = 36;
    }
    print_map(my_map);

    // 요소 검색
    const auto it_find = my_map.find("Lisa");
    if (it_find != my_map.end()) {
        std::cout << "Found: " << it_find->first << " => " << it_find->second << '\n';
    }

    // C++17 이상에서의 안전한 요소 접근
    if (auto it = my_map.find("Jan"); it != my_map.end()) {
        std::cout << "Jan's age: " << it->second << '\n';
    }

    return 0;
}

 

실행 결과

Jan: 28
Sam: 40
Veronika: 24

Jan: 28
Sam: 40
Veronika: 25

Jan: 28
Lisa: 36
Sam: 40
Veronika: 25

Found: Lisa => 36
Jan's age: 28

 

활용팁

1. 정렬된 데이터 필요 시: 키를 기준으로 자동 정렬이 필요한 경우 사용
2. 빈번한 검색이 필요할 때: 이진 탐색을 통한 효율적인 검색이 가능
3. 중복 키가 필요할 때: std::multimap 사용 고려
4. 해시 기반이 필요할 때: std::unordered_map이 더 나은 성능을 보일 수 있음
5. 메모리 효율성: 노드 기반 컨테이너이므로 메모리 단편화가 발생할 수 있음
6. 반복자 무효화: 삽입/삭제 시에도 다른 요소들에 대한 반복자는 무효화되지 않음

 

성능 고려사항

• 삽입/삭제/검색: O(log n)
• 메모리 오버헤드: 노드 기반 구조로 인해 추가 메모리 사용
• 연속 메모리 접근이 아니므로 캐시 효율성이 떨어질 수 있음
• 정렬된 데이터가 필요없다면 std::unordered_map이 더 나은 성능을 보일 수 있음