map과 multimap 개요

map과 multimap은 C++ Standard Template Library (STL)에서 제공하는 연관 컨테이너로, std::pair 객체를 사용하여 키(key)와 값(value)의 쌍으로 데이터를 저장합니다. 이 두 컨테이너는 내부적으로 레드-블랙 트리(Red-Black Tree) 자료구조를 기반으로 구현되어, 저장된 요소들이 항상 키를 기준으로 정렬된 상태를 유지합니다. 이러한 정렬 특성 때문에 map과 multimap의 반복자(iterator)는 순차 컨테이너와 달리 전진(++) 및 후진(--) 연산과 동등 비교(==, !=)만 지원하며, 요소에 대한 임의 접근은 불가능합니다.

map 컨테이너에서 키는 고유해야 하며 중복될 수 없습니다. 하지만 값은 중복이 허용됩니다. 반면, multimap은 키의 중복을 허용하므로 동일한 키를 가진 여러 요소를 저장할 수 있습니다. map 컨테이너의 키는 변경이 불가능하도록 설계되었으며, 이는 map<const KeyType, ValueType>과 같이 상수(const) 키 타입으로 명시되는 것과 유사한 효과를 가집니다. map은 operator[]와 at() 멤버 함수를 통해 키를 이용한 값의 접근 및 수정이 용이합니다.

map 컨테이너의 주요 멤버 함수

• begin(): 정렬된 첫 번째 키-값 쌍을 가리키는 양방향 반복자를 반환합니다. const 맵의 경우 const 반복자를 반환합니다.
• end(): 정렬된 마지막 요소 다음 위치를 가리키는 양방향 반복자를 반환합니다.
• rbegin(): 정렬된 마지막 요소를 가리키는 역방향 반복자를 반환합니다.
• rend(): 정렬된 첫 번째 요소 이전 위치를 가리키는 역방향 반복자를 반환합니다.
• cbegin(), cend(), crbegin(), crend(): const 버전의 반복자를 반환하여 요소 수정을 방지합니다.
• find(key): 지정된 키를 가진 요소를 검색하여 해당 요소를 가리키는 반복자를 반환합니다. 찾지 못하면 end()와 동일한 반복자를 반환합니다.
• lower_bound(key): 키가 key보다 크거나 같은 첫 번째 요소를 가리키는 반복자를 반환합니다.
• upper_bound(key): 키가 key보다 큰 첫 번째 요소를 가리키는 반복자를 반환합니다.
• equal_range(key): key와 동일한 키를 가진 모든 요소의 범위를 나타내는 두 반복자 쌍을 반환합니다. map에서는 최대 하나의 요소를 포함하는 범위를 반환합니다.
• empty(): 컨테이너가 비어 있으면 true를, 그렇지 않으면 false를 반환합니다.
• size(): 컨테이너에 저장된 요소의 개수를 반환합니다.
• max_size(): 컨테이너가 최대로 저장할 수 있는 요소의 개수를 반환합니다.
• operator[]: 키를 사용하여 해당 값에 접근하거나, 키가 존재하지 않으면 새 요소를 삽입하고 해당 값에 접근합니다.
• at(key): 키를 사용하여 해당 값에 접근합니다. 키가 존재하지 않으면 std::out_of_range 예외를 발생시킵니다.
• insert(): 새 요소를 삽입합니다.
• erase(): 지정된 키, 반복자 또는 범위의 요소를 삭제합니다.
• swap(other_map): 다른 map 컨테이너의 모든 요소를 교환합니다.
• clear(): 컨테이너의 모든 요소를 삭제합니다.
• emplace(): 인자를 사용하여 직접 요소를 구성하여 삽입합니다. insert보다 효율적일 수 있습니다.
• emplace_hint(): 힌트 반복자를 제공하여 삽입 위치를 제안하며, 해당 위치에서 요소를 구성하여 삽입합니다.
• count(key): 지정된 키를 가진 요소의 개수를 반환합니다. map에서는 최대 1을 반환합니다.

map과 multimap을 사용하려면 #include <map> 헤더 파일을 포함해야 합니다.

1. map 기본 생성

map은 기본 생성자를 통해 빈 맵을 생성할 수 있습니다. 다양한 키-값 타입 조합으로 맵을 선언할 수 있습니다.

int main() {
    // 다양한 키-값 타입으로 map 선언 가능
    std::map m1;
    std::map m2;
    // 사용자 정의 타입도 키 또는 값으로 사용 가능 (키의 경우 비교 연산자 필요)
    // std::map m3; 
    // std::map m4;
    // std::map m5;

    // system("pause"); // Windows 환경에서 콘솔 창 유지를 위해 사용
    return 0;
}
  

2. map 유효 인자 생성

map은 초기화 리스트, 다른 맵의 범위, 복사 생성자 등 다양한 방법으로 초기화될 수 있습니다.

int main() {
    // 초기화 리스트 사용 (C++11 이상)
    std::map m1 = { {"Alice", 18}, {"Bob", 20} };
    std::map m2{ {"Alice", 18}, {"Bob", 20} }; // 중괄호 초기화

    // std::pair 객체를 이용한 초기화
    std::pair p1("Charlie", 22);
    std::pair p2("David", 24);
    std::map m3 = {p1, p2};
    std::map m4{ p1, p2 };

    // 다른 map의 범위(iterators)를 이용한 초기화
    std::map m5(m1.begin(), m1.end());
    std::map m6{ m1.begin(), m1.end() };

    // 복사 생성자를 이용한 초기화
    std::map m7(m1); 
    std::map m8 = m1; // 복사 초기화

    // make_pair 함수를 이용한 초기화
    std::map m9 = { std::make_pair("Eve", 25) };
    std::map m10{ std::make_pair("Frank", 28) };

    return 0;
}
  

3. map 컨테이너 요소 개수 확인

size() 함수는 맵에 저장된 키-값 쌍의 총 개수를 반환하며, count() 함수는 특정 키가 존재하는지 확인하고 그 개수를 반환합니다 (map에서는 0 또는 1). size_type은 컨테이너 크기 정보를 나타내는 타입입니다.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map scores = { {"Math", 108}, {"Korean", 80}, {"English", 100} };

    std::cout << "scores 맵의 요소 개수: " << scores.size() << std::endl; // 출력: 3

    // count 함수 사용
    std::map<std::string, int>::size_type math_count = scores.count("Math");
    std::cout << "'Math' 키의 개수: " << math_count << std::endl; // 출력: 1

    std::map<std::string, int>::size_type physics_count = scores.count("Physics");
    std::cout << "'Physics' 키의 개수: " << physics_count << std::endl; // 출력: 0

    return 0;
}
  

• count(key): 주어진 키를 가진 요소의 개수를 반환합니다. map에서는 키가 고유하므로 결과는 0 또는 1입니다. multimap에서는 1보다 큰 값이 나올 수 있습니다.
• size_type: 컨테이너의 크기를 나타내는 부호 없는 정수 타입입니다.

4. map의 요소 접근

operator[]와 at() 멤버 함수를 사용하여 map의 요소에 접근하고 수정할 수 있습니다. operator[]는 키가 존재하지 않을 경우 새로운 요소를 삽입하지만, at()은 키가 존재하지 않으면 예외를 발생시킵니다.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::string separator(20, '-');
    std::map grades = { {"Math", 108}, {"Korean", 80}, {"English", 100} };

    // operator[]를 이용한 접근 및 수정
    std::cout << "키: Math, 값: " << grades["Math"] << std::endl; // 출력: 108

    grades["Math"] = 110; // 값 수정
    std::cout << "수정된 Math 점수: " << grades["Math"] << std::endl; // 출력: 110

    grades["Politics"] = 90; // 키가 없으면 새 요소 삽입
    std::cout << "추가된 Politics 점수: " << grades["Politics"] << std::endl; // 출력: 90

    std::cout << separator << std::endl;

    // at() 함수를 이용한 접근 및 수정
    std::cout << "키: Math, 값: " << grades.at("Math") << std::endl; // 출력: 110

    grades.at("Korean") = 110; // 값 수정
    std::cout << "수정된 Korean 점수: " << grades.at("Korean") << std::endl; // 출력: 110
    
    std::cout << separator << std::endl;

    // 반복자를 이용한 요소 접근
    std::map data = { {1, "one"} };
    auto iter = data.begin();
    std::cout << "이터레이터로 접근한 키: " << iter->first << std::endl;  // 출력: 1
    std::cout << "이터레이터로 접근한 값: " << iter->second << std::endl; // 출력: one

    // key는 반복자를 통해 직접 수정할 수 없습니다.
    // iter->first = 10; // 컴파일 오류 발생

    return 0;
}
  

• operator[]: 키로 값에 접근합니다. 키가 없으면 새로운 요소를 생성하고 기본값으로 초기화한 후 해당 값에 접근합니다.
• at(key): 키로 값에 접근합니다. 키가 없으면 std::out_of_range 예외를 발생시킵니다.
• 반복자를 사용하면 iter->first (키)와 iter->second (값)으로 각 멤버에 접근할 수 있습니다. map의 키는 반복자를 통해서도 수정할 수 없습니다.

5. map의 반복자

map의 반복자는 컨테이너 내의 요소를 순회하는 데 사용됩니다. begin(), end(), rbegin(), rend() 및 const 버전의 반복자(cbegin() 등)가 제공됩니다. map의 반복자는 요소를 정렬된 순서대로 가리키며, 전진(++), 후진(--) 연산과 동등 비교(==, !=)만 가능합니다. 반복자를 사용하여 키의 값을 수정하는 것은 불가능합니다.

6. map에 요소 삽입

insert(), emplace(), emplace_hint() 함수를 사용하여 map에 요소를 삽입할 수 있습니다. insert()는 std::pair 객체나 초기화 리스트를 받으며, 삽입 성공 여부를 나타내는 std::pair<iterator, bool>를 반환할 수 있습니다. emplace()와 emplace_hint()는 요소를 직접 구성하여 삽입하므로 더 효율적일 수 있습니다.

#include <iostream>
#include <map>
#include <string>
#include <utility> // std::pair, std::make_pair

int main() {
    std::map m1;

    // 1. std::pair 객체를 이용한 insert
    std::pair p1("Alice", 18);
    auto result1 = m1.insert(p1); 
    if (result1.second) {
        std::cout << "Successfully inserted: " << result1.first->first << std::endl;
    }

    // 2. pair 생성자를 이용한 insert
    auto result2 = m1.insert(std::pair("Bob", 20));
    if (result2.second) {
        std::cout << "Successfully inserted: " << result2.first->first << std::endl;
    }

    // 3. 초기화 리스트를 이용한 insert (C++11 이상)
    // 여러 요소를 한 번에 삽입할 경우 void 반환
    m1.insert({ {"Charlie", 22}, {"David", 24} }); 

    // 4. make_pair 함수를 이용한 insert
    auto result3 = m1.insert(std::make_pair("Eve", 25));
    if (result3.second) {
        std::cout << "Successfully inserted: " << result3.first->first << std::endl;
    }

    // 5. value_type을 이용한 insert
    m1.insert(std::map::value_type("Frank", 26));

    // 6. emplace() 함수 사용 (C++11 이상) - 효율적
    auto result4 = m1.emplace("Grace", 27);
    if (result4.second) {
        std::cout << "Successfully emplaced: " << result4.first->first << std::endl;
    }

    // 7. emplace_hint() 함수 사용 (C++11 이상) - 힌트 제공
    // 힌트 반복자는 삽입 위치를 제안하지만, 최종 위치는 키 값에 따라 결정됩니다.
    auto result5 = m1.emplace_hint(m1.begin(), "Heidi", 28);
    if (result5.second) {
        std::cout << "Successfully emplaced with hint: " << result5.first->first << std::endl;
    }

    // 삽입 시도 (키 중복)
    auto result_duplicate = m1.insert({"Alice", 30}); // Alice는 이미 존재하므로 삽입 실패
    if (!result_duplicate.second) {
        std::cout << "Failed to insert 'Alice' again. Existing value: " << result_duplicate.first->second << std::endl;
    }

    return 0;
}
  

