C++에서는 연관 컨테이너로서 키-값 쌍을 저장하는 몇 가지 중요한 자료 구조가 있습니다. 각각의 특성에 따라 특정 상황에서 더 적합한 컨테이너가 됩니다. 여기서는 unordered_map, map, 그리고 이와 관련된 여러 연관 컨테이너들을 정리해서 비교하고 언제 어떤 것을 사용하는 게 좋은지 설명하겠습니다.

1. map (Ordered Map)

map은 키-값 쌍을 저장하며, 키가 자동으로 정렬됩니다. 내부적으로 이진 탐색 트리(주로 레드-블랙 트리) 구조를 사용하여 데이터를 관리합니다. 따라서 map은 삽입, 검색, 삭제 연산이 **O(log n)**의 시간 복잡도를 가집니다.

특징:

• 정렬된 순서로 데이터를 저장합니다.
• 중복된 키를 허용하지 않습니다.
• 키가 정렬되어 있어 범위 기반 연산에 유리합니다.

사용 예시:

cpp
코드 복사
#include <iostream>#include <map>int main() {
    std::map<int, std::string> myMap;

    // 요소 추가
    myMap[3] = "Three";
    myMap[1] = "One";
    myMap[2] = "Two";

    // 자동으로 키가 정렬되어 저장됨
    for (const auto& pair : myMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

언제 사용하는가?

• 정렬된 순서로 데이터가 필요할 때 유용합니다.
• 특정 범위 내의 데이터를 자주 조회해야 하는 경우, 예를 들어 lower_bound, upper_bound와 같은 함수로 키 범위 내의 값을 쉽게 찾을 수 있습니다.

시간 복잡도:

• 삽입, 검색, 삭제: O(log n)
• 정렬된 순서가 필요하면 map이 적합합니다.

2. unordered_map (Unordered Map)

unordered_map은 해시 테이블을 사용하여 키-값 쌍을 관리합니다. 키는 정렬되지 않으며, 삽입, 검색, 삭제 연산이 평균적으로 O(1) 시간 복잡도를 가집니다. 다만 최악의 경우에는 O(n)의 시간이 걸릴 수 있습니다.

특징: