C++ STL의 map 및 set 컨테이너 심층 해설

C++의 표준 템플릿 라이브러리(STL)에서 map과 set은 연관 컨테이너로 분류되며, 주로 레드-블랙 트리 기반으로 구현되어 로그 시간 복잡도 내의 삽입/삭제/탐색 연산을 보장합니다. 이 글에서는 두 컨테이너의 내부 동작 원리와 주요 기능, 실용적인 사용 예를 살펴보겠습니다.

map: 키-값 쌍의 정렬된 연결 매핑

map은 고유 키에 대응하는 값을 저장하는 연관 컨테이너입니다. 키 기준 오름차순 정렬을 유지하며, 동일 키 중복을 허용하지 않습니다.

1.1 선언 및 초기화 사용 전 반드시 <map> 헤더를 포함해야 하며, 보통 다음과 같이 선언합니다:

#include <map>
#include <string>

std::map<std::string, int> scoreTable;
scoreTable.insert({"John", 92});
scoreTable.emplace("Jane", 88);

여기서 insert()는 중복 키 입력 시 실패하나, emplace()는 내부 생성 시도를 최적화하여 편리하게 키-값 쌍을 삽입할 수 있습니다.

1.2 주요 연산

KeyUpdate 및 참조 operator[]는 키가 없을 경우 기본값으로 삽입된 후 참조되므로 편리하지만, 의도치 않은 삽입에 유의해야 합니다:

scoreTable["Alice"] = 79; // 없으면 삽입 후 설정
scoreTable.at("Bob") = 86; // 키 존재 여부 확인 후 설정

요소 검색 find()는 반복자 기반 탐색을 제공합니다. 존재하지 않을 경우 end() 반환:

auto iter = scoreTable.find("Alice");
if (iter != scoreTable.end()) {
    // .first는 키, .second는 값
    std::cout << "Score: " << iter->second << '\n';
}

요소 제거

scoreTable.erase("Alice");        // 키 기반
scoreTable.erase(iter);           // 반복자 기반
scoreTable.erase(scoreTable.begin(), ++scoreTable.begin()); // 범위 기반

순회

for (const auto& [name, point] : scoreTable) {
    std::cout << name << " → " << point << '\n';
}

C++17 기준, 구조화 바인딩을 사용하면 가독성을 크게 향상시킬 수 있습니다.

set: 정렬된 고유 요소 집합

set은 중복을 허용하지 않는 단일 요소의 정렬된 컨테이너입니다. 내부적으로도 레드-블랙 트리 구조를 기반으로 하며, 논리적으로는 '정렬된 벡터'와 유사한 성능 특성을 가집니다.

2.1 선언 및 초기화

#include <set>

std::set<int> nums;
nums.insert(10);
nums.insert(5);
nums.insert(10); // 10은 중복되어 무시됨

std::set<int> copySet(nums.begin(), nums.end()); // 복사 생성

2.2 주요 연산

요소 존재 여부 확인 count()는 존재 여부를 0 또는 1로 반환합니다:

if (nums.count(5)) {
    std::cout << "5 is present\n";
}

요소 검색 및 제거

auto pos = nums.find(5);
if (pos != nums.end()) {
    nums.erase(pos);
}

범위 쿼리 ( lower_bound / upper_bound ) map과 동일하게, 정렬된 상태에서 특정 조건을 만족하는 요소 범위를 빠르게 추출 가능합니다:

auto it1 = nums.lower_bound(5); // 5 이상(first ≥ 5) 첫 요소
auto it2 = nums.upper_bound(7); // 7 초(first > 7) 첫 요소

for (auto it = it1; it != it2; ++it) {
    std::cout << *it << ' ';
}

정리 및 비교

map은 키-값 연관을 관리할 때, set은 고유성 및 정렬 기능이 요구될 때 각각 선택합니다. 둘 다 내부 정렬 구조 덕분에 '순서 유지'와 '단조 증가 인덱스 없이도 정렬 기반 알고리즘 적용'이 가능합니다. 레드-블랙 트리 구현 특성상, 삽입 및 삭제 시 자동 균형 유지가 이루어지므로 최악의 경우에도 $O(\log n)$ 보장이라는 장점이 있습니다.

태그: cpp STL map set red-black-tree

9월 7일 00:02에 게시됨

괴물 클럽

C++ STL의 map 및 set 컨테이너 심층 해설

인기 태그