• insert() 반환값: std::pair<iterator, bool>. iterator는 삽입된 요소 또는 키가 이미 존재하는 경우 해당 요소의 반복자를 가리키고, bool은 삽입 성공 여부를 나타냅니다.
• emplace() 및 emplace_hint(): std::pair 객체를 미리 생성하지 않고 직접 생성자를 호출하여 요소를 삽입하므로 오버헤드를 줄일 수 있습니다.
• map은 정렬된 컨테이너이므로, emplace_hint()와 같이 삽입 위치를 지정하더라도 실제 삽입 위치는 키 값에 따라 결정됩니다.

7. map 요소 삭제

erase() 함수는 지정된 키, 반복자 또는 범위의 요소를 삭제합니다. clear() 함수는 map의 모든 요소를 삭제합니다.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map m1 = { {"Alice", 25}, {"Bob", 26}, {"Charlie", 27} };

    // 1. 키로 요소 삭제
    size_t erased_count_key = m1.erase("Alice"); // 반환값: 삭제된 요소의 개수 (map에서는 0 또는 1)
    std::cout << "Erased 'Alice': " << erased_count_key << " element(s)." << std::endl;

    // 2. 반복자로 요소 삭제
    auto it_bob = m1.find("Bob");
    if (it_bob != m1.end()) {
        auto next_it = m1.erase(it_bob); // 삭제된 요소 다음 요소를 가리키는 반복자 반환
        std::cout << "Erased 'Bob'. Next element is: " << (next_it != m1.end() ? next_it->first : "N/A") << std::endl;
    }

    // 3. 범위(반복자)로 요소 삭제
    std::map m2 = { {"D", 1}, {"E", 2}, {"F", 3}, {"G", 4} };
    auto it_begin = m2.begin();
    std::advance(it_begin, 1); // 'E'를 가리키도록 이동
    auto it_end = m2.begin();
    std::advance(it_end, 3);   // 'F'를 가리키도록 이동 (F는 포함되지 않음)
    
    auto it_after_erase = m2.erase(it_begin, it_end); // ['E', 'F') 범위 삭제
    std::cout << "Erased range. Element after erased range: " << (it_after_erase != m2.end() ? it_after_erase->first : "N/A") << std::endl; // 출력: G

    // 4. 모든 요소 삭제
    m1.clear();
    std::cout << "m1 size after clear(): " << m1.size() << std::endl; // 출력: 0

    return 0;
}
  

• erase(key): 지정된 키를 가진 요소를 삭제하고, 삭제된 요소의 개수 (map에서는 0 또는 1)를 반환합니다.
• erase(iterator): 해당 반복자가 가리키는 요소를 삭제하고, 삭제된 요소 다음 요소를 가리키는 반복자를 반환합니다.
• erase(first, last): [first, last) 범위 내의 요소들을 삭제하고, last와 동일한 반복자를 반환합니다.
• clear(): 컨테이너의 모든 요소를 삭제합니다.

8. map 요소 검색

find(), lower_bound(), upper_bound(), equal_range() 함수를 사용하여 map의 요소를 검색할 수 있습니다.

#include <iostream>
#include <map>
#include <string>
#include <utility> // std::pair

int main() {
    std::map m1 = { {"Alice", 25}, {"Bob", 26}, {"Charlie", 27} };

    // 1. find() 함수 사용
    auto it_find_bob = m1.find("Bob");
    if (it_find_bob != m1.end()) {
        std::cout << "Found 'Bob': Key=" << it_find_bob->first << ", Value=" << it_find_bob->second << std::endl;
    } else {
        std::cout << "'Bob' not found." << std::endl;
    }

    auto it_find_david = m1.find("David");
    if (it_find_david == m1.end()) {
        std::cout << "'David' not found." << std::endl;
    }

    // 2. lower_bound(), upper_bound(), equal_range() 함수 사용 (키가 정렬된 경우 유용)
    std::map sorted_map = { {10, "Ten"}, {20, "Twenty"}, {30, "Thirty"} };

    // 키가 20인 요소 찾기
    auto lb_20 = sorted_map.lower_bound(20); // >= 20 인 첫 번째 요소
    auto ub_20 = sorted_map.upper_bound(20); // > 20 인 첫 번째 요소
    auto er_20 = sorted_map.equal_range(20); // == 20 인 요소의 범위

    if (lb_20 != sorted_map.end()) {
        std::cout << "lower_bound(20): Key=" << lb_20->first << ", Value=" << lb_20->second << std::endl;
    }
    if (ub_20 != sorted_map.end()) {
        std::cout << "upper_bound(20): Key=" << ub_20->first << ", Value=" << ub_20->second << std::endl;
    }
    if (er_20.first != sorted_map.end()) {
        std::cout << "equal_range(20) - first: Key=" << er_20.first->first << ", Value=" << er_20.first->second << std::endl;
        std::cout << "equal_range(20) - second: Key=" << er_20.second->first << ", Value=" << er_20.second->first << std::endl; // second는 다음 요소 가리킴
    }

    // 키가 25인 요소 찾기 (존재하지 않음)
    auto lb_25 = sorted_map.lower_bound(25); // >= 25 인 첫 번째 요소 (30)
    auto ub_25 = sorted_map.upper_bound(25); // > 25 인 첫 번째 요소 (30)
    auto er_25 = sorted_map.equal_range(25); // == 25 인 요소의 범위 (둘 다 30을 가리킴)

    if (lb_25 != sorted_map.end()) {
        std::cout << "lower_bound(25): Key=" << lb_25->first << ", Value=" << lb_25->second << std::endl;
    }
     if (er_25.first != sorted_map.end()) {
        std::cout << "equal_range(25) - first: Key=" << er_25.first->first << ", Value=" << er_25.first->second << std::endl;
     }
     if (er_25.second != sorted_map.end()) {
        std::cout << "equal_range(25) - second: Key=" << er_25.second->first << ", Value=" << er_25.second->second << std::endl;
     } else {
         std::cout << "equal_range(25) - second points to end()" << std::endl;
     }


    return 0;
}
  

• find(key): 키가 key인 첫 번째 요소를 가리키는 반복자를 반환합니다. 찾지 못하면 end() 반복자를 반환합니다.
• lower_bound(key): 키가 key보다 크거나 같은 첫 번째 요소를 가리키는 반복자를 반환합니다.
• upper_bound(key): 키가 key보다 큰 첫 번째 요소를 가리키는 반복자를 반환합니다.
• equal_range(key): key와 동일한 키를 가진 모든 요소의 범위를 나타내는 두 반복자 쌍을 반환합니다. map에서는 최대 하나의 요소를 포함합니다.

9. map의 정렬 규칙

map은 기본적으로 키를 기준으로 오름차순으로 정렬됩니다. 정렬 순서는 템플릿 매개변수로 제공되는 비교 함수 객체(Comparator)에 의해 결정됩니다. 기본값은 std::less<KeyType>입니다. 내림차순 정렬을 원하면 std::greater<KeyType>을 사용할 수 있습니다.

#include <iostream>
#include <map>
#include <string>
#include <functional> // std::greater

int main() {
    // 기본 오름차순 정렬
    std::map ascending_map = { {30, "Thirty"}, {10, "Ten"}, {20, "Twenty"} };
    std::cout << "Ascending map:" << std::endl;
    for (const auto& pair : ascending_map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // std::greater를 사용한 내림차순 정렬
    std::map descending_map = { {30, "Thirty"}, {10, "Ten"}, {20, "Twenty"} };
    std::cout << "\nDescending map:" << std::endl;
    for (const auto& pair : descending_map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
  

10. map의 value_comp() 함수

value_comp() 함수는 map의 값 비교 함수 객체를 반환합니다. 이 함수 객체는 map에 저장된 두 요소(std::pair)를 인자로 받아, 첫 번째 요소의 키가 두 번째 요소의 키보다 앞에 오는지 여부를 반환합니다. 이 비교 기준은 map 생성 시 지정된 정렬 규칙을 따릅니다.

#include <iostream>
#include <map>
#include <string>
#include <functional> // std::greater

int main() {
    // 내림차순 정렬 map
    std::map desc_map = { {25, "Apple"}, {26, "Banana"} };

    // 값 비교 함수 객체 얻기
    auto compare_values = desc_map.value_comp();

    // map의 value_type (std::pair) 생성
    std::map::value_type val1 = std::make_pair(25, "Apple");
    std::map::value_type val2 = std::make_pair(26, "Banana");

    // 비교 수행
    if (compare_values(val1, val2)) {
        // desc_map은 내림차순이므로, 25는 26보다 앞에 오는 것이 아니라 뒤에 옵니다.
        // 따라서 이 조건은 false가 됩니다.
        std::cout << "val1 (key 25) comes before val2 (key 26) according to the map's ordering." << std::endl;
    } else {
        std::cout << "val1 (key 25) does not come before val2 (key 26) according to the map's ordering." << std::endl; // 이 메시지가 출력됩니다.
    }

    return 0;
}
  

11. map의 key_comp() 함수

key_comp() 함수는 map의 키 비교 함수 객체(Comparator)를 반환합니다. 이 반환된 함수 객체를 사용하여 두 키 값을 비교할 수 있으며, 이는 map의 정렬 규칙과 동일합니다.

#include <iostream>
#include <map>
#include <string>
#include <functional> // std::greater

int main() {
    // 내림차순 정렬 map
    std::map desc_map = { {25, "Apple"}, {26, "Banana"} };

    // 키 비교 함수 객체 얻기
    auto compare_keys = desc_map.key_comp();

    // 키 비교 수행 (std::greater에 의해 1이 2보다 앞에 오는 것이 true)
    if (compare_keys(1, 2)) {
        std::cout << "Key 1 comes before Key 2 according to the map's ordering." << std::endl; // 이 메시지가 출력됩니다.
    } else {
        std::cout << "Key 1 does not come before Key 2 according to the map's ordering." << std::endl;
    }

    return 0;
}
  

12. map의 기타 함수

map은 swap() (두 맵의 요소를 교환), empty() (맵이 비었는지 확인), max_size() (최대 저장 가능 요소 수) 등 유용한 멤버 함수들을 제공합니다.

13. map과 multimap의 차이점

multimap은 map과 대부분의 멤버 함수를 공유하지만, 가장 큰 차이점은 multimap은 동일한 키를 가진 여러 요소를 저장할 수 있다는 점입니다. 이로 인해 다음과 같은 차이가 발생합니다:

• erase(key): multimap에서 이 함수는 삭제된 모든 키-값 쌍의 개수를 반환합니다 (1보다 클 수 있음).
• count(key): multimap에서 이 함수는 특정 키를 가진 모든 요소의 개수를 반환합니다 (1보다 클 수 있음).
• lower_bound(), upper_bound(), equal_range(): 이 함수들은 multimap에서 특정 키를 가진 모든 요소를 포함하는 범위를 올바르게 처리하는 데 더 유용합니다.

주의사항

• map의 키는 정렬 순서에 영향을 미치므로, 삽입된 요소의 키를 직접 수정하는 것은 권장되지 않으며, 또한 대부분의 구현에서 불가능합니다. 키를 변경하려면 해당 요소를 삭제하고 새로운 키-값 쌍을 삽입해야 합니다.
• size_type, value_type 등 내장 타입들은 다른 STL 컨테이너와 유사하게 사용됩니다.
• multimap도 map과 유사하게 작동합니다.